Bộ đề ôn luyện thi Học sinh giỏi Tin học 12 (Kèm đáp án)

 Bộ đề ôn luyện thi Học sinh giỏi Tin học 12 (Kèm đáp án) - De-Thi.com
Bài 3. (6,0 điểm) VẬN CHUYỂN. Gồm 10 bộ test, mỗi bộ test 0,6 điểm.
 Test VANCHUYEN.INP VANCHUYEN.OUT Điểm
 1 101539 2 0,6
 2 10011155100 252 0,6
 3 1501607999 54 0,6
 4 27930076153 1024 0,6
 5 50050042465 878 0,6
 6 700800268527 2898 0,6
 7 950955418894 4472 0.6
 8 100010007663 479 0,6
 9 99991000009991132 3493 0.6
 10 100000100000999911234 41726 0,6
Hướng dẫn thuật toán:
Bài 1. (7,0 điểm) PHƯƠNG TRÌNH BẬC HAI
Nhận xét: Vì phương trình bậc hai ax2 +bx + c = 0 có nghiệm x = 1 nên thay x = ―1 vào 
phương trình, ta có a ⋅ ( ― 1)2 ―b ⋅ ( ― 1) + c = 0⇔a ― b + c = 0⇔a + c = b
Bài toán đưa về đếm số bộ ba phần tử của dãy số thoả điều kiện tổng hai phần từ bằng phần 
từ còn lại.
- Subtask 1 : n ≤ 300
Dùng 3 lệnh lặp duyệt 3 chỉ số 푖,푗, sao cho [푖] + [푗] = [ ] (với 푖 ≠ 푗)
Độ phức tạp : O(n3).
- Subtask 2 : 푛 ≤ 3000
Vì các phân tử của dãy là số dương nên ta có a,c < b.
Sắp xếp dãy theo thứ tự tăng dần, duyệt xét từng phần tử b = u[k].
Với mỗi giá trị k, duyệt các chỉ số i và tìm kiếm nhị phân tìm chỉ số j. 
Độ phức tạp O 푛2log 푛
Hoặc dùng phương pháp 2 con trỏ tìm hai chỉ số 푖,푗, Độ phức tạp (푛2).
 5
- Subtask 3: n ≤ 10 ,ui ≤ n
Vì các phần tử của dãy là đôi một khác nhau và 푖 ≤ 푛 nên dãy đã cho chính là hoán vị của n 
số nguyên dương đầu tiên.
 De-Thi.com Bộ đề ôn luyện thi Học sinh giỏi Tin học 12 (Kèm đáp án) - De-Thi.com
Với mỗi giá trị k(1 ≤ k ≤ n), sử dụng công thức để tính số cách chọn cặp số i,j sao cho 
i + j = k. Độ phức tạp O(n).
Bài 2. (7,0 điểm) ĐOÀN XE QUA CẦU
Gọi 퐹[푖] là thời gian ngắn nhất khi các xe từ xe 1 đến xe i qua cầu, ta có:
 퐹[푖] = Min{퐹[푗 ― 1] + (푗,푖)},푗 = 1,푖 ― 1
với T(j,i) là thời gian để nhóm từ xe thứ j đến thứ i qua cầu cùng lúc, 
T(j,i) = L/min(vj,.,vi)khiwj + + wi ≤ P
Độ phức tạp thuật toán (푛2).
Bài 3. (6,0 điểm) VẬN CHUYỂN 
Áp dụng thuật toán Dijkstra tìm đường đi ngắn nhất từ s đến t.
- Subtask 1 : n ≤ 103
Sử dụng thuật toán Dijkstra thông thường.
- Subtask 2 : n ≤ 105
Sử dụng thuật toán Dijkstra kết hợp cấu trúc dữ liệu Heap.
 De-Thi.com Bộ đề ôn luyện thi Học sinh giỏi Tin học 12 (Kèm đáp án) - De-Thi.com
 ĐỀ SỐ 5
 SỞ GIÁO DỤC VÀ ĐÀO TẠO KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH 
 TỈNH QUẢNG NINH THPT NĂM 2022
 Môn thi: TIN HỌC - Bảng A
 Thời gian: 180 phút, không kể thời gian giao đề
 TỔNG QUAN ĐỀ THI
 Tệp Tệp Tệp Thời gian
Bài Tên bài Bộ nhớ Điểm
 chương trình dữ liệu kết quả / test
1 Loại bỏ một phần tử remo.* remo.inp remo.out 1024 MB 1 giây 6
2 Nhà hàng rest.* rest.inp rest.out 1024 MB 1 giây 6
3 Độ rộng tối đa maxi.* maxi.inp maxi.out 1024 MB 1 giây 5
4 Lát nền tili.* tili.inp tili.out 1024 MB 1 giây 3
Dấu * được thay thế bởi pas hoặc cpp hoặc py của ngôn ngữ lập trình được sử dụng tương 
ứng là Pascal hoặc C++ hoặc Python.
Hãy lập trình giải các bài toán sau:
Bài 1. Loại bỏ một phần tử (6 điểm)
An có một mảng gồm 푛 số nguyên phân biệt. Bình lấy đúng 푛 ―1 phần tử từ mảng và 
cộng thêm cho mỗi phần tử này một số nguyên dương , sau đó xáo trộn chúng để tạo thành 
một mảng mới có 푛 ―1 phần tử.
Cho hai mảng và , bạn hãy xác định giá trị mà Bình đã chọn. Nếu có nhiều giá trị thỏa 
mãn, thì hãy đưa ra giá trị nhỏ nhất trong số chúng.
Dữ liệu: Vào từ tệp văn bản remo.inp. Dòng đầu tiên chứa số nguyên 푡 (1 ≤ 푡 ≤ 5) là số 
test. Các dòng tiếp theo mô tả 푡 test, mỗi test mô tả trên 3 dòng:
- Dòng đầu tiên của mỗi test chứa số nguyên 푛 (2 ≤ 푛 ≤ 105) là số phần tử của mảng ;
 9
- Dòng thứ hai của mỗi test chứa 푛 số nguyên phân biệt 1, 2, , 푛 (1 ≤ 푖 ≤ 10 ) là các 
phần tử của mảng ;
 9
- Dòng thứ ba của mỗi test chứa n – 1 số nguyên phân biệt 1, 2, , 푛―1 (1 ≤ 푖 ≤ 2 × 10 ) 
là các phần tử của mảng b.
Kết quả: Ghi ra tệp văn bản remo.out. Với mỗi test, in ra giá trị x mà Bình đã chọn. Trường 
hợp có nhiều giá trị x thỏa mãn, hãy in giá trị nhỏ nhất trong số chúng. Dữ liệu cho đảm bảo 
rằng luôn tồn tại ít nhất một giá trị x. 
 De-Thi.com Bộ đề ôn luyện thi Học sinh giỏi Tin học 12 (Kèm đáp án) - De-Thi.com
Ví dụ:
 remo.inp remo.out
 3 7
 4 2
 1 4 3 8 1
 15 8 11
 2
 4 8
 10
 2
 2 4
 3
Trong test thứ nhất, Bình lấy các phần tử 1, 4, 8 và cộng thêm 7 vào mỗi phần tử này được 
mảng 8, 11, 15, sau đó anh ta xáo trộn chúng để có được mảng b mới là 15, 8, 11. Không có 
giá trị nào khác thỏa mãn yêu cầu bài toán.
Trong test thứ hai có 2 lựa chọn với Bình để xem xét: một là lấy phần tử 4 và cộng thêm 6 
vào nó để được mảng b; hai là lấy phần tử 8 và cộng thêm 2 vào nó để được mảng b. Nhưng 
giá trị 2 là nhỏ nhất trong số các giá trị x thỏa mãn, do đó câu trả lời là 2.
Trong test thứ ba chỉ có một lựa chọn với Bình để xem xét là lấy phần tử 2 và cộng thêm 1 
vào nó để được mảng b. Nếu anh ta lấy phần tử 4 thì anh ta sẽ phải cộng thêm - 1 vào phần 
tử này, nhưng giá trị cộng thêm này không dương nên việc cộng này là không hợp lệ.
Ràng buộc:
- Có 25% số test ứng với 25% số điểm của bài thỏa mãn: 푡 = 1 và 2 ≤ 푛 ≤ 10;
 2 4
- 25% số test khác ứng với 25% số điểm của bài thỏa mãn: 2 ≤ 푛 ≤ 10 ;1 ≤ 푖 ≤ 10 và 
 4
1 ≤ 푖 ≤ 2 × 10 ;
- 25% số test khác ứng với 25% số điểm của bài thỏa mãn: 2 ≤ 푛 ≤ 103;
- 25% số test còn lại ứng với 25% số điểm của bài không có thêm ràng buộc nào.
Bài 2. Nhà hàng (6 điểm)
An là một đầu bếp và anh ấy vừa khai trương một nhà hàng. Nhà hàng mở cửa trong 푛 
khoảng thời gian [푙1, 1),[푙2, 2), ,[푙푛, 푛). Không có hai khoảng thời gian nào giao nhau, tức 
là với mọi 푖,푗 sao cho 푖 ≠ 푗 thì 푖 < 푙푗 hoặc 푗 < 푙푖. Có người (được đánh số từ 1 tới ) lên 
kế hoạch ăn ở nhà hàng. Gọi thời gian người 푖 đến nhà hàng là 푖. Nếu nhà hàng mở cửa vào 
thời gian đó, tức là tồn tại chỉ số 푗 (1 ≤ 푗 ≤ 푛) sao cho 푙푗 ≤ 푖 < 푗, thì người này không phải 
đợi, nhưng nếu nhà hàng đang đóng cửa thì người này phải chờ cho tới khi nhà hàng mở cửa 
hoặc phải chờ mãi mãi.
 De-Thi.com Bộ đề ôn luyện thi Học sinh giỏi Tin học 12 (Kèm đáp án) - De-Thi.com
Với mỗi người, hãy tính thời gian họ phải chờ đợi (nếu người đó không phải đợi thì thời gian 
chờ đợi bằng 0), hoặc xác định người đó sẽ phải chờ mãi mãi.
Dữ liệu: Vào từ tệp văn bản rest.inp. Dòng đầu tiên chứa số nguyên 푡 (1 ≤ 푡 ≤ 102) là số 
test. Các dòng tiếp theo mô tả 푡 test, mỗi test mô tả như sau:
- Dòng đầu tiên của mỗi test chứa hai số nguyên 푛 và (1 ≤ 푛, ≤ 105);
 9
- 푛 dòng tiếp theo của mỗi test, mỗi dòng chứa hai số nguyên 푙푖 và 푖 (1 ≤ 푙푖 < 푖 ≤ 10 ). 
Không có hai khoảng thời gian nào giao nhau;
 9
- dòng tiếp theo của mỗi test, mỗi dòng chứa một số nguyên 푖 1 ≤ 푖 ≤ 10 .
Tổng các giá trị 푛 của tất cả các test không vượt quá 3 × 105 và tổng các giá trị của tất cả 
các test không vượt quá 3 × 105.
Kết quả: Ghi ra tệp văn bản rest.out. Với mỗi test, in ra 푛 dòng: dòng thứ 푖 chứa một số 
nguyên là thời gian người thứ 푖 phải chờ đợi hoặc in ra ―1 nếu người đó phải chờ mãi mãi.
Ví dụ:
 rest.inp rest.out
 1 0
 4 5 0
 5 7 2
 9 10 -1
 2 3 1
 20 30
 5
 6
 7
 35
 1
Ràng buộc:
- Có 50% số test ứng với 50% số điểm của bài thỏa mãn: 푡 = 1;푛 ≤ 103 và ≤ 103;
- 50% số test còn lại ứng với 50% số điểm của bài không có thêm ràng buộc nào.
Bài 3. Độ rộng tối đa (5 điểm)
Cho hai xâu: xâu 푠 độ dài 푛 và xâu 푡 độ dài .
Một dãy , trong đó , được gọi là đẹp nếu với 
 1, 2, , 1 ≤ 1 < 2 < < ≤ 푛 푠 푖 = 푡푖
mọi 푖 = 1, 2, , . Độ rộng của dãy được định nghĩa là ( 푖+1 ― 푖).
 1 ≤ 푖 < 
Bạn hãy xác định độ rộng tối đa của một dãy đẹp. Giả thiết rằng luôn tồn tại ít nhất một dãy 
đẹp với hai xâu 푠 và 푡 cho trước.
 De-Thi.com Bộ đề ôn luyện thi Học sinh giỏi Tin học 12 (Kèm đáp án) - De-Thi.com
Dữ liệu: Vào từ tệp văn bản maxi.inp. Dòng đầu tiên chứa hai số nguyên 푛 và 
(2 ≤ ≤ 푛 ≤ 2 × 105) tương ứng là độ dài xâu 푠 và 푡. Dòng thứ hai chứa xâu 푠 độ dài 푛. 
Dòng thứ ba chứa xâu 푡 độ dài . Xâu 푠 và 푡 chỉ gồm các chữ cái viết thường của bảng chữ 
cái Latinh. Dữ liệu đảm bảo luôn tồn tại ít nhất một dãy đẹp với hai xâu 푠 và 푡.
Kết quả: Ghi ra tệp văn bản maxi.out một số nguyên là độ rộng tối đa của một dãy đẹp.
Ví dụ:
 maxi.inp maxi.out
 5 3 3
 abbbc
 abc
 5 2 4
 aaaaa
 aa
 5 5 1
 abcdf
 abcdf
Trong ví dụ đầu tiên, chúng ta có 3 dãy đẹp: dãy đẹp 1, 2, 5 có độ rộng bằng 3; dãy đẹp 1, 3, 
5 có độ rộng bằng 2 và dãy đẹp 1, 4, 5 có độ rộng bằng 3. Độ rộng tối đa của một dãy đẹp là 
3.
Trong ví dụ thứ hai, dãy đẹp 1, 5 là dãy đẹp có độ rộng tối đa là 4.
Trong ví dụ thứ ba có đúng một dãy đẹp là 1, 2, 3, 4, 5 với độ rộng là 1.
Ràng buộc:
- Có 30% số test ứng với 30% số điểm của bài thỏa mãn: 2 ≤ ≤ 푛 ≤ 20;
- 40% số test khác ứng với 40% số điểm của bài thỏa mãn: 2 ≤ ≤ 푛 ≤ 2 × 103;
- 30% số test còn lại ứng với 30% số điểm của bài không có thêm ràng buộc nào.
Bài 4. Lát nền (3 điểm)
Viện Công nghệ thông tin đang được tu sửa và nâng cấp. Một trong những hạng mục công 
việc là lát lại hành lang nối từ phòng làm việc sang phòng đặt máy chủ. Hành lang có độ 
rộng 2 và độ dài 푛 được biểu thị như một lưới ô vuông gồm 2 hàng và n cột. Để lát người ta 
dùng các viên gạch men loại kích thước 1 x 1 và kích thước 1 x 2 với số lượng dự trữ không 
hạn chế. Các viên gạch 1 x 2 có thể lát dọc hoặc xoay ngang. Trước đây hành lang được lát 
bằng các viên gạch kích thước 1 x 1 và có k viên gạch bên dưới lắp các thiết bị điện tử, trong 
đó viên thứ 푖 ở hàng 푖 và cột 푖. Ban Giám đốc viện không muốn lắp lại hệ thống điện tử 
vốn đang hoạt động rất tốt, nên yêu cầu đánh dấu những viên này và không được bóc chúng 
lên trong quá trình lát nền.
 De-Thi.com Bộ đề ôn luyện thi Học sinh giỏi Tin học 12 (Kèm đáp án) - De-Thi.com
Bộ phận thi công phàn nàn về yêu cầu trên, vì như thế sẽ hạn chế khả năng lát. Điều này làm 
Trưởng phòng vật tư đề nghị bộ phận lập trình tính số phương án lát nền khác nhau mà vẫn 
đảm bảo yêu cầu đã nêu, để bên thi công thấy có nhiều cách làm khác nhau.
Bạn hãy tính và đưa ra số phương án lát nền theo mô-đun 109 +7 (tức là đưa ra số dư của số 
phương án lát nền chia cho 109 +7). Hai phương án gọi là khác nhau nếu tồn tại hai ô kề 
cạnh trong phương án này được phủ bằng một viên gạch 1 x 2, còn phương án kia thì không 
được phủ bằng một viên gạch 1 x 2.
Ví dụ với 푛 = 2 và = 0 (không có viên gạch kích thước 1 × 1 nào được đánh dấu), ta có 7 
phương án lát nền như minh họa trong hình dưới đây:
Ví dụ khác với n = 3 và k = 1 viên gạch kích thước 1 x 1 được đánh dấu ở vị trí (1, 2) (ô 
được tô kín trong hình vẽ), ta có 8 phương án lát nền như minh họa trong hình dưới đây:
Dữ liệu: Vào từ tệp văn bản tili.inp. Dòng đầu tiên chứa số nguyên 푛 và 
 5
(1 ≤ 푛 ≤ 10 ;0 ≤ < 2푛). Dòng thứ 푖 trong dòng tiếp theo chứa hai số nguyên 푖 và 푖 
(1 ≤ 푖 ≤ 2;1 ≤ 푖 ≤ 푛).
Kết quả: Ghi ra tệp văn bản tili.out một số nguyên là số phương án lát nền theo mô-đun 
109 +7.
Ví dụ:
 tili.inp tili.out
 2 0 7
 3 1 8
 1 2
Ràng buộc:
- Có 20% số test ứng với 20% số điểm của bài thỏa mãn: 1 ≤ 푛 ≤ 8; = 0;
- 20% số test khác ứng với 20% số điểm của bài thỏa mãn: 1 ≤ 푛 ≤ 103; = 0;
- 20% số test khác ứng với 20% số điểm của bài thỏa mãn: 1 ≤ 푛 ≤ 105; = 0;
- 20% số test khác ứng với 20% số điểm của bài thỏa mãn: 1 ≤ 푛 ≤ 105; = 1;
- 20% số test còn lại ứng với 20% số điểm của bài không có thêm ràng buộc nào.
 ---------- HẾT ----------
 De-Thi.com Bộ đề ôn luyện thi Học sinh giỏi Tin học 12 (Kèm đáp án) - De-Thi.com
 ĐÁP ÁN
Bài 1. Loại bỏ một phần tử (6 điểm)
Phân bổ điểm
- Có 25% số test ứng với 25% số điểm của bài thỏa mãn: 푡 = 1 và 2 ≤ 푛 ≤ 10;
 2 4
- 25% số test khác ứng với 25% số điểm của bài thỏa mãn: 2 ≤ 푛 ≤ 10 ;1 ≤ 푖 ≤ 10 và 
 4
1 ≤ 푖 ≤ 2 × 10 ;
- 25% số test khác ứng với 25% số điểm của bài thỏa mãn: 2 ≤ 푛 ≤ 103;
- 25% số test còn lại ứng với 25% số điểm của bài không có thêm ràng buộc nào.
Thuật toán
Sắp xếp các mảng , theo thứ tự tăng dần.
Gọi 1 = 1 ― 1 và 2 = 1 ― 2. Nếu 2 ≤ 0 hoặc 푛 > 2, 2 ― 3 ≠ 2 thì = 1, ngược 
lại = 2.
Độ phức tạp thuật toán là (푡.푛.푙표 2푛).
Bài 2. Nhà hàng (6 điểm)
Phân bổ điểm
- Có 50% số test ứng với 50% số điểm của bài thỏa mãn: 푡 = 1;푛 ≤ 103 và ≤ 103;
- 50% số test còn lại ứng với 50% số điểm của bài không có thêm ràng buộc nào.
Thuật toán
Đặt [푖] = {푙푖, 푖}, rồi sắp xếp các [푖] tăng dần.
Với mỗi truy vấn 푖, ta tìm chỉ số 푗 lớn nhất sao cho [푖]. 푖 푠푡 ≤ 푖 bằng thuật toán tìm kiếm 
nhị phân. Xảy ra các trường hợp sau:
Trường hợp 1. Không tồn tại chỉ số 푗: Câu trả lời bài toán là [1]. 푖 푠푡 ― 푖.
Trường hợp 2. Tồn tại chỉ số 푗: 
- Nếu < [푗].푠푒 표푛 thì câu trả lời bài toán là 0;
- Nếu ≥ [푗].푠푒 표푛 :
+ Nếu 푗 < 푛 thì câu trả lời bài toán là [푗 + 1]. 푖 푠푡 ― 푖;
+ Nếu 푗 ≥ 푛 thì câu trả lời bài toán là ―1.
 푡
Độ phức tạp thuật toán là 푡 × ∑푖=1(푛푖 + 푖)푙표 2(푛푖) .
Bài 3. Độ rộng tối đa (5 điểm)
Phân bổ điểm
- Có 30% số test ứng với 30% số điểm của bài thỏa mãn: 2 ≤ ≤ 푛 ≤ 20;
- 40% số test khác ứng với 40% số điểm của bài thỏa mãn: 2 ≤ ≤ 푛 ≤ 2 × 103;
- 30% số test còn lại ứng với 30% số điểm của bài không có thêm ràng buộc nào.
Thuật toán
Gọi 푙푖, 푖 là giá trị nhỏ nhất, lớn nhất của 푖 sao cho nó hợp lệ với tất cả các phần tử khác của 
dãy .
 De-Thi.com Bộ đề ôn luyện thi Học sinh giỏi Tin học 12 (Kèm đáp án) - De-Thi.com
Chúng ta tính 푙푖 bằng cách tìm phần tử đầu tiên sau 푙푖―1 mà nó bằng 푡푖. Việc này có thể làm 
bằng thuật toán tham lam hoặc thuật toán quy hoạch động.
Bằng cách tương tự, chúng ta tính 푖.
Sau khi tìm 푙푖 và 푖, câu trả lời bài toán sẽ là ( 푖+1 ― 푙푖).
 푖 = 1,2, ,푛 ― 1
Độ phức tạp thuật toán là ( + 푛).
Bài 4. Lát nền (3 điểm)
Phân bổ điểm
- Có 20% số test ứng với 20% số điểm của bài thỏa mãn: 1 ≤ 푛 ≤ 8; = 0;
- 20% số test khác ứng với 20% số điểm của bài thỏa mãn: 1 ≤ 푛 ≤ 103; = 0;
- 20% số test khác ứng với 20% số điểm của bài thỏa mãn: 1 ≤ 푛 ≤ 105; = 0;
- 20% số test khác ứng với 20% số điểm của bài thỏa mãn: 1 ≤ 푛 ≤ 105; = 1;
- 20% số test còn lại ứng với 20% số điểm của bài không có thêm ràng buộc nào.
Thuật toán
Subtask 1, 2, 3: 풌 = 
- [푖] là số cách lát đến cột 푖 mà tất cả các ô ở cột 푖 đều được lát;
- [푖] là số cách lát đến cột 푖 mà ô (1,푖) chưa được lát và ô (2,푖) được lát;
- 표푤푛[푖] là số cách lát đến cột 푖 mà ô (1,푖) được lát và ô (2,푖) chưa được lát.
Ta có công thức tính [푖], [푖], 표푤푛[푖] như sau. Ban đầu khởi tạo các giá trị cho cột 0:
- [0] = 1;
- [0] = 표푤푛[0] = 0.
Sau đó là công thức truy hồi với 푖 = 1, 2, ,푛:
- [푖] = 2 × [푖 ― 1] + [푖 ― 1] + 표푤푛[푖 ― 1] + (푖 > 1 ? [푖 ― 2] :0);
- [푖] = [푖 ― 1] + 표푤푛[푖 ― 1];
- 표푤푛[푖] = [푖 ― 1] + [푖 ― 1].
Câu trả lời của bài toán là [푛].
Độ phức tạp thuật toán là (푛).
Subtask 4: 풌 = 
Ta gọi [푖][푗] = 푡 푒/ 푙푠푒 ứng với ô (푖,푗) có/không đánh dấu và gọi [푖], [푖], 표푤푛[푖] 
tương tự như trong các subtask trước.
Việc khởi tạo [0] = 1, [0] = 표푤푛[0] = 0 cũng giống như các subtask trước. Công 
thức truy hồi tính [푖], [푖], 표푤푛[푖] với 푖 = 1, 2, ,푛 bây giờ sẽ như sau.
Vì chỉ có tối đa một ô bị đánh dấu, nên xảy ra các trường hợp sau:
Trường hợp 1. Ô phía trên ở cột 푖 bị đánh dấu, còn ô phía dưới không bị đánh dấu 
( [1][푖] = 푡 푒, [2][푖] = 푙푠푒):
- [푖] = [푖 ― 1] + 표푤푛[푖 ― 1];
 De-Thi.com Bộ đề ôn luyện thi Học sinh giỏi Tin học 12 (Kèm đáp án) - De-Thi.com
- [푖] = 0;
- 표푤푛[푖] = [푖 ― 1].
Trường hợp 2. Ô phía trên ở cột 푖 không bị đánh dấu, còn ô phía dưới bị đánh dấu 
( [1][푖] = 푙푠푒, [2][푖] = 푡 푒):
- [푖] = [푖 ― 1] + [푖 ― 1];
- [푖] = [푖 ― 1];
- 표푤푛[푖] = 0.
Trường hợp 3. Hai ô ở cột 푖 không bị đánh dấu ( [1][푖] = 푙푠푒, [2][푖] = 푙푠푒):
-
 [푖] = 2 × [푖 ― 1] + (! [1][푖 ― 1] ? [푖 ― 1] :0) + (! [2][푖 ― 1] ? 표푤푛[푖 ― 1] :0) +
(푖 > 1 && ! [1][푖 ― 1] && ! [2][푖 ― 1] ? [푖 ― 2] :0);
- [푖] = [푖 ― 1] + (! [2][푖 ― 1] ? 표푤푛[푖 ― 1] :0);
- 표푤푛[푖] = [푖 ― 1] + (! [1][푖 ― 1] ? [푖 ― 1] :0).
Độ phức tạp thuật toán là (푛).
Subtask 5: Không có thêm ràng buộc nào
Thuật toán trong subtask 5 chỉ khác với subtask 4 ở công thức truy hồi như sau.
Trường hợp 1. Hai ô ở cột 푖 đều bị đánh dấu ( [1][푖] = 푡 푒, [2][푖] = 푡 푒):
 • [푖] = [푖 ― 1];
 • [푖] = 0;
 • 표푤푛[푖] = 0.
Trường hợp 2. Ô phía trên ở cột 푖 bị đánh dấu, còn ô phía dưới không bị đánh dấu 
( [1][푖] = 푡 푒, [2][푖] = 푙푠푒):
 • [푖] = [푖 ― 1] + (! [2][푖 ― 1] ? 표푤푛[푖 ― 1] :0);
 • [푖] = 0;
 • 표푤푛[푖] = [푖 ― 1].
Trường hợp 3. Ô phía trên ở cột 푖 không bị đánh dấu, còn ô phía dưới bị đánh dấu 
( [1][푖] = 푙푠푒, [2][푖] = 푡 푒):
 • [푖] = [푖 ― 1] + (! [1][푖 ― 1] ? [푖 ― 1] :0);
 • [푖] = [푖 ― 1];
 • 표푤푛[푖] = 0.
Trường hợp 4. Hai ô ở cột 푖 không bị đánh dấu ( [1][푖] = 푙푠푒, [2][푖] = 푙푠푒):
 • [푖] = 2 × [푖 ― 1] + (! [1][푖 ― 1] ? [푖 ― 1] :0) +
 (! [2][푖 ― 1] ? 표푤푛[푖 ― 1] :0) +
 (푖 > 1 && ! [1][푖 ― 1] && ! [2][푖 ― 1] ? [푖 ― 2] :0);
 • [푖] = [푖 ― 1] + (! [2][푖 ― 1] ? 표푤푛[푖 ― 1] :0);
 De-Thi.com