Bộ 12 Đề thi HSG môn Tin học THCS (Có đáp án)

 Bộ 12 Đề thi HSG môn Tin học THCS (Có đáp án) - DeThiTinHoc.net
 DeThiTinHoc.net Bộ 12 Đề thi HSG môn Tin học THCS (Có đáp án) - DeThiTinHoc.net
 ĐỀ SỐ 1
 SỞ GIÁO DỤC VÀ ĐÀO TẠO ĐỀ THI CHỌN HỌC SINH GIỎI 
 TỈNH QUẢNG NINH CẤP TỈNH THCS 
 Môn thi: TIN HỌC - Bảng A
 Thời gian: 150 phút, không kể thời gian giao đề
 TỔNG QUAN ĐỀ THI
 Tệp Tệp Tệp Bộ nhớ Thời gian
Bài Tên bài Điểm
 chương trình dữ liệu kết quả (MB) (giây)
 1 Oẳn tù tì rsp.* rsp.inp rsp.out 1024 1 6
 2 Khung tranh fra.* fra.inp fra.out 1024 1 6
 3 Dãy số bitonic bit.* bit.inp bit.out 1024 1 5
 4 Sửa đường roa.* roa.inp roa.out 1024 1 3
Dấu * được thay thế bởi cpp hoặc py tương ứng với ngôn ngữ lập trình C++ hoặc Python.
Hãy lập trình giải các bài toán sau:
Bài 1. Oẳn tù tì (6 điểm)
Trò chơi oẳn tù tì là một trò chơi dân gian phổ biến, thường chơi khi hai người đối diện 
nhau. Mỗi người sẽ đưa ra một trong ba hình dạng của bàn tay như sau:
 • Búa - thể hiện bằng cách cả bàn tay nắm chặt lại;
 • Kéo - thể hiện bằng cách ngón trỏ và ngón giữa tạo thành hình chữ V; 
 • Bao - thể hiện bằng cách cả bàn tay xòe ra.
Người chơi sẽ đồng loạt đưa ra một trong ba lựa chọn và so sánh với đối thủ. Nếu hai người 
chọn giống nhau thì hòa, còn nếu khác nhau thì sẽ có người thắng và người thua: Búa thắng 
Kéo (vì búa đập kéo), Kéo thắng Bao (vì kéo cắt bao), Bao thắng Búa (vì bao bọc búa).
Hai bạn An và Bình sẽ chơi n lần. Tuy nhiên, trước đó An đã tìm thấy một ghi chú cho biết 
Bình sẽ lựa chọn gì trong các lần chơi. Bạn hãy xác định số lần chơi tối đa mà An có thể 
thắng, nếu anh ta không được phép đưa ra cùng một lựa chọn trong hai lần liên tiếp.
Dữ liệu: Vào từ tệp rsp.inp. Dòng đầu tiên chứa một số nguyên n (1 ≤ n ≤ 105) là số lần chơi. 
Dòng thứ hai chứa hai chứa một xâu s độ dài n, trong đó kí tự (viết hoa) thứ i là ‘R’ hoặc ‘S’ 
hoặc ‘P’ biểu thị trong lần chơi thứ i, Bình ra Búa hoặc Kéo hoặc Bao tương ứng.
Kết quả: Ghi ra tệp rsp.out một số nguyên là số lần chơi tối đa mà An có thể thắng, nếu anh 
ta không được phép đưa ra cùng một lựa chọn trong hai lần liên tiếp.
Ví dụ:
 rsp.inp rsp.out
 5 4
 RPRRS
 DeThiTinHoc.net Bộ 12 Đề thi HSG môn Tin học THCS (Có đáp án) - DeThiTinHoc.net
Trong ví dụ trên, An có thể đưa ra PSPSR và anh ta thắng ở lần chơi thứ nhất, thứ hai, thứ ba, 
thứ năm và thua ở lần chơi thứ tư. 
Ràng buộc:
 • Có 30% số test ứng với 30% số điểm thỏa mãn: Xâu s không chứa hai kí tự liên tiếp 
 giống nhau;
 • 30% số test khác ứng với 30% số điểm thỏa mãn: 1 ≤ n ≤ 15;
 • 40% số test còn lại ứng với 40% số điểm: Không có thêm ràng buộc nào.
Bài 2. Khung tranh (6 điểm)
An có n thanh gỗ có chiều dài 1 và m thanh gỗ có chiều dài 2. Các thanh gỗ có thể được nối 
với nhau bằng cách xếp chúng thẳng hàng hoặc vuông góc.
An muốn lắp ráp một khung hình chữ nhật từ các thanh gỗ này, để sau đó anh có thể đặt một 
tờ giấy vào khung này và vẽ một phong cảnh thật đẹp tặng cho mẹ mình nhân dịp Ngày 
Quốc tế Phụ nữ.
Hơn nữa An nghĩ rằng diện tích khung hình chữ nhật càng lớn thì món quà sẽ càng có ý 
nghĩa. Vì vậy, điều quan trọng là anh ta phải xác định diện tích tối đa của khung hình chữ 
nhật có thể được ghép từ các thanh gỗ có sẵn.
Dữ liệu: Vào từ tệp fra.inp. Dòng đầu tiên chứa số nguyên n (0 ≤ n ≤ 109) là số thanh gỗ có 
chiều dài 1. Dòng thứ hai chứa số nguyên m (0 ≤ m ≤ 109) là số thanh gỗ có chiều dài 2. 
Kết quả: Ghi ra tệp fra.out một số nguyên là diện tích tối đa của khung hình chữ nhật có thể 
được tạo thành từ các thanh gỗ có sẵn. Nếu không thể tạo thành bất kỳ khung hình chữ nhật 
nào từ các thanh gỗ có sẵn thì in ra số 0.
Ví dụ:
 fra.inp fra.out
 5 1
 0
 4 6
 3
 3 0
 0
Trong ví dụ đầu tiên có 5 thanh gỗ chiều dài 1. Từ chúng, An có thể tạo một hình vuông có 
cạnh 1, diện tích của nó là 1 và sẽ còn lại 1 thanh gỗ.
Trong ví dụ thứ hai có 4 thanh gỗ chiều dài 1 và 3 thanh gỗ chiều dài 2. Từ chúng, An có thể 
tạo thành một hình chữ nhật có kích thước 2 x 3.
Trong ví dụ thứ ba có 3 thanh gỗ chiều dài bằng 1. Từ chúng, An không thể tạo thành hình 
chữ nhật.
 DeThiTinHoc.net Bộ 12 Đề thi HSG môn Tin học THCS (Có đáp án) - DeThiTinHoc.net
Ràng buộc:
 • Có 10% số test ứng với 10% số điểm thỏa mãn: n = 0 hoặc m = 0;
 • 20% số test khác ứng với 20% số điểm thỏa mãn: n,m ≤ 20;
 • 20% số test khác ứng với 20% số điểm thỏa mãn: n,m ≤ 1000;
 • 20% số test khác ứng với 20% số điểm thỏa mãn: n,m ≤ 5 × 105;
 • 30% số test còn lại ứng với 30% số điểm: Không có thêm ràng buộc nào.
Bài 3. Dãy số bitonic (5 điểm)
Dãy số 1, 2,, được gọi là dãy bitonic nếu 1  > với 1 ≤ 푖 ≤ . 
Chú ý rằng nếu 푖 = 1 thì 1 > 2 >  > và dãy là dãy giảm, còn nếu 푖 = thì 1 < 2
<  < và dãy là dãy tăng, còn nếu 1 < 푖 < thì các phần tử từ 1 đến 푖 tăng dần và 
các phần tử từ 푖 đến giảm dần.
Ví dụ các dãy sau là dãy bitonic:
 1;
 1,2,3,2;
 1,4,10;
 3,2. 
và các dãy sau không là dãy bitonic:
 1,1;
 2,1,3.
Cho dãy số 1, 2,, 푛. Hãy đếm số cặp (푙, ) sao cho 1 ≤ 푙 ≤ ≤ 푛 và dãy 푙, 푙+1,, là 
dãy bitonic.
Dữ liệu: Vào từ tệp bit.inp. Dòng đầu tiên chứa số nguyên 푛 (1 ≤ 푛 ≤ 3 × 105). Dòng thứ 
hai chứa 푛 số nguyên 1, 2,, 푛 (1 ≤ 푖 ≤ 푛).
Kết quả: Ghi ra tệp bit.out một số nguyên là số cặp (푙, ) sao cho 1 ≤ 푙 ≤ ≤ 푛 và dãy 푙,
 푙+1,, là dãy bitonic.
Ví dụ:
 bit.inp bit.out
 5 11
 1 1 2 3 1
 3 3
 1 1 1
Trong ví dụ đầu tiên, các cặp sau là thỏa mãn:
 1. (1,1) ứng với dãy 1;
 2. (2,2) ứng với dãy 2;
 3. (2,3) ứng với dãy 1,2;
 DeThiTinHoc.net Bộ 12 Đề thi HSG môn Tin học THCS (Có đáp án) - DeThiTinHoc.net
 4. (2,4) ứng với dãy 1,2,3;
 5. (2,5) ứng với dãy 1,2,3,1;
 6. (3,3) ứng với dãy 2;
 7. (3,4) ứng với dãy 2,3;
 8. (3,5) ứng với dãy 2,3,1;
 9. (4,4) ứng với dãy 3;
 10. (4,5) ứng với dãy 3,1;
 11. (5,5) ứng với dãy 1. 
Ràng buộc:
 • Có 40% số test ứng với 40% số điểm thỏa mãn: n ≤ 500;
 • 30% số test khác ứng với 30% số điểm thỏa mãn: n ≤ 5000;
 • 30% số test còn lại ứng với 30% số điểm: Không có thêm ràng buộc nào.
Bài 4. Sửa đường (3 điểm)
Ở thành phố của An mọi thứ đều tốt, ngoại trừ một con đường. Con đường này có 푛 cái hố 
xếp theo một hàng. Chúng ta đánh số các hố này từ 1 đến 푛 theo thứ tự từ đầu đến cuối con 
đường.
An thực sự muốn giúp thành phố của mình. Vì vậy, anh ta muốn sửa chữa ít nhất cái hố (có 
thể anh ta sửa chữa nhiều hơn) trên con đường này.
Thành phố có công ty sửa đường, công ty thứ 푖 cần 푖 đơn vị tiền để sửa chữa một đoạn 
đường có chứa các hố với chỉ số nhỏ nhất là 푙푖 và lớn nhất là 푖. Các công ty này rất tham 
lam, vì vậy nếu họ sửa chữa một đoạn đường có chứa một số hố đã được sửa, họ không giảm 
giá sửa chữa đoạn đường này.
Hãy xác định số tiền tối thiểu mà An sẽ cần để sửa chữa ít nhất cái hố.
Dữ liệu: Vào từ tệp roa.inp. Dòng đầu tiên chứa 3 số nguyên n, m, k (1 ≤ n ≤ 300; 1 ≤ m ≤ 
 5
10 ; 1 ≤ k ≤ n). Dòng thứ i trong m dòng tiếp theo chứa 3 số nguyên li, ri, ci (1 ≤ li ≤ ri ≤ n; 1 
 9
≤ ci ≤ 10 ) mô tả công ty thứ i cần ci đơn vị tiền để sửa chữa đoạn đường từ hố li đến ri.
Kết quả: Ghi ra tệp roa.out một số nguyên là số tiền tối thiểu mà An cần để sửa chữa ít nhất 
k cái hố. Trong trường hợp không thể sửa ít nhất k cái hố thì ghi ra số -1.
Ví dụ:
 roa.inp roa.out
 10 4 6 17
 7 9 11
 6 9 13
 7 7 7
 3 5 6
 10 7 1 2
 DeThiTinHoc.net Bộ 12 Đề thi HSG môn Tin học THCS (Có đáp án) - DeThiTinHoc.net
 3 4 15
 8 9 8
 5 6 8
 9 10 6
 1 4 2
 1 4 10
 8 10 13
 10 1 9 -1
 5 10 14
Trong ví dụ đầu tiên, phương án tối ưu là sử dụng công ty thứ nhất và thứ tư để sửa đường. 
Tổng cộng có 6 hố được sửa chữa là 3,4,5,7,8,9 với tổng chi phí là 11+ 6 = 17.
Trong ví dụ thứ hai, phương án tối ưu là sử dụng công ty thứ năm sửa đường và có 4 hố 
được sửa chữa là 1,2,3,4 (thỏa mãn tối thiểu 1 hố được sửa chữa) với chi phí là 2.
Trong ví dụ thứ ba chỉ có duy nhất một công ty sửa đường và sửa được 6 hố. Vì vậy không 
có phương án nào để sửa được ít nhất 9 hố.
Ràng buộc:
 • Có 10% số test ứng với 10% số điểm thỏa mãn: k = 1;
 • 15% số test khác ứng với 15% số điểm thỏa mãn: 1 ≤ li = ri ≤ n với mọi i = 1,2,,m;
 • 20% số test khác ứng với 20% số điểm thỏa mãn: 1 ≤ m ≤ 20;
 • 25% số test khác ứng với 25% số điểm thỏa mãn: 1 ≤ n ≤ 100 và 1 ≤ m ≤ 1000;
 • 30% số test còn lại ứng với 30% số điểm: Không có thêm ràng buộc nào.
 ----------HẾT----------
 DeThiTinHoc.net Bộ 12 Đề thi HSG môn Tin học THCS (Có đáp án) - DeThiTinHoc.net
 ĐÁP ÁN
Bài 1. Oẳn tù tì (6 điểm)
Phân bổ điểm
 • Có 30% số test ứng với 30% số điểm thỏa mãn: Xâu 푠 không chứa hai kí tự liên tiếp 
 giống nhau;
 • 30% số test khác ứng với 30% số điểm thỏa mãn: 1 ≤ 푛 ≤ 15;
 • 40% số test còn lại ứng với 40% số điểm: Không có thêm ràng buộc nào.
Cấu hình bài thi
Hướng dẫn giải
Subtask 1 (30%): Xâu 풔 không chứa hai kí tự liên tiếp giống nhau
Nếu ta chưa để ý đến điều kiện An không được phép đưa ra hai lựa chọn liên tiếp giống nhau 
thì trong mỗi lần chơi, An luôn có thể đưa ra lựa chọn để dành phần thắng.
Do xâu 푠 không chứa hai kí tự liên tiếp giống nhau, tức là Bình không đưa ra hai lựa chọn 
liên tiếp nào giống nhau, nên hai lựa chọn thắng liên tiếp của An cũng không giống nhau. Vì 
vậy số lần chơi tối đa mà An có thể thắng là 푛.
Độ phức tạp thuật toán là (푛).
Subtask 2 (30%): ≤ 풏 ≤ 
Ta duyệt mọi cách chơi của An. Với mỗi cách chơi, ta tính số lần thắng và cập nhật số lần 
thắng nhiều nhất.
Độ phức tạp thuật toán là (3푛).
Subtask 3 (40%): Không có thêm ràng buộc nào
Hãy xem xét một đoạn liên tục các lựa chọn giống nhau của Bình. Giả sử đoạn có độ dài . 
An không thể đưa ra hai lựa chọn liên tiếp giống nhau, vì vậy trong đoạn này chắc chắn An 
không thể thắng hai lần liên tiếp. Cách tốt nhất là An thắng lần thứ nhất, thứ ba, thứ năm, , 
tức là các lần chơi lẻ và số lần thắng tối đa của An sẽ là .
 ⌈2⌉
 DeThiTinHoc.net Bộ 12 Đề thi HSG môn Tin học THCS (Có đáp án) - DeThiTinHoc.net
Tổng quát, ta sẽ chia xâu 푠 thành các đoạn kí tự giống nhau. Giả sử có đoạn và mỗi đoạn 
có độ dài . Áp dụng điều trên cho mọi đoạn, ta có số lần thắng tối đa của An sẽ 1 + 2
 푖 ⌈ 2 ⌉ ⌈ 2 ⌉
+ + . 
 ⌈ 2 ⌉
Độ phức tạp thuật toán là (푛).
Bài 2. Khung tranh (6 điểm)
Phân bổ điểm
 • Có 10% số test ứng với 10% số điểm thỏa mãn: 푛 = 0 hoặc = 0;
 • 20% số test khác ứng với 20% số điểm thỏa mãn: 푛, ≤ 20;
 • 20% số test khác ứng với 20% số điểm thỏa mãn: 푛, ≤ 1000;
 • 20% số test khác ứng với 20% số điểm thỏa mãn: 푛, ≤ 5 × 105;
 • 30% số test còn lại ứng với 30% số điểm: Không có thêm ràng buộc nào.
Cấu hình bài thi
Hướng dẫn giải
Subtask 1 (10%): 풏 = hoặc = 
Gọi , là độ dài hai cạnh của hình chữ nhật. 
Trường hợp 푛 = 0 (không có các thanh độ dài 1): ta phân bổ đều các thanh độ dài 2 cho 4 
cạnh của khung, tức là = = × 2. Nếu số que độ dài 2 còn lại lớn hơn hoặc bằng 2, 
 ⌊ 4 ⌋
tức là mod 4 ≥ 2, thì tăng độ dài cạnh lên 2.
Trường hợp = 0 (không có các thanh độ dài 2): ta phân bổ đều các thanh độ dài 1 cho 4 
 푛
cạnh của khung, tức là = = . Nếu số que độ dài 1 còn lại lớn hơn hoặc bằng 2, tức là 
 ⌊4⌋
푛 mod 4 ≥ 2, thì tăng độ dài cạnh lên 1.
Diện tích khung hình chữ nhật lớn nhất sẽ bằng × .
Độ phức tạp thuật toán là (1).
 DeThiTinHoc.net Bộ 12 Đề thi HSG môn Tin học THCS (Có đáp án) - DeThiTinHoc.net
Subtask 2 (20%): 풏, ≤ và Subtask 3 (20%): 풏, ≤ 
Nhận thấy rằng giá trị lớn nhất của một cạnh hình chữ nhật là 푛 2 .
 ⌊ 2 ⌋
 푛 2 
Ta duyệt mọi khả năng kích thước × của hình chữ nhật 1 ≤ ≤ ≤ . Với mỗi 
 ⌊ 2 ⌋
hình chữ nhật kích thước × , ta kiểm tra xem có thể tạo được từ các thanh có sẵn hay 
không. Điều kiện là chu vi của hình chữ nhật 2( + ) phải nhỏ hơn hoặc bằng tổng chiều 
dài của tất cả các thanh 푛 + 2 . Hơn nữa mỗi cạnh hình chữ nhật có độ dài lẻ phải chứa ít 
nhất một thanh có độ dài 1, tức là số cạnh độ dài lẻ của hình chữ nhật (số các số lẻ trong các 
số , , , ) phải nhỏ hơn hoặc bằng 푛.
long long ans = 0;
int mx = (n + 2LL * m) / 2;
for (int a = 1; a <= mx; a++)
 for (int b = a; b <= mx - a; b++)
 if (2 * (a % 2 + b % 2) <= n)
 ans = max(ans, 1LL * a * b);
cout << ans << "\n";
 푛 2 
Độ phức tạp thuật toán là ( 2) với = .
 ⌊ 2 ⌋
Subtask 4 (20%): 풏, ≤ × 
 푛 2 
Trong subtask này, ta chỉ duyệt độ dài của một cạnh hình chữ nhật 1 ≤ ≤ . Khi 
 ⌊ 2 ⌋
đó ta sẽ có hai cạnh có độ dài là . Hãy kiểm tra điều kiện 푛 không nhỏ hơn 2( mod 2), 
nghĩa là nếu lẻ thì sẽ có ít nhất hai thanh có độ dài là 1.
Bây giờ chúng ta xác định giá trị thích hợp lớn nhất của với một giá trị cho trước. Nhận 
 푛 2 2 푛 2 2 
thấy rằng ≤ . Đầu tiên ta giả sử = . Nếu 푛 < 2( mod 2 + mod 2), 
 ⌊ 2 ⌋ ⌊ 2 ⌋
tức là 푛 nhỏ hơn số các số lẻ trong các giá trị , , , , thì chúng ta sẽ không có đủ các thanh 
độ dài 1 để xếp thành các cạnh độ dài lẻ trong các cạnh , , , . Nhưng trước đó chúng ta đã 
xếp được các thanh có độ dài lẻ trong các thanh và , vì vậy điều này xảy ra với là số lẻ. 
Tức là không đủ thanh độ dài 1 để xếp cạnh độ dài lẻ và , vì vậy cần giảm giá trị của đi 
1. Theo cách này, chúng ta xác định giá trị lớn nhất của cạnh thứ hai ứng với cạnh đã 
chọn trước đó. Trong quá trình duyệt, lưu giá trị lớn nhất của diện tích hình chữ nhật × .
long long ans = 0;
int mx = (n + 2LL * m) / 2;
for (int a = 1; a <= mx; a++) {
 if (n < 2 * (a % 2))
 continue;
 DeThiTinHoc.net Bộ 12 Đề thi HSG môn Tin học THCS (Có đáp án) - DeThiTinHoc.net
 int b = (mx - a);
 if (n < 2 * (a % 2 + b % 2))
 b--;
 ans = max(ans, 1LL * a * b);
}
cout << ans << "\n";
 푛 2 
Độ phức tạp thuật toán là .
 ⌊ 2 ⌋
Subtask 5 (30%): Không có thêm ràng buộc nào
Chú ý rằng trong tất cả các hình chữ nhật có cùng chu vi, diện tích lớn nhất sẽ là diện tích 
của hình vuông hoặc hình chữ nhật có các cạnh chênh lệch nhau 1. Thật vậy, giả sử hình chữ 
nhật có các cạnh là và , trong đó + 1 < . Xét một hình chữ nhật có các cạnh + 1 và 
 ― 1 có cùng chu vi. Diện tích của nó sẽ bằng + ― ― 1, tức là lớn hơn diện tích 
của hình chữ nhật ban đầu.
 1
Do đó để tối ưu, ta chọn của chu vi lớn nhất có thể làm giá trị của một trong các cạnh. Để 
 4
 푛 2 
thực hiện điều này, ta lấy giá trị làm giá trị của cạnh nhỏ nhất và chọn giá trị phù 
 ⌊ 4 ⌋
hợp lớn nhất cho , như trong thuật toán trước. Nhưng nếu là số lẻ, thì để tạo thành các 
cạnh có độ dài , chúng ta sẽ cần ít nhất 2 thanh độ dài 1 và chúng ta có thể không có đủ số 
thanh có độ dài 1 để đạt được giá trị lớn nhất có thể của . Do đó, cần xét cả giá trị chẵn và 
 푛 2 푛 2 
lẻ của , nghĩa là cần lấy không chỉ = mà còn lấy giá trị ―1, vì một trong 
 ⌊ 4 ⌋ ⌊ 4 ⌋
hai số đó sẽ là số chẵn. Với mỗi giá trị này, ta chọn một giá trị thích hợp và tìm giá trị 
lớn nhất của × .
long long ans = 0;
int mx = (n + 2LL * m) / 2, side = (n + 2LL * m) / 4;
for (int a = side - 1; a <= side; a++) {
 if (n < 2 * (a % 2))
 continue;
 int b = mx - a;
 if (n < 2 * (a % 2 + b % 2))
 b--;
 ans = max(ans, 1LL * a * b);
}
cout << ans << "\n";
}
Độ phức tạp thuật toán là (1).
Bài 3. Dãy số bitonic (5 điểm)
 DeThiTinHoc.net