Đề thi chọn học sinh giỏi môn Tin học Lớp 9 - Năm học 2018-2019 (Bản đẹp)

Nội dung text: Đề thi chọn học sinh giỏi môn Tin học Lớp 9 - Năm học 2018-2019 (Bản đẹp)

1. HỘI THI TIN HỌC TRẺ VĨNH PHÚC ĐỀ THI THỰC HÀNH BẢNG B – THCS Thời gian làm bài: 150 phút LẦN THỨ XIII - 2018 (không kể thời gian phát đề) Đề thi gồm có 2 trang Tổng quan về đề thi: Thời Tên bài Tên chương trình Dữ liệu vào Dữ liệu ra Điểm gian Ghép cặp pairing.* pairing.inp pairing.out 1s 30 Lập trình program.* program.inp program.out 1s 35 Phần thưởng bonus.* bonus.inp bonus.out 1s 35 Lưu ý: Thí sinh thay * trong tên chương trình là PAS hoặc CPP tuỳ theo ngôn ngữ lập trình thí sinh sử dụng là Pascal hay C/C++. Lập chương trình giải các bài toán sau: Bài 1: Ghép cặp Tỉnh Đoàn tổ chức học khiêu vũ cho các bạn học sinh. Để tăng hiệu quả học tập cần ghép đôi bạn tập và cố định cách ghép này cho tất cả các buổi học. Tỉnh Đoàn đã lấy ý kiến từng học sinh và thu được thống kê: có a bạn nam muốn được tập cùng bạn nam, b bạn nam muốn được tập cùng bạn nữ, c bạn nữ muốn tập cùng bạn nữ, d bạn nữ muốn tập cùng bạn nam. Tỉnh Đoàn muốn tối thiểu hóa số lượng học sinh không được ghép đôi đúng mong muốn. Hãy xác định số lượng nhỏ nhất đó. Yêu cầu: Tìm số lượng học sinh (nhỏ nhất có thể) không được ghép đôi đúng mong muốn. Dữ liệu: Một dòng duy nhất ghi bốn số nguyên a, b, c, d các nhau bởi ít nhất một dấu cách. Dữ liệu đảm bảo kết quả của a + b + c + d là một số chẵn. Kết quả: Ghi một số nguyên duy nhất là kết quả tìm được. Ràng buộc: 1 ≤ a, b, c, d ≤ 105 20% số điểm của bài có 1 ≤ a, b, c, d ≤ 10 30% số điểm của bài có 1 ≤ a, b, c, d ≤ 100 Ví dụ: pairing.inp pairing.out 1 1 1 1 2 Bài 2: Lập trình Hoàng Anh chuẩn bị tham gia kỳ thi lập trình do Tỉnh Đoàn tổ chức. Mặc dù Hoàng Anh đã giải được nhiều bài tập nhưng vẫn còn một bài chưa được giải quyết và Hoàng Anh quyết định nhờ bạn trợ giúp. Bạn nhận được chuỗi S (chỉ bao gồm các chữ cái in thường trong tiếng Anh) và Q truy vấn. Với mỗi truy vấn, bạn được cấp bốn số nguyên dương A, B, C và D. Gọi xâu X là xâu bao gồm các chữ cái từ vị trí A đến vị trí B trong S, gọi xâu Y là xâu bao gồm các chữ cái từ vị trí C đến vị trí D trong S. Yêu cầu: Với mỗi truy vấn, bạn phải trả lời nếu có thể bằng cách nào đó sắp xếp các chữ cái trong xâu Y được xâu X thì ghi ra YES, ngược lại ghi NO Trang | 1
2. Dữ liệu: Dòng đầu ghi chuỗi S, (1 ≤ |S| ≤ 50 000) với |S| được hiểu là số ký tự trong chuỗi S. Dòng thứ hai ghi số nguyên Q, (1 ≤ Q ≤ 50 000) Với mỗi dòng trong Q dòng tiếp theo, ghi bốn số nguyên A, B, C, D, (1 ≤ A ≤ B ≤ |S| và 1 ≤ C ≤ D ≤ |S|) Kết quả: Ứng với Q truy vấn, in ra Q dòng, mỗi dòng ghi YES hoặc NO Ví dụ: program.inp program.out alohaahola YES 3 YES 1 2 9 10 NO 1 5 6 10 1 3 4 8 Bài 3: Phần thưởng Hoàng Anh là người chiến thắng trong một cuộc thi “Tìm hiểu Kiến thức Vũ trụ” và được nhận các phần thưởng do Tỉnh Đoàn trao thưởng. Các phần thưởng được bố trí trên một bảng hình vuông n x n có dạng một lưới ô vuông kích thước đơn vị. Các dòng của bảng được đánh số từ 1 đến n, từ trên xuống dưới và các cột của bảng được đánh số từ 1 đến n, từ trái qua phải. Ô nằm trên giao của dòng i và cột j được gọi là ô (i,j) và trên ô đó chứa một món quà có giá trị là a[i,j] (1 ≤ i,j ≤ n) Đề nhận phần thưởng, Hoàng Anh được phép chọn một hình vuông kích thước k x k chiếm trọn trong một số ô của bảng và nhận tất cả các phần quà có trong các ô nằm trong hình vuông đó. Yêu cầu: Xác định tổng giá trị lớn nhất của món quà mà Hoàng Anh có thể nhận được. Dữ liệu: Dòng đầu: Ghi hai số nguyên n và k cách nhau ít nhất một dấu cách, (n/3 ≤ k ≤ n) Dòng thứ i trong số n dòng tiếp theo, ghi n số nguyên dương, số thứ j là a[i,j], a[i,j] ≤ 105 Kết quả: Một số nguyên duy nhất là kết quả tìm được. Ràng buộc: 1 ≤ n ≤ 1000 50% số điểm có 1 ≤ n ≤ 100 Ví dụ: bonus.inp bonus.out 4 3 86 1 9 1 1 9 9 9 9 1 9 9 9 1 9 9 14 HẾT Thí sinh không sử dụng tài liệu để làm bài Cán bộ coi thi không giải thích gì thêm Trang | 2