| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
PTIT017B - ACM PTIT 2017 B - CHUYỂN N THÀNH 1 |
Cho số nguyên dương N (N<231). Chỉ được phép sử dụng hai thao tác A, B dưới đây, hãy dịch chuyển N về 1 sao cho số các thao tác A, B được thực hiện ít nhất.
Thao tác A: Biến đổi N = N-1.
Thao tác B: Biến đổi N = max(u, v), trong đó u*v = N (u>1, v>1).
Ví dụ N = 17 được thực hiện ít nhất 4 bước A, B như sau:
Thao tác A: N = N – 1 = 17-1 = 16
Thao tác B: N = max (u, v) = max(4*4) = 4
Thao tác B: N = max (u, v) = max(2*2) = 2
Thao tác A: N = N-1 = 2-1 = 1
Input
- Dòng đầu tiên ghi lại T là số lượng bộ test (T≤50).
- Mỗi bộ test gồm một dòng ghi lại một số nguyên không âm.
Output
- Ứng với mỗi bộ test đưa ra số các bước A, B thực hiện ít nhất để dịch chuyển test tương ứng về 1.
Example
Input:
6
17
33
255
1024
1029
65535
Output:
4
5
5
5
6
6
| Được gửi lên bởi: | adm |
| Ngày: | 2017-04-29 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
