Đề thi học sinh giỏi lớp 12 THPT tỉnh Thanh Hóa năm học 2011 - 2012 môn Tin học (Có đáp án)

[DOWNC="http://w6.mien-phi.com/data/file/2013/thang05/19/Dethi-HSG-L12-ThanhHoa-2012-Tinhoc.pdf"]TẢI TÀI LIỆU[/DOWNC]

Đề thi học sinh giỏi lớp 12 THPT tỉnh Thanh Hóa năm học 2011 - 2012 môn Tin học (Có đáp án) - Sở GD&ĐT Thanh Hóa

[TABLE]
[TBODY]
[TR]
[TD]
SỞ GIÁO DỤC VÀ ĐÀO TẠO
THANH HÓA
(Đề thi chính thức)
[/TD]
[TD]
KỲTHI CHỌN HỌC SINH GIỎI LỚP 12 THPT
CẤP TỈNH NĂM HỌC 2011 - 2012
Ngày thi: 23/03/2012
[/TD]
[/TR]
[/TBODY]
[/TABLE]
MÔN THI: TIN HỌC
Thời gian làm bài: 180 phút (không kể thời gian giao đề)
--------------------------------------------------------------------------------
Tổng quan bài thi:

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:

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 ≤10[SUP]3[/SUP]).
- Dòng 2 n+1: Mỗi dòng chứa một sốnguyên K (0 ≤ K ≤ 10[SUP]9[/SUP]).
Kết quả: Ghi ra file BAI1.OUT gồm: n dòng là n số hexa tương ứng.
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à 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ố a[SUB]1[/SUB], a[SUB]2[/SUB], . a[SUB]n[/SUB]. 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 a[SUB]1[/SUB], a[SUB]2[/SUB], . an (0 ≤ ai ≤10[SUP]9[/SUP]).
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
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à 10[SUP]5[/SUP].
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 ≤ 10[SUP]4[/SUP]). 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:

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ốn guyê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
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.
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à x[SUB]1[/SUB], y[SUB]1[/SUB], x[SUB]2 [/SUB]và y[SUB]2[/SUB], trong đó (x[SUB]1[/SUB], y[SUB]1[/SUB]) là điểm trái trên của tấm bạt hình chữ nhật còn (x[SUB]2[/SUB], y[SUB]2[/SUB]) là điểm phải dưới của tấm bạt hình chữnhật (-10[SUP]4[/SUP] ≤ x[SUB]1[/SUB], y[SUB]1[/SUB], x[SUB]2[/SUB], y[SUB]2[/SUB] ≤ 10[SUP]4[/SUP]). 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.