Hacker

Nguồn: CLUE OJ – Chương 19: Đệ quy cơ bản Độ khó: Dễ Đệ quy Cây đệ quy

Đề bài

Bạn là một hacker tài khoản ngân hàng. Ban đầu bạn có 1 USD trong tài khoản của mình và bạn muốn có chính xác $N$ USD trong tài khoản. Bạn đã viết hai bản hack:

• Loại hack thứ nhất có thể nhân số tiền bạn sở hữu với $10$.
• Loại hack thứ hai có thể nhân số tiền bạn sở hữu với $20$.

Những hack này có thể được sử dụng bao nhiêu lần cũng được. Bạn đang thắc mắc có thể đạt được đúng $N$ USD mong muốn bằng cách sử dụng các hack này hay không. Hãy lập trình để giải quyết điều này.

Dữ liệu vào:

• Dòng đầu tiên chứa một số nguyên $T$ là số lượng trường hợp kiểm tra $(1 \le T \le 100)$.
• $T$ dòng tiếp theo, mỗi dòng chứa một số nguyên $N$ cần kiểm tra $(1 \le N \le 10^{18})$.

Kết quả: với mỗi trường hợp in ra một dòng: Yes nếu có thể hack được đúng số tiền $N$, còn không thể thì in No.

Giới hạn thời gian: 1 giây, bộ nhớ: 256 MB. Nguồn bài: VinhDinhCoder.

Ví dụ – input

5
1
2
10
25
200

Ví dụ – output

Yes
No
Yes
No
Yes

Lời mở đầu

Ở ví dụ: $N = 1$ thì không cần hack gì cả (đã có sẵn 1 USD) → Yes. $N = 10$: hack ×10 một lần. $N = 200$: hack ×10 rồi ×20 (hoặc ×20 rồi ×10). Còn $N = 2$ hay $N = 25$ thì không cách nào ghép ra được → No.

Đây là bài mở đầu rất hợp để tập nghĩ theo kiểu đệ quy: "đang có $x$ USD, mình thử từng loại hack, mỗi lựa chọn lại là một bài toán y hệt nhưng với số tiền mới". Mình làm 2 cách: đi lên từ 1 và đi ngược từ $N$ về 1.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test100 testÝ tưởngcây đệ quyCách 1đi lên từ 1Cách 2đi ngược từ NTổng kếtkết quả

Bộ testBộ test chính thức có gì?

Bộ test có 100 test, mỗi test gồm nhiều truy vấn. Đề không chia subtask, nhưng nhìn dữ liệu thì thấy rõ 2 mức:

Test	Số truy vấn T	N nhỏ nhất	N lớn nhất	Yes / No
1–30	5 … 10	1	$6{,}4 \cdot 10^{7}$	113 / 116
31–100	100 … 100	112	$10^{18}$	2.860 / 4.140

• Test 1–30 là các số "nhỏ" (tối đa $6{,}4 \cdot 10^7$), test 31–100 có $N$ tới đúng $10^{18}$ – phải dùng long long và cẩn thận tràn số khi nhân.
• Gần một nửa số truy vấn có đáp án Yes: các số dạng $10^a \cdot 20^b$ như $1\,600\,000\,000\,000\,000$ được cài vào rất nhiều.

Kết quả chạy thật (giới hạn 1 giây):

Mức	Điều kiện	Test	Cách 1 (đi lên từ 1)	Cách 2 (đi ngược từ N)
Mức 1	$T \le 10$, $N \le 6{,}4 \cdot 10^7$	1–30	30/30	30/30
Mức 2	$T = 100$, $N \le 10^{18}$	31–100	70/70	70/70

Ý tưởngCây đệ quy: mỗi nút rẽ 2 nhánh ×10 và ×20

Gọi hack(x) là câu hỏi: "đang có $x$ USD, có hack tiếp để được đúng $N$ không?". Khi đó:

Công thức đệ quy

• Điểm dừng 1: $x = N$ → trả về true.
• Điểm dừng 2: $x$ đã quá lớn (nhân 10 là vượt $N$) → trả về false, vì số tiền chỉ tăng chứ không giảm.
• Bước đệ quy: hack(x) = hack(10x) || hack(20x).

Đáp án là hack(1). Các lời gọi tạo thành một cây nhị phân: mỗi nút $x$ có 2 con $10x$ và $20x$. Vì số tiền tăng ít nhất 10 lần sau mỗi bước, cây sâu tối đa khoảng $\log_{10} N \le 18$ tầng.

Em nhập $N$ rồi bấm Tiếp để xem máy đi trên cây đệ quy (nhánh trên là ×10, nhánh dưới là ×20):

N =

Ví dụ nhanh:

Cách 1Đệ quy đi lên từ 1 USD

Cài đặt đúng công thức ở trên. Điểm dừng 2 mình viết là x > N / 10 chứ không phải x * 10 > N: hai cách viết cùng ý nghĩa, nhưng với $x$ khoảng $10^{18}$ thì phép nhân x * 10 sẽ tràn long long (vượt $9{,}2 \cdot 10^{18}$) cho ra số âm rác. Phép chia thì không bao giờ tràn.

C++▶ Chạy tay từng dòng codeCách 1: đệ quy đi lên từ 1 USD, mỗi lời gọi thử ×10 rồi ×20.

Dữ liệu vào (stdin) – sửa thoải mái5 1 2 10 25 200

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Nếu $x \le N/10$ thì $10x \le N$ và $20x \le 2N \le 2 \cdot 10^{18}$ – vẫn vừa long long, nên hai lời gọi con an toàn.
2. Toán tử || "ngắt mạch": nếu nhánh ×10 đã trả về true thì máy không gọi nhánh ×20 nữa.
3. $N = 1$: ngay lời gọi đầu hack(1) đã có $x = N$ → Yes.
4. Bản Python không lo tràn số (số nguyên Python lớn tuỳ ý), nên viết x > N cũng được.

Không gian$O(\log N)$ (độ sâu đệ quy)

Thời giansố nút cây, $\le$ vài $10^5$ mỗi truy vấn

Số nút của cây: mỗi nút là một cách chọn dãy hack có tích $\le N$, với $N \le 10^{18}$ chỉ cỡ vài trăm nghìn nút trong trường hợp xấu nhất – rất nhanh.

Kết quả chạy thật: Bản C++ đúng 100/100 test; test đúng chạy lâu nhất 0.01s. Bản Python đúng 100/100 test; test đúng chạy lâu nhất 0.24s.

Cách 2Đệ quy đi ngược từ N về 1

Đi ngược lại: lần hack cuối cùng là ×10 hoặc ×20, nên trước lần hack đó ta có $N/10$ hoặc $N/20$ USD. Hỏi tiếp: số đó có quay về được 1 không?

Nhận xét giúp cắt nhánh

Cả ×10 lẫn ×20 đều làm số tiền chia hết cho 10. Vậy nếu $N \ne 1$ mà $N$ không chia hết cho 10 thì chắc chắn No. Nhánh ×20 chỉ thử khi $N$ chia hết cho 20.

C++▶ Chạy tay từng dòng codeCách 2: đệ quy đi ngược từ N, chia cho 10 hoặc 20 để về 1.

Dữ liệu vào (stdin) – sửa thoải mái5 1 2 10 25 200

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Cách này chỉ chia nên không bao giờ tràn số.
2. Rất nhiều số bị loại ngay ở lời gọi đầu (ví dụ $N = 25$: $25 \bmod 10 \ne 0$ → No luôn).
3. Thật ra còn có lời giải "toán" không cần đệ quy: $N = 10^a \cdot 20^b = 10^{a+b} \cdot 2^b$, tức là bỏ hết các chữ số 0 ở cuối (giả sử bỏ được $k$ số 0) thì phần còn lại phải là $2^b$ với $b \le k$. Nhưng chương này luyện đệ quy nên mình giữ cách 2.

Không gian$O(\log N)$ (độ sâu đệ quy)

Thời gianrất nhỏ, thường $O(\log N)$

Kết quả chạy thật: Bản C++ đúng 100/100 test; test đúng chạy lâu nhất 0.00s. Bản Python đúng 100/100 test; test đúng chạy lâu nhất 0.03s.

Tổng kếtKết quả chạy thật trên bộ test

Cách	Ngôn ngữ	Đúng	Lâu nhất	Ghi chú
1. Đệ quy đi lên từ 1	C++	100/100	0.01s	Full điểm
	Python	100/100	0.24s	Full điểm
2. Đệ quy đi ngược từ N	C++	100/100	0.00s	Full điểm
	Python	100/100	0.03s	Full điểm

Ghi chú của mình: thời gian là thời gian CPU đo trên máy mình, giới hạn 1 giây. Cả hai cách đều full điểm vì cây đệ quy rất nông (≤ 18 tầng). Điều cần nhớ nhất ở bài này là tràn số: khi $N$ lên tới $10^{18}$, đừng viết x * 10 > N mà hãy viết x > N / 10.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇