Đề thi học sinh giỏi môn Tin lớp 12 - Sở GD&ĐT Thanh hóa

Chia sẻ: Phung Tuyet | Ngày: | Loại File: PDF | Số trang:8

Thêm vào BST

Báo xấu

175
lượt xem 25
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Cùng tham khảo đề thi học sinh giỏi môn Tin học lớp 12 giúp các em ôn tập lại các kiến thức đã học, đánh giá năng lực làm bài của mình và chuẩn bị kì thi sắp tới được tốt hơn với số điểm cao như mong muốn.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Đề thi học sinh giỏi môn Tin lớp 12 - Sở GD&ĐT Thanh hóa

SỞ GIÁO DỤC VÀ ĐÀO TẠO KỲ THI HỌC SINH GIỎI TỈNH THANH HÓA Năm học: 2010 – 2011 Môn thi: TIN HỌC ĐỀ CHÍNH THỨC Lớp 12 THPT Số báo danh Ngày thi: 24/3/2011 ………… Thời gian: 180 phút (không kể thời gian giao đề) Đề thi có 05 câu, gồm 2 trang. Tổng quan bài thi: Tên bài File chương trình File dữ liệu vào File kết quả Bài 1 Cấp số cộng BAI1.PAS BAI1.INP BAI1.OUT Bài 2 Biến đổi xâu BAI2.PAS BAI2.INP BAI2.OUT Bài 3 Chuẩn hóa văn bản BAI3.PAS BAI3.INP BAI3.OUT Bài 4 Chia đoạn một dãy số BAI4.PAS BAI4.INP BAI4.OUT Bài 5 Chia lưới BAI5.PAS BAI5.INP BAI5.OUT Hãy lập trình giải các bài toán sau: Bài 1: (5 điểm) Cấp số cộng Cho dãy gồm n số nguyên a1, a2,..., an. Yêu cầu: cho biết dãy số trên có lập thành cấp số cộng hay không? Dữ liệu vào: từ file BAI1.INP gồm: - Dòng đầu tiên ghi số n. - Dòng tiếp theo lần lượt ghi n số a1, a2,..., an. Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách trống. Kết quả: ghi ra file BAI1.OUT như sau: - Số 1 - Nếu dãy số là cấp số cộng. - Số 0 - Nếu dãy số không phải là cấp số cộng. Ví dụ: BAI1.INP BAI1.OUT BAI1.INP BAI1.OUT 456 1 -3 4 5 0 Bài 2 (4 điểm) Biến đổi xâu Cho trước một xâu nhị phân có độ dài bất kỳ. Cần biến đổi xâu nhị phân này về dạng toàn số 0. Các phép biến đổi chỉ có thể là một trong các loại sau: - Biến đổi xâu con 11 thành 00. - Biến đổi xâu con 010 thành 000. Hãy chỉ ra một cách biến đổi xâu đã cho thành xâu có toàn 0. Dữ liệu vào: từ file BAI2.INP xâu nhị phân độ dài bất kỳ. Kết quả: ghi ra file BAI2.OUT như sau: - Dòng đầu tiên chứa xâu ban đầu. - Sau đó mỗi dòng là một xâu tiếp theo sau một phép biến đổi. Xâu cuối cùng là xâu toàn 0. - Nếu không biến đổi được thì ghi "Khong the bien doi duoc". Ví dụ: BAI2.INP BAI2.OUT 11010011 11010011 BAI2.INP BAI2.OUT 11010000 10101101 Khong the bien doi duoc 00010000 00000000 Bài 3 (4 điểm) Chuẩn hoá văn bản Một văn bản được gọi là văn bản chuẩn nếu: - Hai từ liền nhau có duy nhất một dấu cách trống. - Dấu ngắt câu (dấu chấm, dấu phẩy, dấu chấm phẩy, dấu chấm hỏi, dấu chấm than) được đặt sát vào từ ngay trước nó, sau đó mới đến dấu cách trống. - Dấu mở ngoặc đặt sát vào phía bên trái của từ bắt đầu mở ngoặc. Trang 1/2 - Dấu đóng ngoặc đặt sát bên phải từ cuối cùng được đóng ngoặc.
Hãy viết chương trình để kiểm tra và đưa một đoạn văn bản về dạng văn bản chuẩn. Dữ liệu vào: từ file BAI3.INP Kết quả: ghi ra file BAI3.OUT văn bản đã được chuẩn hoá. ví dụ: BAI3.INP BAI3.OUT Thấy rét u tôi bọc lại mền Thấy rét u tôi bọc lại mền Cô nàng cất rượu ủ thêm men . Cô nàng cất rượu ủ thêm men. ( trích Hoa với rượu – Nguyễn Bính) ( trích Hoa với rượu – Nguyễn Bính) Bài 4 (4 điểm) Chia đoạn một dãy số Cho dãy số tự nhiên a1, a2,..., an. Hãy tìm cách chia dãy số trên thành nhiều đoạn nhất sao cho tổng các số trong tất cả các đoạn con đều bằng nhau. Dữ liệu vào: từ file BAI4.INP gồm: - Dòng đầu ghi số n. - Các dòng còn lại ghi các số a1, a2,..., an. Các số trên cùng một dòng cách nhau ít nhất một dấu cách trống. Kết quả: ghi ra file BAI4.OUT, gồm K+1 dòng (K là số đoạn chia được nhiều nhất) như sau: - Dòng đầu ghi hai số K và S (S là tổng giá trị của một đoạn). - K dòng còn lại mỗi dòng ghi các số của mỗi đoạn chia được. Các số trên cùng một dòng cách nhau ít nhất một dấu cách trống. Ví dụ: BAI4.INP BAI4.OUT 6 38 351780 35 17 80 Bài 5: ( 3điểm) Chia lưới Cho lưới M x N (M, N
Së Gi¸o dôc vμ ®μo t¹o Kú thi häc sinh giái tØnh thanh ho¸ Năm học: 2010-2011 Môn thi: Tin học Lớp 12 THPT Ngày thi: 24/03/2011 HƯỚNG DẪN CHẤM Bài 1: 5 điểm Test File dữ liệu vào File kết quả ra Điểm 1 bai1_1.inp bai1_1.out 1 điểm 2 bai1_2.inp bai1_2.out 1 điểm 3 bai1_3.inp bai1_3.out 1 điểm 4 bai1_4.inp bai1_4.out 1 điểm 5 bai1_5.inp bai1_5.out 1 điểm Bài 2: 4 điểm Test File dữ liệu vào File kết quả ra Điểm 1 bai2_1.inp bai2_1.out 2 điểm 2 bai2_2.inp bai2_2.out 1 điểm 3 bai2_3.inp bai2_3.out 1 điểm Bài 3: 4 điểm Test File dữ liệu vào File kết quả ra Điểm 1 bai3_1.in bai3_1.out 2 điểm 2 bai3_2.in bai3_2.out 1 điểm 3 bai3_3.in bai3_3.out 1 điểm Bài 4: 4 điểm Test File dữ liệu vào File kết quả ra Điểm 1 bai4_1.in bai4_1.out 2 điểm 2 bai4_2.in bai4_2.out 1 điểm 3 bai4_3.in bai4_3.out 1 điểm Bài 5: 3 điểm Test File dữ liệu vào File kết quả ra Điểm 1 bai5_1.in bai5_1.out 1 điểm 2 bai5_2.in bai5_2.out 1 điểm 3 bai5_3.in bai5_3.out 1 điểm
SỞ GIÁO DỤC VÀ ĐÀO TẠO KÌ THI CHỌN HỌC SINH GIỎI TỈNH THANH HÓA Năm học: 2011-2012 ĐỀ THI CHÍNH THỨC Môn thi: TIN HỌC Số báo danh Lớp 12 THPT Ngày thi: 23 tháng 3 năm 2012 …...............…… Thời gian : 180 phút (không kể thời gian giao đề) Đề này có 3 trang, gồm 5 câu. Tổng quan bài thi: Tên bài File chương trình File dữ liệu vào File kết quả Bài 1 Số hexa BAI1.PAS BAI1.INP BAI1.OUT Bài 2 Số hoàn hảo BAI2.PAS BAI2.INP BAI2.OUT Bài 3 Chữ cái xuất hiện BAI3.PAS BAI3.INP BAI3.OUT Bài 4 Điểm gấp BAI4.PAS BAI4.INP BAI4.OUT Bài 5 Diện tích miền phủ BAI5.PAS BAI5.INP BAI5.OUT Hãy lập trình giải các bài toán sau: Bài 1: (5.0 điểm) Số hexa Trong toán học, lâu nay Bờm chỉ biết đến số thập phân. Hôm nay, tình cờ Bờm đọc được tài liệu nói về số hexa. Số hexa là số được tạo thành bởi các chữ số (0 → 9) và các chữ cái (A → F). Muốn chuyển đổi một số nguyên K (K ≥ 0) từ hệ thập phân sang hệ hexa Bờm làm như sau: Bờm lấy số K chia cho 16 được thương là P, rồi lấy thương P chia cho 16. Cứ lặp lại như vậy cho đến khi nào thương bằng 0 thì dừng, sau đó viết liên tiếp phần dư từ dưới lên thì Bờm thu được số hexa: 27 16 11 1 16 ⇒ 27(10) = 1B(16) 1 0 Yêu cầu: Cho dãy số nguyên ở hệ thập phân. Hãy giúp Bờm chuyển dãy số trên thành dãy số tương ứng ở hệ hexa. Dữ liệu vào: Từ file BAI1.INP gồm: - Dòng 1: Số nguyên dương n (n ≤ 103). - Dòng 2…n+1: Mỗi dòng chứa một số nguyên K (0 ≤ K ≤ 109). Kết quả: Ghi ra file BAI1.OUT gồm: n dòng là n số hexa tương ứng. Ví dụ: BAI1.INP BAI1.OUT 8 6 6 A 10 B 11 C 12 D 13 E 14 F 15 1B 27 Trang 1/3
Bài 2 (5.0 điểm) Số hoàn hảo Trong một buổi học toán Bờm được học khái niệm về số có tính chất đặc biệt. Số hoàn hảo là số có tổng các ước trừ nó ra thì bằng chính nó. Ví dụ: Số 6 là là số hoàn hảo vì nó có tổng các ước 1 + 2 + 3 = 6, số 8 không phải là số hoàn hảo vì 1 + 2 + 4 = 7 ≠ 8. Yêu cầu: Cho dãy số a1, a2,... an. Hãy giúp Bờm đếm xem trong dãy có bao nhiêu số có tổng các chữ số là số hoàn hảo. Dữ liệu vào: Từ file BAI2.INP gồm: - Dòng đầu tiên là số nguyên dương n (n ≤ 100). - n dòng tiếp theo ghi n số nguyên a1, a2,... an (0 ≤ ai ≤ 109). Kết quả: Ghi ra file BAI2.OUT gồm: Một dòng duy nhất là kết quả của bài toán. Ví dụ: BAI2.INP BAI2.OUT 3 2 6 123 28 Bài 3 (4.0 điểm) Chữ cái xuất hiện Cho xâu St chỉ gồm các chữ cái. Tính số lần xuất hiện của chữ cái xuất hiện nhiều nhất trong xâu (không phân biệt chữ in hoa và in thường). Dữ liệu vào: Từ file BAI3.INP gồm: Xâu St (độ dài ≤ 500 ký tự). Kết quả: Ghi ra file BAI3.OUT gồm: Một dòng duy nhất là bội số chung nhỏ nhất của kết quả bài toán và 105. Ví dụ: BAI3.INP BAI3.OUT AAABDA 100000 Bài 4 (3.0 điểm) Điểm gấp Mạnh có một sợi dây thừng có độ dài N (1 ≤ N ≤ 104). Sợi dây thừng có K nút thắt ở các vị trí khác nhau (2 ≤ K ≤ 100), bao gồm cả nút thắt ở mỗi đầu sợi dây. Mạnh cho rằng có một số điểm gấp để sợi dây trở lại sao cho các nút thắt ở phía đối diện thẳng hàng với nhau như trong hình sau: Điểm gấp Hãy giúp Mạnh đếm số lượng các điểm có thể gấp lại sao cho thỏa mãn điều kiện trên. Điểm gấp có thể là nút thắt nhưng không phải là nút thắt ở hai đầu. Tất nhiên, điểm gấp có thể là nút thắt ở một bên có thể dư ra (có nghĩa là nếu cả hai bên có nút thắt thì nó sẽ đối diện với nhau). Hơn nữa, Mạnh chỉ gấp lại một lần tại một thời điểm, cậu ta không bao giờ gấp nhiều lần. Dữ liệu vào: Từ file BAI4.INP gồm: - Dòng đầu tiên gồm hai số K và N (hai số cách nhau ít nhất một dấu cách trống). - Các dòng còn lại mỗi dòng chứa một số nguyên từ 0.. N là vị trí của các nút thắt. Trong đó sẽ có 2 nút thắt là 0 và N. Trang 2/3
Kết quả: Ghi ra file BAI4.OUT gồm: Một dòng duy nhất là số lượng các điểm gấp thỏa mãn điều kiện. Ví dụ: BAI4.INP BAI4.OUT 56 4 2 0 3 6 5 Giải thích: Sợi dây thừng có độ dài bằng 6 và có 5 nút thắt ở các vị trí 0, 2, 3, 5 và 6. Có 4 điểm gấp hợp lệ là 1, 2.5, 4 và 5.5. Bài 5: (3.0 điểm) Diện tích miền phủ Một trường học X cần làm mái che nằm ngang. Trường học có N tấm bạt hình chữ nhật, các tấm bạt làm mái che có thể chồng lên nhau. Tính diện tích bị che phủ. Dữ liệu vào: Từ file BAI5.INP gồm: - Dòng 1: Số nguyên N (1 ≤ N ≤ 10). - Dòng 2…N+1: Mỗi dòng chứa bốn số nguyên là x1, y1, x2 và y2, trong đó (x1, y1) là điểm trái trên của tấm bạt hình chữ nhật còn (x2, y2) là điểm phải dưới của tấm bạt hình chữ nhật (-104 ≤ x1, y1, x2, y2 ≤ 104). Các số trên một dòng cách nhau ít nhất một dấu cách trống. Kết quả: Ghi ra file BAI5.OUT gồm: Một dòng duy nhất là kết quả của bài toán. Ví dụ: BAI5.INP BAI5.OUT 3 20 0 5 4 1 2 4 6 2 0 5 4 1 ------------------- Hết ------------------- - Thí sinh không sử dụng tài liệu. - Cán bộ coi thi không giải thích gì thêm. Trang 3/3
SỞ GIÁO DỤC VÀ ĐÀO TẠO KÌ THI CHỌN HỌC SINH GIỎI TỈNH THANH HÓA Năm học: 2011-2012 HƯỚNG DẪN CHẤM MÔN TIN HỌC (Đề chính thức) Lớp 12 THPT Ngày thi: 23 tháng 3 năm 2012 (Hướng dẫn gồm 2 trang) HƯỚNG DẪN CHẤM (Kèm theo đĩa CD) Bài 1: 5 điểm Test File dữ liệu vào File kết quả ra Điểm 0 bai1.inp bai1.out 0.5 điểm 1 bai1.inp bai1.out 0.5 điểm 2 bai1.inp bai1.out 0.5 điểm 3 bai1.inp bai1.out 0.5 điểm 4 bai1.inp bai1.out 0.5 điểm 5 bai1.inp bai1.out 0.5 điểm 6 bai1.inp bai1.out 0.5 điểm 7 bai1.inp bai1.out 0.5 điểm 8 bai1.inp bai1.out 0.5 điểm 9 bai1.inp bai1.out 0.5 điểm Bài 2: 5 điểm Test File dữ liệu vào File kết quả ra Điểm 0 bai2.inp bai2.out 0.5 điểm 1 bai2.inp bai2.out 0.5 điểm 2 bai2.inp bai2.out 0.5 điểm 3 bai2.inp bai2.out 0.5 điểm 4 bai2.inp bai2.out 0.5 điểm 5 bai2.inp bai2.out 0.5 điểm 6 bai2.inp bai2.out 0.5 điểm 7 bai2.inp bai2.out 0.5 điểm 8 bai2.inp bai2.out 0.5 điểm 9 bai2.inp bai2.out 0.5 điểm Bài 3: 4 điểm Test File dữ liệu vào File kết quả ra Điểm 0 bai3.inp bai3.out 0.5 điểm 1 bai3.inp bai3.out 0.5 điểm 2 bai3.inp bai3.out 0.5 điểm 3 bai3.inp bai3.out 0.5 điểm 4 bai3.inp bai3.out 0.5 điểm 5 bai3.inp bai3.out 0.5 điểm Trang 1/2
6 bai3.inp bai3.out 0.5 điểm 7 bai3.inp bai3.out 0.5 điểm Bài 4: 3 điểm Test File dữ liệu vào File kết quả ra Điểm 0 bai4.inp bai4.out 0.5 điểm 1 bai4.inp bai4.out 0.5 điểm 2 bai4.inp bai4.out 0.5 điểm 3 bai4.inp bai4.out 0.5 điểm 4 bai4.inp bai4.out 0.5 điểm 5 bai4.inp bai4.out 0.5 điểm Bài 5: 3 điểm Test File dữ liệu vào File kết quả ra Điểm 0 bai5.inp bai5.out 0.5 điểm 1 bai5.inp bai5.out 0.5 điểm 2 bai5.inp bai5.out 0.5 điểm 3 bai5.inp bai5.out 0.5 điểm 4 bai5.inp bai5.out 0.5 điểm 5 bai5.inp bai5.out 0.5 điểm Trang 2/2