Tổng hợp 11 Đề thi học sinh giỏi Tin học THCS (Kèm đáp án)

Nội dung text: Tổng hợp 11 Đề thi học sinh giỏi Tin học THCS (Kèm đáp án)

1. Tổng hợp 11 Đề thi học sinh giỏi Tin học THCS (Kèm đáp án) - DeThi.edu.vn Phân bổ điểm • Có 40% số test ứng với 40% số điểm thỏa mãn: 푛 ≤ 500; • 30% số test khác ứng với 30% số điểm thỏa mã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. Cấu hình bài thi Hướng dẫn giải Subtask 1 (40%): 풏 ≤ Chúng ta hãy xem xét tất cả những cặp (푙, ) sao cho 1 ≤ 푙 ≤ ≤ 푛 và kiểm tra dãy 푙, 푙+1 , , có là dãy bitonic hay không. Độ phức tạp thuật toán (푛3). Subtask 2 (30%): 풏 ≤ Lưu ý rằng với mọi 푙 < sao cho dãy các phần tử từ chỉ số 푙 đến là bitonic, thì dãy các phần tử từ chỉ số 푙 đến ― 1 cũng là bitonic. Điều này có nghĩa là chúng ta có thể cố định chỉ số bên trái 푙 và tìm chỉ số bên phải lớn nhất sao cho dãy các phần tử từ chỉ số 푙 đến là bitonic. Khi đó số lượng dãy bitonic có phần tử bắt đầu ở chỉ số 푙 là ― 푙 + 1. Duyệt mọi chỉ số 푙 = 1, 2, ,푛, rồi tính tổng các dãy bitonic ta sẽ tìm được câu trả lời của bài toán. Độ phức tạp thuật toán là (푛2). Subtask 3 (30%): Không có thêm ràng buộc nào Gọi [푖] là số phần tử mảng tăng liên tiếp bắt đầu từ phần tử chỉ số 푖. Ta có công thức tính [푖] như sau: • [푛] = 1; • Với mọi 푖 chạy lần lượt từ 푛 ― 1 về 1: [푖 + 1] + 1 nếu < [푖] = 푖 푖+1 1 nếu 푖 ≥ 푖+1 Tương tự, gọi 표푤푛[푖] là số phần tử mảng giảm liên tiếp bắt đầu từ phần tử chỉ số 푖. Ta có DeThi.edu.vn
2. Tổng hợp 11 Đề thi học sinh giỏi Tin học THCS (Kèm đáp án) - DeThi.edu.vn công thức tính 표푤푛[푖] như sau: • 표푤푛[푛] = 1; • Với mọi 푖 chạy lần lượt từ 푛 ― 1 về 1: 표푤푛[푖 + 1] + 1 nếu > 표푤푛[푖] = 푖 푖+1 1 nếu 푖 ≤ 푖+1 Nhận thấy rằng độ dài dãy bitonic dài nhất bắt đầu từ chỉ số 푖 là [푖] + 표푤푛[푖 + [푖] ― 1] ―1 và nó cũng là số dãy bitonic có phần tử đầu ở chỉ số 푖. Vì vậy số dãy bitonic cần tìm là: 푛 ∑푖=1 [푖] + 표푤푛[푖 + [푖] ― 1] ― 1 Độ phức tạp thuật toán là (푛). Bài 4. Sửa đường (3 điểm) Phân bổ điểm • Có 10% số test ứng với 10% số điểm thỏa mãn: = 1; • 15% số test khác ứng với 15% số điểm thỏa mãn: 1 ≤ 푙푖 = 푖 ≤ 푛 với mọi 푖 = 1, 2, , ; • 20% số test khác ứng với 20% số điểm thỏa mãn: 1 ≤ ≤ 20; • 25% số test khác ứng với 25% số điểm thỏa mãn: 1 ≤ 푛 ≤ 100 và 1 ≤ ≤ 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. Cấu hình bài thi Hướng dẫn giải Subtask 1 (10%): 풌 = Chú ý rằng công ty 푖 luôn sửa chữa một đoạn đường từ hố 푙푖 đến 푖 với chi phí 푖. Mặt khác, do = 1, tức là sửa chữa ít nhất một cái hố, nên câu trả lời sẽ là min ( 푖). 푖 = 1,2, , Subtask 2 (15%): ≤ 풍풊 = 풓풊 ≤ 풏 với mọi 풊 = , , , DeThi.edu.vn
3. Tổng hợp 11 Đề thi học sinh giỏi Tin học THCS (Kèm đáp án) - DeThi.edu.vn Do 푙푖 = 푖, tức là mỗi công ty chỉ sửa chữa đúng 1 cái hố, nên ta sẽ sắp xếp các công ty theo chi phí sửa chữa 푖 tăng dần. Chú ý rằng, nếu có nhiều công ty cùng sửa chữa một cái hố thì ta chỉ giữ lại một công ty có chi phí sửa chữa nhỏ nhất trong số các công ty đó. Gọi ’ là số công ty cần giữ lại. Rõ ràng nếu ≤ ′ thì ta sẽ chọn công ty có chi phí sửa chữa rẻ nhất, tức là công ty đầu tiên sau khi sắp xếp và loại bỏ. Vậy câu trả lời sẽ là 1 + 2 + + . Ngược lại, nếu > ′ thì không thể sửa ít nhất cái hố được và cần ghi ra câu trả lời là ―1. Độ phức tạp thuật toán ( .log2 ). Subtask 3 (20%): ≤ ≤ Ta duyệt mọi tập con của công ty. Mỗi tập con sẽ tương ứng với một cách chọn các công ty để sửa chữa. Với mỗi cách chọn các công ty cần sửa chữa, ta kiểm tra xem có sửa chữa được ít nhất cái hố hay không. Trong quá trình duyệt, lưu lại cách chọn thỏa mãn với tổng chi phí nhỏ nhất. Độ phức tạp thuật toán (2 . ). Subtask 4 (25%): ≤ 풏 ≤ và ≤ ≤ Gọi 표푠푡[푖][푗] là chi phí nhỏ nhất để sửa các hố từ 푖 đến 푗. Ban đầu ta gán 표푠푡[푖][푗] = +∞. Sau đó với mỗi công ty , ta sẽ cập nhật 표푠푡[푖][푗] = min( 표푠푡[푖][푗], ) với mọi 푙 ≤ 푖 ≤ 푗 ≤ . Tiếp theo, gọi [푖][푗] là chi phí nhỏ nhất để sửa chữa ít nhất 푗 hố (푗 = 0, 1, ,푛) trong các hố từ 1 đến 푖 (푖 = 0, 1, ,푛). Ban đầu ta khởi tạo [0][0] = 0 và [푖][0] = 0, [0][푖] = +∞ với mọi 푖 = 1, 2, ,푛. Bây giờ ta sẽ lập công thức truy hồi tính [푖][푗] với 푖 = 1, 2, ,푛 và 푗 = 1, 2, ,푛. Xét hai trường hợp sau: Trường hợp 1. 푖 < 푗: Hiển nhiên [푖][푗] = +∞. Trường hợp 2. 푖 ≥ 푗: Nếu hố 푖 không sửa chữa thì chi phí sửa chữa sẽ là [푖 ― 1][푗]. Còn nếu hố 푖 được sửa chữa thì chi phí sửa chữa sẽ là [푖 ― 푙][푗 ― 푙] + 표푠푡[푖 ― 푙 + 1][푖] với mọi 푙 = 1, 2,...,푗. Vì vậy: [푖][푗] = min [푖 ― 1][푗], min ( [푖 ― 푙][푗 ― 푙] + 표푠푡[푖 ― 푙 + 1][푖]) 푙 = 1, 2,...,푗 Cuối cùng, nếu [푛][ ] = +∞ thì không thể sửa ít nhất cái hố và ghi ra số ―1. Ngược lại, chi phí để sửa ít nhất cái hố là [푛][ ]. Độ phức tạp thuật toán ( .푛2 + 푛3). Subtask 5 (30%): Không có thêm ràng buộc nào Ta sẽ cải tiến thuật toán trong subtask 4. Để ý trong công thức tính [푖][푗], ta cần có chi phí tối thiểu 표푠푡[푖 ― 푙 + 1][푖] để sửa chữa từ hố 푖 ― 푙 + 1 đến hố 푖. Thực tế ta chỉ cần xem xét các công ty mà đoạn sửa chữa phủ các hố này và có hố trái nhất tại 푖 ― 푙 + 1, vì các công ty DeThi.edu.vn
4. Tổng hợp 11 Đề thi học sinh giỏi Tin học THCS (Kèm đáp án) - DeThi.edu.vn có đoạn sửa chữa phủ đoạn này và có hố trái nhất nhỏ hơn đã được xem xét ở các bước trước. Bây giờ ta sẽ gọi 표푠푡[푖][푗] là chi phí nhỏ nhất để sửa các hố từ 푖 đến 푗 với các công ty có hố sửa chữa trái nhất là 푖. Vì vậy với mỗi công ty , ta sẽ cập nhật 표푠푡[푙 ][푗] = min ( 표푠푡[푙 ][푗], ) với mọi 푙 ≤ 푗 ≤ . Độ phức tạp thuật toán ( .푛 + 푛3). DeThi.edu.vn
5. Tổng hợp 11 Đề thi học sinh giỏi Tin học THCS (Kèm đáp án) - DeThi.edu.vn ĐỀ SỐ 2 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 B 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 chương Điểm dữ liệu kết quả (MB) (giây) trình 1 Oẳn tù tì rsp.* rsp.inp rsp.out 1024 1 6 2 Ước chung đặc biệt div.* div.inp div.out 1024 1 6 3 Khung tranh fra.* fra.inp fra.out 1024 1 5 4 Dãy số bitonic bit.* bit.inp bit.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 푛 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 푛 (1 ≤ 푛 ≤ 105) là số lần chơi. Dòng thứ hai chứa hai chứa một xâu 푠 độ dài 푛, trong đó kí tự (viết hoa) thứ 푖 là ‘R’ hoặc ‘S’ hoặc ‘P’ biểu thị trong lần chơi thứ 푖, 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. DeThi.edu.vn
6. Tổng hợp 11 Đề thi học sinh giỏi Tin học THCS (Kèm đáp án) - DeThi.edu.vn Ví dụ: rsp.inp rsp.out 5 4 RPRRS 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. Ước chung đặc biệt (6 điểm) Cho 2 số nguyên dương a, b. Hãy tìm một số nguyên dương d là ước của a và d cũng là ước của b, sao cho tổng các chữ số của d lớn nhất. Trong trường hợp có nhiều số d thoả mãn thì đưa ra số lớn nhất trong các số đó. Dữ liệu: Vào từ tệp div.inp gồm 2 số nguyên a,b (1 ≤ a,b ≤ 109). Kết quả: Ghi ra tệp div.out số nguyên dương d cần tìm. div.inp div.out 36 24 6 720 960 48 Ràng buộc: • Có 40% số test ứng với 40% số điểm thỏa mãn: 1 ≤ a,b ≤ 103; • 30% số test khác ứng với 30% số điểm thỏa mãn: 1 ≤ a,b ≤ 106; • 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. Khung tranh (5 đ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. DeThi.edu.vn
7. Tổng hợp 11 Đề thi học sinh giỏi Tin học THCS (Kèm đáp án) - DeThi.edu.vn 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 × 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. 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 4. Dãy số bitonic (3 đ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. DeThi.edu.vn
8. Tổng hợp 11 Đề thi học sinh giỏi Tin học THCS (Kèm đáp án) - DeThi.edu.vn 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; 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. ----------HẾT---------- DeThi.edu.vn
9. Tổng hợp 11 Đề thi học sinh giỏi Tin học THCS (Kèm đáp án) - DeThi.edu.vn ĐÁ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⌉ DeThi.edu.vn
10. Tổng hợp 11 Đề thi học sinh giỏi Tin học THCS (Kèm đáp án) - DeThi.edu.vn 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. Ước chung đặc biệt (6 điểm) Phân bổ điểm • Có 40% số test ứng với 40% số điểm thỏa mãn: 1 ≤ , ≤ 103; • 30% số test khác ứng với 30% số điểm thỏa mãn: 1 ≤ , ≤ 106; • 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 (40%): ≤ , ≤ và Subtask 2 (30%): ≤ , ≤ Ta duyệt các số từ 1 đến min( , ), kiểm tra có là ước của cả và hay không và lưu lại số có tổng các chữ số lớn nhất. Độ phức tạp thuật toán là (min( , )). Subtask 3 (30%): Không có thêm ràng buộc nào Gọi là ước chung lớn nhất của và . Nhận thấy rằng nếu là ước chung của và thì sẽ là ước của . Vì vậy ta tìm các ước của và lưu lại ước có tổng các chữ số lớn nhất. Độ phức tạp thuật toán là min( , ) . DeThi.edu.vn