trang chủ / đề bài / icpc19_reg_g

Sinh số

Đề bài

Mô tả

Ging đang phát triển thế hệ máy tính tiếp theo: "máy tính Tanquum".

"Máy tính Tanquum" tận dụng những thành tựu vật lý tiên tiến, cho phép sắp xếp lại các chữ số của mọi số nguyên dương chỉ trong một lệnh.

Ứng dụng của nó là vô hạn. Ví dụ, từ số 1, "máy tính Tanquum" có thể tạo ra mọi số nguyên dương x chỉ với hai loại lệnh: tăng một đơn vị và sắp xếp lại.

Cụ thể hơn, chỉ có hai thao tác sau được phép thực hiện trên số nguyên a:

  1. Tăng a thêm 1, tức là gán a:=a+1.
  2. Sắp xếp lại các chữ số của a. Kết quả không được có chữ số 0 ở đầu. Ví dụ, từ 102, với một lệnh loại này, bạn có thể thu được một trong các số sau: 102, 120, 201, 210.

Vì "máy tính Tanquum" rất tiên tiến, nó luôn chỉ dùng số lệnh ít nhất.

Bạn vừa được Ging tuyển để hỗ trợ phát triển "máy tính Tanquum". Nhiệm vụ đầu tiên của bạn là kiểm tra tính đúng đắn của "máy tính Tanquum". Cho một số x, hãy tìm số lệnh ít nhất cần dùng để biến 1 thành x.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên t (1≤t≤1000) là số bộ dữ liệu.

t dòng tiếp theo, mỗi dòng chứa một số nguyên x (1≤x≤109).

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra trên một dòng số lệnh ít nhất.

Ràng buộc

  • 1≤t≤1000
  • 1≤x≤109

Ví dụ

Input Output Giải thích
3
5
26
843
4
17
44
Cần 4 lần tăng để tạo ra số 5. Có thể tạo ra 26 bằng 17 lệnh: 11 lần tăng để được 12, 1 lần sắp xếp lại để được 21, rồi 5 lần tăng để được 26.
4
1
9
10
100
0
8
9
28
Ví dụ bổ sung (không có trong đề gốc). Số 1 không cần lệnh nào. Số 100: tăng 1→19 (18 lệnh), sắp xếp lại thành 91, rồi tăng 9 lần tới 100.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0