Tuyển tập 9 Đề thi HSG cấp Trường môn Tin học 12 (Kèm đáp án)

Tuyển tập 9 Đề thi HSG cấp Trường môn Tin học 12 (Kèm đáp án) - DeThi.edu.vn

DeThi.edu.vn

ĐỀ SỐ 1

PHÒNG GIÁO DỤC & ĐÀO TẠO

……………

ĐỀ KIỂM TRA CHẤT LƯỢNG HỌC SINH GIỎI CẤP TRƯỜNG MÔN: TIN HỌC – LỚP 12 Thời gian: 180 phút (không kể thời gian giao đề)

TỔNG QUAN BÀI THI Bài File mã nguồn File dữ liệu vào File dữ liệu ra Bộ nhớ Điểm Bài 1 SEQ.* SEQ.INP SEQ.OUT 1024 MB 5.0 Bài 2 TRI.* TRI.INP TRI.OUT 1024 MB 5.0 Bài 3 GRID.* GRID.INP GRID.OUT 1024 MB 6.0 Bài 4 MSD.* MSD.INP MSD.OUT 1024 MB 6.0 Bài 5 PLAN.* PLAN.INP PLAN.OUT 1024 MB 8.0 Chú ý: Học sinh làm bài trên máy tính, sử dụng ngôn ngữ lập trình C++ hoặc Python viết chương trình theo yêu cầu của các bài toán - Học sinh nộp bài thi là các file mã nguồn được đặt tên theo quy định trên; dấu * trong tên file mã nguồn là cpp hoặc py tương ứng với ngôn ngữ C++ hoặc Python; - Không ghi thông tin cá nhân (họ tên, số báo danh, ngày sinh, trường,...) và các ký hiệu khác thường vào file mã nguồn nộp; Bài 1. Dãy số nguyên

Dãy số nguyên A {a1, a2, a3, a4,…} được xây dựng như sau:

1

1 

      i i

a k

a a d với k và d là các số

nguyên cho trước. Ví dụ: với k = 2 và d = 3 thì dãy số A là {2, 5, 8, 11}. Yêu cầu: Cho số nguyên dương n, tìm số an của dãy A và tính tổng a1 + a2 + … + an. Dữ liệu: Nhập vào từ file văn bản SEQ. INP có 3 số nguyên dương k, d và n viết cách nhau bởi dấu cách trống (k, d ≤ 103; n ≤ 1015). Kết quả: Ghi ra file văn bản SEQ.OUT 2 dòng: • Dòng đầu tiên ghi số nguyên an của dãy A; • Dòng thứ hai ghi số nguyên là phần dư trong phép chia tổng a1 + a2 + … + an cho số nguyên 1000000007. Ví dụ:

SEQ.INP SEQ.OUT Giải thích 1 2 5 9 25

Dãy số ? là {1, 3, 5, 7, 9, 11 … }. Số ?5 = 9; Tổng ? = 1 + 3 + 5 + 7 + 9 = 25 10 100 1000 99910 49960000

DeThi.edu.vn

Tuyển tập 9 Đề thi HSG cấp Trường môn Tin học 12 (Kèm đáp án) - DeThi.edu.vn

DeThi.edu.vn

Chấm điểm: • Subtask 1 (80% số điểm): Dữ liệu vào có ? ≤ 106. • Subtask 2 (20% số điểm): Không có ràng buộc nào thêm. Bài 2. Tam giác vuông Trong mặt phẳng tọa độ ???, cho đoạn thẳng ?? nằm trên trục hoành ?? và có trung điểm là gốc tọa độ ?(0; 0). Yêu cầu: Đếm số tam giác vuông có cạnh huyền là ?? và tọa độ của đỉnh ở góc vuông là số nguyên. Dữ liệu: Nhập vào từ file văn bản TRI.INP có một số nguyên dương ? (? ≤ 1016) là hoành độ của điểm ?. Kết quả: Ghi ra file văn bản TRI.OUT một số nguyên dương là kết quả tìm được theo yêu cầu của bài toán. Ví dụ:

TRI.INP TRI.OUT Giải thích 5 10 Có 10 tam giác vuông như hình vẽ sau đây:

3125 42 Chấm điểm: • Subtask 1 (80% số điểm): Dữ liệu vào có ? ≤ 108. • Subtask 2 (20% số điểm): Không có ràng buộc nào thêm. Bài 3. Lưới ô vuông Cho lưới ô vuông có ? hàng và ? cột. Ô vuông (?, ?) là ô giao giữa hàng ? (? ∈ [1, ?]) với cột ? (? ∈ [1, ?]). Trên mỗi ô (?, ?) ghi một số nguyên dương theo quy tắc sau: • Bắt đầu từ ô trên cùng bên trái (1,1) ghi số nguyên dương ?. • Các ô tiếp theo lần lượt từ trái sang phải, từ trên xuống dưới, từ phải quay về trái ghi một số

DeThi.edu.vn

Tuyển tập 9 Đề thi HSG cấp Trường môn Tin học 12 (Kèm đáp án) - DeThi.edu.vn

DeThi.edu.vn

có giá trị hơn số ở ô liền kề phía trước đó một giá trị nguyên dương ? cho trước. Thao tác này lặp lại cho đến hết ô cuối cùng. Ví dụ: với ? = 6, ? = 5, ? = 2, ? = 3, các số trong hình chữ nhật như sau:

2 5 8 11 14 17 35 20 38

89

Yêu cầu: Tìm hình chữ nhật (gồm các ô liền kề nhau) có nhiều ô nhất sao cho tổng các số trong hình chữ nhật đó có giá trị bằng số nguyên ? cho trước. Dữ liệu: Nhập vào từ file văn bản GRID.INP có nội dung như sau: • Dòng đầu tiên có 4 số nguyên dương ?, ?, ?, ? (?, ? ≤ 102; ?, ? ≤ 103) viết cách nhau bởi dấu cách trống. • Dòng thứ hai là số nguyên dương ? (? ≤ 1012). Kết quả: Ghi ra file văn bản GRID.OUT số lượng ô của hình chữ nhật tìm được theo yêu cầu. Nếu không có hình chữ nhật nào thỏa mãn thì ghi ra -1. Ví dụ:

GRID.INP GRID.OUT Giải thích 1 8 1 2 32

4 Hình chữ nhật có các số in đậm:

1 3 5 7 9 11 13 15 5 6 2 3 414

9 Hình chữ nhật có các số in đậm:

2 5 8 11 14 17 35 32 29 26 23 20 38 41 44 …