HSG lớp 9 Đồng Tháp 2016-2017

SỞ GIÁO DỤC VÀ ĐÀO TẠO TỈNH ĐỒNG THÁP ĐỀ CHÍNH THỨC

KỲ THI CHỌN HỌC SINH GIỎI LỚP 9 CẤP TỈNH Năm học 2016 - 2017
Đề thi môn Tin học - Ngày thi: 19/3/2017
Thời gian làm bài: 150 phút (không kể thời gian phát đề)
(Đề thi gồm có 03 trang)

---

Tổng quan đề thi

Bài	Tên tệp chương trình	Tên tệp dữ liệu vào	Tên tệp kết quả ra
Bài 1. Cắt giấy	BL1.*	PAPER.INP	PAPER.OUT
Bài 2. Các thí sinh thông minh	BL2.*	TM.INP	TM.OUT
Bài 3. Hàng cây phi lao	BL3.*	PHILAO.INP	PHILAO.OUT

Ghi chú: Kí tự * là phần mở rộng của tệp chương trình tùy theo ngôn ngữ lập trình (ngôn ngữ Pascal là .pas, ngôn ngữ C là .cpp). Thời gian chạy chương trình không quá 01 giây.

Bài 1. Cắt giấy (6,0 điểm)

Để chuẩn bị cho ngày cắm trại, Nam và các bạn cùng nhau cắt những mảnh giấy màu để trang trí trại. Nhằm làm tăng thêm phần độc đáo, bạn Nam nghĩ ra một cách cắt tờ giấy màu thành các hình vuông.

Tờ giấy màu của Nam có dạng hình chữ nhật kích thước a × b (a > b). Sau đó Nam sẽ gấp chéo tờ giấy tạo thành đường gấp có góc 45 độ, một mép trùng với một cạnh của tờ giấy (như hình vẽ), sau đó cắt phần giấy thừa không bị gấp đè lên.

Sau khi cắt, Nam nhận được một mảnh giấy hình vuông kích thước b × b và một mảnh kích thước b × (a - b). Nam lại tiếp tục thực hiện thao tác như trên với mảnh giấy b × (a - b) và cứ thế cho đến khi tất cả các mảnh giấy đều là hình vuông.

Yêu cầu: Hãy xác định xem Nam có thể có được bao nhiêu mảnh giấy hình vuông?

Dữ liệu vào: Cho từ tệp văn bản PAPER.INP gồm một dòng ghi hai số nguyên a và b cách nhau một kí tự trắng (1 ≤ b ≤ a ≤ 10⁹).

Kết quả: Ghi ra tệp văn bản PAPER.OUT gồm một dòng ghi một số nguyên là số hình vuông sau khi cắt.

Ví dụ:

PAPER.INP	PAPER.OUT
10 7	6

Bài 2. Các thí sinh thông minh (7,0 điểm)

Cuộc thi “Các thí sinh thông minh” là một cuộc thi rất nổi tiếng trên truyền hình. Để chọn các thí sinh thông minh nhất, cuộc thi có nhiều vòng thi, thang điểm mỗi vòng thi là 20 điểm. Năm nay có n thí sinh dự thi, hiện tại đang chuẩn bị bước vào vòng thi cuối cùng và tổng điểm số của từng thí sinh ở các vòng thi trước lần lượt là a₁, a₂, …, aₙ. Tổng điểm chung cuộc của các thí sinh sẽ bằng điểm số của họ đạt được trong vòng thi này cộng với điểm số đã có ở các vòng thi trước.

Yêu cầu: Cho trước tổng số điểm của từng thí sinh ở các vòng thi trước. Hãy tính xem có bao nhiêu thí sinh có khả năng vô địch. Biết rằng thí sinh vô địch là thí sinh đạt tổng số điểm cao nhất của cuộc thi.

Dữ liệu vào: Cho từ tệp TM.INP gồm hai dòng:

• Dòng thứ nhất ghi số nguyên n là số thí sinh dự thi (1 < n ≤ 10⁵).
• Dòng thứ hai ghi n số nguyên a₁, a₂, …, aₙ là tổng điểm số ở các vòng thi trước của từng thí sinh, thí sinh thứ i có tổng điểm số là aᵢ (1 < aᵢ < 10⁵, i = 1..n). Các số ghi trên cùng một dòng cách nhau một kí tự trắng.

Kết quả: Ghi vào tệp văn bản TM.OUT gồm một dòng ghi số nguyên là số lượng thí sinh có khả năng vô địch.

Ví dụ:

TM.INP	TM.OUT
4 40 45 15 45	3

Bài 3. Hàng cây phi lao (7,0 điểm)

Cây phi lao là loại cây được trồng nhiều ở ven biển nước ta. Ngoài công dụng chắn gió, giữ đất, cây phi lao còn là nguyên liệu để làm giấy. Ở ven biển, ông Năm trồng cây phi lao thành một hàng dài gồm có n cây, các cây có độ cao lần lượt là a₁, a₂, …, aₙ mét. Để đảm bảo chắn gió và giữ đất, ông Năm thu hoạch phi lao từ trên ngọn xuống để giữ lại phần gốc. Chẳng hạn để thu hoạch m mét gỗ phi lao, ông Năm cưa hàng cây ở độ cao h mét nào đó (dĩ nhiên những cây có độ cao không lớn hơn h thì không bị cưa) sao cho thu hoạch phần ngọn đủ m mét gỗ và số gỗ phi lao dư ra là ít nhất. Ví dụ, hàng cây có các cây với độ cao tương ứng là: 20; 15; 10 và 18 mét, cần lấy 7 mét gỗ, ông Năm cưa hàng cây ở độ cao h = 15 là hợp lí nhất vì ông Năm thu hoạch được 8 mét phần ngọn (dư 1 mét), phần gốc còn lại lần lượt là: 15; 15; 10; 15 mét.

Yêu cầu:

a) Tính tổng số lượng mét gỗ thu hoạch được nếu chọn cưa hàng cây ở độ cao bằng với cây phi lao thấp nhất.

b) Hãy tìm vị trí h mét hợp lí nhất (h là số nguyên) sao cho thu hoạch được m mét gỗ và số mét gỗ dư ra là ít nhất.

Dữ liệu vào: Cho từ tệp văn bản PHILAO.INP gồm hai dòng:

• Dòng thứ nhất ghi hai số nguyên dương n và m (1 ≤ n ≤ 10⁶; 1 ≤ m ≤ 10⁷).
• Dòng thứ hai ghi n số nguyên dương a₁, a₂, …, aₙ với aᵢ là độ cao của cây thứ i (1 ≤ aᵢ ≤ 10⁹; i = 1…n). Các số ghi trên cùng một dòng cách nhau một kí tự trắng.

Kết quả: Ghi vào tệp văn bản PHILAO.OUT gồm hai dòng:

• Dòng thứ nhất ghi số nguyên s là tổng số mét gỗ thu hoạch được nếu cưa hàng cây ở độ cao bằng với cây phi lao thấp nhất.
• Dòng thứ hai ghi số nguyên h tìm được để thu hoạch đủ m mét gỗ và số gỗ dư ra là ít nhất. Nếu không tìm được h ghi ra số -1.

Ví dụ:

PHILAO.INP	PHILAO.OUT
4 7 20 15 10 18	23 15

Mô phỏng:

Ràng buộc dữ liệu:

• Có 70% số test tương ứng 70% số điểm của bài có n ≤ 10⁴.
• Có 30% số test tương ứng 30% số điểm của bài có n ≤ 10⁶.