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 😇

Xếp hậu (Tin học trẻ toàn quốc 2024 – Vòng khu vực – Bảng B)

Nguồn: Tin học trẻ 2024 Độ khó: Trung bình Quay lui Vét cạn Nhánh cận

Đề bài

Nguồn đề: Hội thi Tin học trẻ toàn quốc 2024 – Vòng khu vực – Bảng B (bài Xếp hậu). Vòng khu vực dùng chung một đề cho cả ba miền Bắc, Trung, Nam. Đề 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).

Có một bàn cờ $n \times n$, hàng đánh số $1..n$ từ trên xuống, cột đánh số $1..n$ từ trái sang. Ô ở hàng $i$, cột $j$ gọi là ô $(i, j)$ và có một trọng số $w_{ij}$ (số nguyên không âm).

Ta cần đặt đúng $k$ quân hậu lên bàn cờ sao cho không có hai quân nào chiếu nhau. Hai quân hậu chiếu nhau khi chúng cùng hàng, hoặc cùng cột, hoặc cùng một đường chéo (chéo xuôi hay chéo ngược đều tính).

Yêu cầu: gọi $s$ là tổng trọng số của các ô có đặt hậu. Hãy đặt sao cho $s$ lớn nhất và in ra giá trị đó.

Dữ liệu vào:

• Dòng 1: hai số nguyên $n, k$ ($1 \le k \le n \le 8$).
• $n$ dòng tiếp theo: dòng thứ $i$ gồm $n$ số nguyên không âm $w_{i1}, w_{i2}, \dots, w_{in}$ (mỗi số không quá $10^6$).

Dữ liệu đảm bảo luôn có cách đặt $k$ quân hậu không chiếu nhau.

Kết quả: một số nguyên là giá trị lớn nhất của $s$.

Subtask:

• Subtask 1 (30%): $k = 1$;
• Subtask 2 (30%): $k \le 3$;
• Subtask 3 (40%): không có ràng buộc gì thêm.

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

3 2
1 0 2
0 0 2
0 2 0

Ví dụ – output

4

Giải thích: đặt 2 quân hậu ở ô $(1, 3)$ và $(3, 2)$: hai ô này khác hàng, khác cột và không cùng đường chéo (hiệu hàng là 2, hiệu cột là 1). Tổng trọng số $2 + 2 = 4$. Không có cách nào được nhiều hơn: ô $(2, 3)$ cũng có trọng số 2 nhưng nó cùng cột với $(1, 3)$ và cùng đường chéo với $(3, 2)$.

Lưu ý: đề gốc chỉ ghi $1 \le k \le n \le 8$. Có hai trường hợp không thể đặt được: $n = k = 2$ và $n = k = 3$. Bộ test trên CLUE tránh hai trường hợp này (mình ghi rõ "dữ liệu đảm bảo luôn có cách đặt"); các lời giải bên dưới nếu gặp thì in $-1$.

Lời mở đầu

Bài toán 8 quân hậu là bài "nhập môn quay lui" kinh điển. Đề Tin học trẻ 2024 đổi đi một chút: không bắt đặt đủ $n$ quân mà chỉ đúng $k$ quân, và mỗi ô có trọng số, cần tổng lớn nhất. Vì $n \le 8$ nên bài này hoàn toàn là bài vét cạn có suy nghĩ: vét cạn "ngây thơ" thì chậm, còn vét cạn theo hàng có cắt nhánh thì chạy trong nháy mắt. Mình đi từ cách dễ nhất (chỉ ăn subtask 1) tới cách full điểm.

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ưởngmỗi hàng 1 hậuCách 1k = 1 – 30đCách 2vét cạn – 60đCách 3quay lui – 100đTổng kếtkết quả

Bộ testBộ test có gì?

Bộ test trên CLUE do mình tự sinh theo đúng giới hạn và tỉ lệ điểm subtask của đề: 20 test (test 1 là ví dụ của đề, thuộc subtask 2 vì $k = 2$). Mỗi bảng có đủ kiểu: trọng số ngẫu nhiên, toàn số 0, toàn số $10^6$, bàn cờ có vài ô rất lớn nằm chiếu nhau để "bẫy" lời giải tham lam.

Nhóm	Test	Các giá trị $n$	Các giá trị $k$	Trọng số lớn nhất	Bàn cờ mọi ô bằng nhau	Đáp án lớn nhất
Subtask 1	2–8	1, 2, 5, 7, 8	1	1.000.000	test 2, 4, 6	1.000.000
Subtask 2	1, 9–12	3, 6, 8	2, 3	1.000.000	không có	2.963.462
Subtask 3	13–20	4, 7, 8	4, 5, 6, 7, 8	1.000.000	test 20	8.000.000

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

Lời giải cuối cùng (cách 3) 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 theo từng subtask (ô xanh = đúng hết các test của subtask đó):

Subtask	Điều kiện	Test	Cách 1 chỉ k = 1	Cách 2 vét cạn bộ ô	Cách 2 Python	Cách 3 quay lui	Cách 3 Python
Subtask 1 (30%)	$k = 1$	2–8	7/7	7/7	7/7	7/7	7/7
Subtask 2 (30%)	$k \le 3$	1, 9–12	0/5	5/5	5/5	5/5	5/5
Subtask 3 (40%)	không ràng buộc thêm	13–20	0/8	4/8	1/8	8/8	8/8

Ý tưởngMỗi hàng có nhiều nhất một quân hậu

Nhận xét quan trọng nhất: hai quân hậu cùng hàng thì chiếu nhau, nên mỗi hàng có tối đa 1 quân hậu. Vậy ta đi lần lượt từng hàng $1, 2, \dots, n$, với mỗi hàng chỉ có $n + 1$ lựa chọn:

• bỏ trống hàng này, hoặc
• đặt 1 quân hậu vào một cột $j$ chưa bị chiếu (cột $j$ chưa có hậu, hai đường chéo đi qua ô đó chưa có hậu).

Để kiểm tra "bị chiếu" trong $O(1)$, ta đánh dấu 3 mảng: cot[j], cheo1[i + j] (các ô trên cùng đường chéo ngược có cùng $i + j$) và cheo2[i - j + n - 1] (cùng đường chéo xuôi có cùng $i - j$; cộng $n - 1$ để chỉ số không âm).

Khi đã đặt đủ $k$ quân thì cập nhật đáp án. Thêm một phép cắt nhánh: nếu số hàng còn lại $n - i$ ít hơn số quân còn phải đặt $k - cnt$ thì đi tiếp cũng vô ích, quay lui luôn. Em nhập bàn cờ rồi bấm Tiếp để xem quá trình quay lui (ô đỏ nhạt = đang bị chiếu, hàng viền vàng = hàng đang xét):

n = k = Bảng w (hàng cách nhau bởi ;) =

Ví dụ nhanh:

Cách 1k = 1: chỉ cần ô lớn nhất (Subtask 1)

Khi $k = 1$ thì chỉ có một quân hậu, không có chuyện chiếu nhau. Đáp án chính là trọng số lớn nhất của bàn cờ. Đọc tới đâu lấy max tới đó:

C++▶ Chạy tay từng dòng codeCách 1: k = 1 – đọc bàn cờ, lấy trọng số lớn nhất.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Đáp án không âm (trọng số không âm) nên khởi tạo best = 0 là được.

Không gian$O(1)$

Thời gian$O(n^2)$

Kết quả chạy thật: Bản C++ đúng 7/20 test, sai test 1, 9–20 (các test đúng chạy lâu nhất 0.003s) → 30 điểm (subtask 1). Các test có $k \ge 2$ đều sai vì chương trình vẫn chỉ in một ô.

Cách 2Vét cạn mọi bộ k ô (Subtask 1, 2)

Cách "thật thà" nhất: đánh số các ô từ $0$ tới $n^2 - 1$ (ô số $x$ nằm ở hàng $x / n$, cột $x \% n$), sinh mọi tổ hợp $k$ ô theo thứ tự tăng dần, khi đã chọn đủ $k$ ô mới kiểm tra từng cặp có chiếu nhau không. Hai ô $(r_1, c_1)$ và $(r_2, c_2)$ chiếu nhau khi cùng hàng, cùng cột, cùng $r - c$ (chéo xuôi) hoặc cùng $r + c$ (chéo ngược).

C++▶ Chạy tay từng dòng codeCách 2: sinh mọi bộ k ô theo thứ tự tăng dần, đủ k ô mới kiểm tra chiếu nhau.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Hàm chon(id, cnt): đã chọn cnt ô, ô tiếp theo phải có số thứ tự từ id trở đi – nhờ vậy mỗi bộ ô chỉ được sinh đúng một lần.
• Không cắt nhánh gì cả: kể cả khi 2 ô đầu đã chiếu nhau, chương trình vẫn sinh hết các ô còn lại rồi mới phát hiện.

Số bộ phải thử là $\binom{n^2}{k}$: với $n = 8$, $k = 3$ chỉ có $41\,664$ bộ, nhưng $k = 5$ đã là $7{,}6$ triệu, $k = 8$ là $4{,}4$ tỉ bộ.

Không gian$O(n^2)$

Thời gian$O\left(\binom{n^2}{k} \cdot k^2\right)$

Kết quả chạy thật: Bản C++ đúng 16/20 test, quá thời gian test 13–15, 20 (các test đúng chạy lâu nhất 0.571s). Ăn trọn subtask 1, 2; subtask 3 chỉ qua được các test có $k \le 6$ hoặc bảng nhỏ (test 13, 14, 20 có $n = k = 8$, test 15 có $n = 8, k = 7$ đều quá thời gian). Bản Python đúng 13/20 test, quá thời gian test 13–17, 19–20 (các test đúng chạy lâu nhất 0.050s) – Python chậm hơn nhiều nên rớt thêm vài test của subtask 3.

Cách 3Quay lui theo từng hàng + cắt nhánh (full)

Làm đúng như phần ý tưởng: hàm dat(i, cnt, s) xét hàng $i$ khi đã đặt cnt quân với tổng trọng số s.

C++▶ Chạy tay từng dòng codeCách 3: quay lui theo hàng – mỗi hàng đặt 1 hậu vào cột chưa bị chiếu hoặc bỏ trống, cắt nhánh khi không đủ hàng.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. if(cnt == k): đủ $k$ quân thì cập nhật best và dừng nhánh này (không đặt thêm vì đề yêu cầu đúng $k$ quân).
2. if(n - i < k - cnt) return; – cắt nhánh: còn $n - i$ hàng (hàng $i..n-1$, đếm từ 0) mà cần thêm $k - cnt$ quân thì không thể đủ. Dòng này cũng thay cho điều kiện dừng i == n.
3. Đặt hậu: đánh dấu 3 mảng, gọi đệ quy, rồi gỡ đánh dấu (đây chính là bước "quay lui").
4. Cuối cùng thử phương án bỏ trống hàng $i$.

Vì sao nhanh? Các nhánh bị chiếu bị loại ngay khi đặt, không đợi đủ $k$ quân. Mình đếm thử với $n = 8$: số lần gọi hàm dat lớn nhất là khoảng $97\,000$ (khi $k = 5$), còn $k = 8$ chỉ $4\,022$ lần – so với $4{,}4$ tỉ bộ của cách 2.

Không gian$O(n^2)$

Thời giantối đa $O((n+1)^n)$ trên lý thuyết, thực tế với $n = 8$ chưa tới $10^5$ lần gọi hàm

Kết quả chạy thật: Bản C++ đúng 20/20 test, chạy lâu nhất 0.004s. Full điểm. Bản Python đúng 20/20 test, chạy lâu nhất 0.080s – bài này Python cũng thoải mái.

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
1. Chỉ lấy ô lớn nhất (k = 1)	C++	7/20	0.003s	30%
	Python	7/20	0.018s	30%
2. Vét cạn mọi bộ k ô	C++	16/20	0.571s	60%
	Python	13/20	0.050s	60%
3. Quay lui theo hàng + cắt nhánh	C++	20/20	0.004s	100%
	Python	20/20	0.080s	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, các test quá giờ bị dừng ở khoảng 4 giây). Điều đáng nhớ ở bài này: cùng là "vét cạn" nhưng vét cạn theo cấu trúc bài toán (mỗi hàng một quân, loại ngay ô bị chiếu, cắt nhánh khi không đủ hàng) nhanh hơn vét cạn mù quáng hàng chục nghìn lần. Khi $n$ nhỏ (ở đây $n \le 8$), hãy nghĩ tới quay lui trước khi nghĩ tới công thức phức tạp.

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 😇