Đề thi chọn Học sinh giỏi cấp tỉnh môn Tin học - Bảng A - Năm học 2019-2020 - Sở Giáo dục và đào tạo tỉnh Quảng Ninh (Có đáp án)

Nội dung text: Đề thi chọn Học sinh giỏi cấp tỉnh môn Tin học - Bảng A - Năm học 2019-2020 - Sở Giáo dục và đào tạo tỉnh Quảng Ninh (Có đáp án)

1. SỞ GIÁO DỤC VÀ ĐÀO TẠO KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH THPT NĂM 2019 TỈNH QUẢNG NINH Môn thi: TIN HỌC - Bảng A Ngày thi: 03/12/2019 ĐỀ THI CHÍNH THỨC Thời gian làm bài: 180 phút, không kể thời gian giao đề (Đề thi này có 03 trang) TỔNG QUAN VỀ ĐỀ THI Bài Bài 1 Bài 2 Bài 3 File chương trình SEQ.* ASUM.* EQUATION.* File dữ liệu vào SEQ.INP ASUM.INP EQUATION.INP File kết quả SEQ.OUT ASUM.OUT EQUATION.OUT Giới hạn thời gian 1 giây/ test 1 giây/ test 1 giây/ test Giới hạn bộ nhớ 1024 MB 1024 MB 1024 MB 7 điểm 7 điểm 6 điểm Điểm Tổng 20 điểm Dấu * được thay thế bởi PAS hoặc CPP của ngôn ngữ lập trình được sử dụng tương ứng là Pascal hoặc C++. Hãy lập trình giải các bài toán sau: Bài 1. Dãy số Cho dãy số ( 푛) được xác định bằng phương pháp truy hồi như sau: 0 = 1, 1 = 6 푛 = 6 푛―1 ― 9 푛―2 푣ớ푖 푛 ≥ 2 Với hai số nguyên dương 푛, cho trước. Hãy tìm số dư khi chia 푛 cho . Dữ liệu: Vào từ file văn bản SEQ.INP: Một dòng duy nhất chứa hai số nguyên dương 푛 và (푛, ≤ 1018) được ghi cách nhau bởi dấu cách. Kết quả: Ghi ra file văn bản SEQ.OUT trên một dòng, một số nguyên duy nhất là kết quả theo yêu cầu của bài toán. Ví dụ: SEQ.INP SEQ.OUT 5 100 58 10 898 285 Ràng buộc: • Có 50% số test ứng với 50% số điểm của bài có 푛 ≤ 35, = 1018. • Có 30% số test khác ứng với 30% số điểm của bài có 푛 ≤ 106, ≤ 1018. • Có 20% số test còn lại ứng với 20% số điểm của bài có 푛 ≤ 1018, ≤ 1018. Trang 1/3
2. Bài 2. Đếm dãy con liên tiếp Cho dãy số có 푛 số nguyên 1, 2, , 푛. Một dãy con liên tiếp các số hạng của dãy là dãy các số hạng từ số hạng 푖 đến số hạng 푗 (1 ≤ 푖 ≤ 푗 ≤ 푛). Hãy cho biết dãy có bao nhiêu dãy con liên tiếp mà giá trị tuyệt đối của tổng các số hạng trong dãy con đó lớn hơn một số nguyên dương 푆 cho trước. Dữ liệu: Vào từ file văn bản ASUM.INP: • Dòng thứ nhất chứa hai số nguyên dương 푛 và 푆 (푛 ≤ 105,푆 ≤ 1014). 9 • Dòng thứ hai chứa 푛 số nguyên 1, 2, , 푛 (| 푖| ≤ 10 ). Hai số liên tiếp trên cùng dòng được ghi cách nhau bởi dấu cách. Kết quả: Ghi ra file văn bản ASUM.OUT trên một dòng, một số nguyên duy nhất là số dãy con liên tiếp thỏa mãn yêu cầu của bài toán. Ví dụ: ASUM.INP ASUM.OUT 4 4 6 5 -1 8 -5 10 7 12 -4 9 2 -11 -3 8 -6 5 -3 1 Giải thích: Trong ví dụ đầu tiên có 6 dãy con thỏa mãn yêu cầu là :{5},{8},{ ―5},{ ―1;8}, {5; ― 1;8} và {5; ― 1;8;5}. Ràng buộc: • Có 50% số test ứng với 50% số điểm của bài có 푛 ≤ 100. • Có 30% test khác ứng với 30% số điểm của bài có 푛 ≤ 103. • Có 20% test còn lại ứng với 20% số điểm của bài có 푛 ≤ 105. Bài 3. Phương trình Cho hai số nguyên dương và 푛. Xét phương trình bậc nhất 푛 ẩn: 1 + 2 + 3 + + 푛 = với 푛 điều kiện ràng buộc 푖 ≥ 푖, 푖 nguyên dương (푖 = 1, 2, 푛). Gọi là số các nghiệm nguyên của phương trình thỏa mãn các điều kiện ràng buộc. Hãy tìm số dư khi chia T cho 1000000007. Dữ liệu: Vào từ file văn bản EQUATION.INP: • Dòng thứ nhất chứa hai số nguyên dương và 푛 ( ≤ 109,푛 ≤ 105). 9 • Dòng thứ hai chứa 푛 số nguyên dương 1, 2, , 푛 ( 푖 ≤ 10 ). Hai số liên tiếp trên cùng dòng được ghi cách nhau bởi dấu cách. Trang 2/3
3. Kết quả: Ghi ra file văn bản EQUATION.OUT trên một dòng, một số nguyên duy nhất là kết quả theo yêu cầu của bài toán. Ví dụ: EQUATION.INP EQUATION.OUT 7 3 6 2 2 1 Giải thích: Có 6 nghiệm là (2;2;3),(2;3;2),(2;4;1),(3;2;2),(3;3;1),(4;2;1). Ràng buộc: • Có 30% số test ứng với 30% số điểm của bài có ≤ 1000,푛 ≤ 3. • Có 40% số test khác ứng với 40% số điểm của bài có ≤ 1000,푛 ≤ 1000. • Có 30% số test còn lại ứng với 30% số điểm của bài có ≤ 109,푛 ≤ 105. Hết - Thí sinh không được sử dụng tài liệu; - Cán bộ coi thi không giải thích gì thêm. Họ và tên thí sinh: Số báo danh: Chữ kí của cán bộ coi thi 1: Chữ kí của cán bộ coi thi 2: Trang 3/3