Đề thi Tin học trẻ cấp Thành phố Khối THPT - Bảng C - Năm học 2018-2019 - Sở GD và ĐT Thành phố Đà Nẵng

Nội dung text: Đề thi Tin học trẻ cấp Thành phố Khối THPT - Bảng C - Năm học 2018-2019 - Sở GD và ĐT Thành phố Đà Nẵng

1. UBND THÀNH PHỐ ĐÀ NẴNG HỘI THI TIN HỌC TRẺ CẤP THÀNH PHỐ NĂM HỌC 2018- 2019 ĐỀ THI BẢNG C - KHỐI THPT Thời gian: 150 phút (không kể thời gian giao đề) ĐỀ CHÍNH THỨC === TỔNG QUAN ĐỀ THI (Đề thi gồm có 3 bài trong 3 trang) File chương Tên bài Dữ liệu vào Dữ liệu ra trình Bài 1 Quân xe ROOKS.* ROOKS.INP ROOKS.OUT Bài 2 Dãy số SEQ.* SEQ.INP SEQ.OUT Bài 3 Thu hoạch nấm LAZY.* LAZY.INP LAZY.OUT (Phần mở rộng * là PAS hay CPP tùy theo ngôn ngữ và môi trường lập trình) Bài 1. Quân xe (3 điểm) Tìm cách đặt N quân xe trên bàn cờ NxN (1 ≤ N ≤ 3000) sao cho thỏa mãn những điều kiện sau: 1/ Không có hai con xe nào có thể ăn được nhau. 2/ Con xe thứ i phải nằm trong hình chữ nhật thứ i cho trước. (cho trước N hình chữ nhật) Giả sử hình chữ nhật thứ i có toạ độ ô trái trên là (a i,bi), toạ độ ô phải dưới là (ci,di). Như vậy con xe thứ i phải đặt tại ô (x i,yi) thoả mãn: a i ≤ x i ≤ c i; bi ≤ y i ≤ d i. (ai,ci,xi – dòng; bi,di,yi - cột) Dữ liệu vào: Từ file văn bản ROOKS.INP gồm: - Dòng đầu chứa số nguyên N thể hiện kích thước bàn cờ. - N dòng tiếp theo dòng thứ i ghi bốn số nguyên a i, bi, ci, di cách nhau bởi dấu cách miêu tả hình chữ nhật thứ i. (1 ≤ ai, bi, ci, di ≤ N). Dữ liệu ra: Ghi ra file văn bản ROOKS.OUT: - Nếu không thể đặt N quân xe thoả mãn các điều kiện trên, ghi ‘No solution.’ - Ngược lại ghi tọa độ của N con xe trên N dòng đầu tiên. Ví dụ: ROOKS.INP ROOKS.OUT 4 1 1 1 1 1 1 2 3 1 3 2 4 3 2 3 1 4 2 4 4 2 2 4 4 Trang 1/3
2. Bài 2: Dãy số (3 điểm) Trong tiết học về dãy số tại trường, thầy giáo cho cả lớp chơi một trò chơi như sau: Cho một dãy số A bao gồm n số nguyên, yêu cầu hãy chia dãy số trên thành hai phần liên tiếp sao cho tổng các số ở phần bên trái bằng tổng các số ở phần bên phải. Với mỗi bước như vậy bạn được 1 điểm còn nếu không thể chia được thì trò chơi sẽ kết thúc. Sau khi chia thành công bạn sẽ được chọn dãy số bên trái hoặc bên phải để tiếp tục cuộc chơi với các bước như trên cho đến khi trò chơi kết thúc. Là một học sinh giỏi toán trong lớp, An muốn kiếm được số điểm cao nhất có thể. Bạn hãy tính xem số điểm lớn nhất mà An có thể đạt được là bao nhiêu? Dữ liệu vào: Từ file văn bản SEQ.INP gồm: - Dòng đầu tiên ghi một số nguyên T ( 1 ≤ T ≤ 10) là số lượng bộ dữ liệu. Mỗi bộ liệu bao gồm hai dòng: + Dòng 1 ghi một số nguyên N là số lượng phần tử của dãy A. + Dòng 2 gồm N phần tử của dãy A được ghi cách nhau bởi dấu cách. (0 ≤ A[i] ≤ 10 9) Dữ liệu ra: Ghi ra file văn bản SEQ.OUT: Với mỗi bộ dữ liệu in ra một số nguyên trên một dòng là kết quả của bộ dữ liệu tương ứng. Ví dụ: SEQ.INP SEQ.OUT 3 0 3 2 3 3 3 3 4 2 2 2 2 7 4 1 0 1 1 0 1 Ràng buộc: - Có 30% số test ứng với 30% số điểm của bài có N ≤ 28. - Có 60% số test ứng với 60% số điểm của bài có 28 < N ≤ 211. - Có 10% số test ứng với 10% số điểm của bài có 211 < N ≤ 214. Bài 3: Thu hoạch nấm (4 điểm) Đang là giữa mùa đông và việc đi ra khỏi nhà là việc vô cùng khó khăn với Bờm. Ngày mai, bạn ấy được giao việc đi thu hoạch nấm trên khu đất nhà mình. Có thể coi khu đất có nấm mà Bờm phải thu hoạch là một đoạn thẳng trên trục số. Có N vị trí có nấm: vị trí có nấm thứ ở điểm có cây nấm. Vì trời rất lạnh nên Bờm muốn chọn một điểm xuất phát để từ đó thu hoạch nấm những điểm có khoảng cách không quá K so với vị trí mà Bờm chọn sao cho tổng số nấm thu được là nhiều nhất có thể. Trang 2/3
3. Yêu cầu: Hãy giúp Bờm tính xem tổng số nấm lớn nhất mà Bờm có thể thu hoạch được trong khoảng cách không quá K tính từ vị trí xuất phát mà Bờm đã chọn từ trước. Dữ liệu vào: Từ file văn bản LAZY.INP gồm: - Dòng đầu chứa hai số nguyên dương N và K (N, K ≤ 2.10 6) được ghi cách nhau bởi dấu cách. - N dòng tiếp theo, mỗi dòng gồm 2 số và : có cây nấm ở điểm được ghi cách nhau bởi dấu cách. Dữ liệu ra: Ghi ra file văn bản LAZY.OUT một số nguyên duy nhất là tổng số nấm lớn nhất mà Bờm có thể thu hoạch được. Ví dụ: LAZY.INP LAZY.OUT 4 3 11 Giải thích: 4 7 Bờm nên xuất phát từ vị trí 4 10 15 để có thể thu hoạch được nấm 2 2 ở vị trí 1, 2 và 7. 5 1 Tổng số nấm là: 5 + 2 + 4 = 11 Ràng buộc: ít nhất 40% số điểm ứng với các test có N ≤ 5000. HẾT Trang 3/3