Xếp que diêm (Tin học trẻ toàn quốc 2024 – Vòng chung kết toàn quốc – Bảng B)

Nguồn: Tin học trẻ 2024 Độ khó: Dễ Duyệt toàn bộ Tham lam

Đề bài

Nguồn đề: Hội thi Tin học trẻ toàn quốc 2024 – Vòng chung kết toàn quốc – Bảng B (bài Xếp que diêm). Đề bên dưới do mình viết lại bằng lời của mình cho dễ hiểu (giữ đúng nghĩa, đúng số liệu và ví dụ của đề gốc).

Người ta dùng que diêm để xếp các chữ số từ $0$ đến $9$ giống như trên đồng hồ điện tử (mỗi nét là một que diêm). Số que cần cho từng chữ số như hình dưới (số ghi bên dưới mỗi chữ số):

Cho số tự nhiên $N$ có ba chữ số. Xếp $N$ bằng que diêm theo đúng cách trên. Hỏi nếu chỉ dùng đúng số que diêm đó (không thừa, không thiếu) thì xếp được số có ba chữ số nhỏ nhất và lớn nhất là bao nhiêu? Số xếp được không được có chữ số $0$ ở đầu.

Dữ liệu vào: một dòng chứa số $N$ ($100 \le N \le 999$).

Kết quả: dòng thứ nhất ghi số có ba chữ số nhỏ nhất xếp được; dòng thứ hai ghi số có ba chữ số lớn nhất xếp được.

Giới hạn thời gian: 1 giây. Dữ liệu nhập từ bàn phím, in ra màn hình.

Ví dụ – input

123

Ví dụ – output

104
971

Giải thích: số $123$ cần $2 + 5 + 5 = 12$ que diêm. Các số $104$ ($2 + 6 + 4$) và $971$ ($6 + 4 + 2$) cũng cần đúng $12$ que, và không có số ba chữ số nào nhỏ hơn $104$ hay lớn hơn $971$ dùng đúng 12 que.

Lời mở đầu

Đây là bài "khởi động" của Bảng B vòng chung kết. Chỉ có $900$ số có ba chữ số nên duyệt hết là đủ full điểm. Nhưng bài vẫn có hai cái bẫy nho nhỏ mà mình muốn các bạn để ý: chữ số 7 trong hình của đề dùng 4 que (không phải 3 như nhiều người quen), và khi làm cách tham lam thì không có chữ số nào dùng đúng 3 que. Mình sẽ cho các bạn thấy cả kết quả chạy thật của các bản "dính bẫy".

Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ

Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.

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ộ test20 testÝ tưởngđếm queCách 1duyệt 900 sốCách 2tham lamTổng kếtkết quả

Bộ testBộ test có gì?

Bộ test trên CLUE do mình tự sinh: 20 test (test 1 là ví dụ của đề), gồm các số đặc biệt như $100$, $999$, $111$, $888$, các số có chữ số $7$, cộng thêm các số ngẫu nhiên. Đề không chia subtask (mọi test đều có $N$ ba chữ số).

Số test	Tổng số que $S$	Số lượng số có 3 chữ số xếp được bằng $S$ que	Chỉ có đúng 1 số (nhỏ nhất = lớn nhất)	Có chữ số 7 trong $N$ hoặc trong đáp án
20	từ 6 đến 21	từ 1 đến 153	test 2–3	6 test

• Hai test chỉ có đúng một số xếp được: $S = 6$ que thì chỉ có số $111$, $S = 21$ que thì chỉ có $888$ (vì mỗi chữ số dùng nhiều nhất 7 que).
• Có 6 test liên quan tới chữ số 7 – đây là các test bắt lỗi đếm sai số que của chữ số 7.

Đã nộp thử trên bộ chấm chính thức

Lời giải cuối cùng trong bài mình đã nộp lên hệ thống chấm chính thức của Hội thi (tinhoctre.vn) và được 100/100 điểm (AC).

Kết quả chạy thật các cách bên dưới:

Subtask	Điều kiện	Test	Cách 1 C++	Cách 1 Python	Cách 2 C++	Cách 2 Python
Toàn bộ (100%)	$100 \le N \le 999$	1–20	20/20	20/20	20/20	20/20

Ý tưởngĐếm que rồi tìm số cùng số que

Đầu tiên chép đúng bảng số que từ hình của đề vào một mảng:

Chữ số	0	1	2	3	4	5	6	7	8	9
Số que	6	2	5	5	4	5	6	4	7	6

Tính $S$ = tổng số que của ba chữ số của $N$. Bài toán trở thành: tìm số có ba chữ số nhỏ nhất và lớn nhất có tổng số que đúng bằng $S$. Có hai cách nghĩ:

• Duyệt: thử hết $900$ số từ $100$ tới $999$ (cách 1).
• Tham lam: muốn số nhỏ nhất thì chữ số hàng trăm phải nhỏ nhất có thể, rồi tới hàng chục, hàng đơn vị – miễn là phần còn lại vẫn xếp được (cách 2). Cách này dùng được cả khi $N$ có rất nhiều chữ số.

Em nhập $N$ rồi bấm Tiếp để xem cách tham lam dựng từng chữ số (chữ số cam là chữ số đang thử, xanh là đã chốt):

N =

Ví dụ nhanh:

Cách 1Duyệt mọi số có ba chữ số (full)

Ba vòng lặp lồng nhau cho chữ số hàng trăm $a$ (từ 1, vì không có số 0 ở đầu), hàng chục $b$ và hàng đơn vị $c$. Vì duyệt theo thứ tự tăng dần nên số đầu tiên có tổng que bằng $S$ là số nhỏ nhất, số cuối cùng là số lớn nhất.

C++▶ Chạy tay từng dòng codeCách 1: duyệt a, b, c theo thứ tự tăng dần (khoảng 2000 bước – em bấm ⏭ hoặc chọn tốc độ "Rất nhanh").

Dữ liệu vào (stdin) – sửa thoải mái123

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. n / 100, n / 10 % 10, n % 10 lần lượt là chữ số hàng trăm, hàng chục, hàng đơn vị của $N$.
2. nho == -1 nghĩa là chưa tìm được số nào – số đầu tiên tìm được chính là số nhỏ nhất. Luôn có ít nhất một số thoả mãn (chính $N$!) nên không bao giờ in ra $-1$.

Không gian$O(1)$

Thời gian$O(900)$ – duyệt 900 số

Kết quả chạy thật: Bản C++ đúng 20/20 test, chạy lâu nhất 0.004s. Bản Python đúng 20/20 test, chạy lâu nhất 0.027s. Full điểm.

Bẫy 1: chữ số 7 dùng mấy que?

Trên đồng hồ điện tử quen thuộc, chữ số 7 thường chỉ có 3 nét. Nhưng trong hình của đề, chữ số 7 có thêm nét trái trên nên dùng 4 que. Mình thử sửa mảng thành {6, 2, 5, 5, 4, 5, 6, 3, 7, 6} (chữ số 7 dùng 3 que) rồi chạy trên bộ test: bản này chỉ đúng 12/20 test, sai test 1, 7–8, 10, 14, 17–18, 20 (các test đúng chạy lâu nhất 0.004s). Ví dụ của đề ($123$) vẫn ra $104$ nhưng số lớn nhất lại ra $977$ – sai ngay! Bài học: đếm que từ hình của đề, đừng đếm theo trí nhớ.

Cách 2Tham lam từng chữ số (mở rộng cho số nhiều chữ số)

Nếu đề cho $N$ có tới 15 chữ số thì không thể duyệt hết $10^{15}$ số. Ta dựng đáp án từng chữ số từ trái sang phải:

• Muốn số nhỏ nhất: ở mỗi vị trí, thử chữ số $d$ từ $0$ (hoặc từ $1$ nếu là vị trí đầu) lên $9$; chốt chữ số đầu tiên mà số que còn lại $r = s - que[d]$ vẫn đủ để xếp các vị trí phía sau.
• Muốn số lớn nhất: làm giống hệt nhưng thử $d$ từ $9$ xuống $0$.

Vì sao đúng? Hai số cùng số chữ số thì số nào có chữ số đầu tiên (khác nhau) nhỏ hơn sẽ nhỏ hơn – nên chữ số hàng cao phải được ưu tiên tuyệt đối, miễn là phía sau vẫn còn cách xếp.

Bẫy 2: "phía sau còn xếp được" kiểm tra thế nào?

Mỗi chữ số dùng từ 2 tới 7 que, nên nhiều bạn kiểm tra 2 * con <= r && r <= 7 * con (còn con chữ số phía sau). Sai! Không có chữ số nào dùng đúng 3 que, nên 1 chữ số không thể xếp bằng 3 que. Bản kiểm tra kiểu này: chỉ đúng 18/20 test, sai test 17–18 (các test đúng chạy lâu nhất 0.004s) – ví dụ $N = 418$ ($S = 13$) sẽ chốt "97" rồi kẹt lại vì chữ số cuối cần đúng 3 que.

Cách chắc chắn: tính trước bảng duoc[i][x] = "có xếp được $i$ chữ số (chữ số nào cũng được, kể cả 0) bằng đúng $x$ que không" bằng quy hoạch động nhỏ: duoc[0][0] = true, và duoc[i][x] = true nếu có chữ số $d$ để duoc[i-1][x - que[d]] đúng.

C++▶ Chạy tay từng dòng codeCách 2: lập bảng duoc[i][x] rồi dựng từng chữ số – nhỏ nhất (thử 0→9) và lớn nhất (thử 9→0).

Dữ liệu vào (stdin) – sửa thoải mái123

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Đọc $N$ dưới dạng string để code dùng được cho số có bao nhiêu chữ số cũng được (k = n.size()).
2. Biểu thức nho ? t : 9 - t giúp dùng chung một hàm cho cả hai chiều: t chạy 0→9 thì d chạy 0→9 (số nhỏ nhất) hoặc 9→0 (số lớn nhất).
3. Ở mỗi vị trí luôn tìm được chữ số để chốt, vì chính các chữ số của $N$ là một cách xếp hợp lệ.

Không gian$O(k \cdot 7k)$

Thời gian$O(k^2 \cdot 7 \cdot 10)$ với $k$ là số chữ số

Kết quả chạy thật: Bản C++ đúng 20/20 test, chạy lâu nhất 0.003s. Bản Python đúng 20/20 test, chạy lâu nhất 0.028s. Mình còn cho hai cách chạy trên cả 900 giá trị $N$ có thể và so sánh – kết quả giống hệt nhau.

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

Cách	Ngôn ngữ	Đúng	Lâu nhất (test đúng)	Điểm theo subtask
Bẫy: chữ số 7 dùng 3 que	C++	12/20	0.004s	0%
1. Duyệt 900 số	C++	20/20	0.004s	100%
	Python	20/20	0.027s	100%
Bẫy: coi mọi số que 2..7 đều xếp được	C++	18/20	0.004s	0%
2. Tham lam từng chữ số	C++	20/20	0.003s	100%
	Python	20/20	0.028s	100%

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). Với bài nhỏ như thế này, cách 1 (duyệt) là lựa chọn an toàn nhất trong phòng thi: ít code, khó sai. Cách 2 đáng học vì đó là kỹ thuật "dựng đáp án nhỏ nhất/lớn nhất từng chữ số, kiểm tra phần còn lại còn làm được không" – gặp rất nhiều trong các bài khó hơn. Hai bẫy cần nhớ: đếm que theo đúng hình của đề, và đừng tưởng tập giá trị "xếp được" là một đoạn liên tục.

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 😇

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.

Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ

Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.

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 😇