Đề thi Học sinh giỏi môn Tin học tỉnh Đồng Tháp 2016 2017

1. THCS Đồng Tháp 2016-2017

Bài 1:CẮT GIẤY

Để 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 X 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 X b và một mảnh kích thước b X (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 X (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 < 109).

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

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à a1, a2,..., an. 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 ≤ 105)
• Dòng thứ hai ghi n số nguyên a1, a2, ..., anlà 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à ai (1< ai < 105, i=1..n). Các số ghi trên 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 451545

3

Bài 3: HÀNG CÂY PHI LAO

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à a1, a2, ..., anmé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:

• 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.
• 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 <=106; 1<= m <= 107)
• Dòng thứ hai ghi n số nguyên dương a1, a2, ..., anvới ai là độ cao của cây thứ i (l<=ai<=109; i=l...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. Các số ghi trên cùng một dòng cách nhau một kí tự trắng.

Ví dụ:

PHILAO.INP

PHILAO.OUT

47

20 15 10 18

23

15

Ràng buộc:

• Có 70% số test tương ứng 70% số điểm của bài có n<=104
• Có 30% số test tương ứng 30% số điểm của bài có n<=106