Kỳ thi Olympic 24/3 tỉnh Quảng Nam môn Tin học Lớp 11 - Năm học 2021-2022 - Sở GD&ĐT Quảng Nam (Có đáp án)

Nội dung text: Kỳ thi Olympic 24/3 tỉnh Quảng Nam môn Tin học Lớp 11 - Năm học 2021-2022 - Sở GD&ĐT Quảng Nam (Có đáp án)

1. SỞ GIÁO DỤC VÀ ĐÀO TẠO KỲ THI OLYMPIC 24/3 TỈNH QUẢNG NAM QUẢNG NAM NĂM 2021 Môn thi : TIN HỌC - LỚP 11 ĐỀ CHÍNH THỨC Thời gian : 150 phút (không kể thời gian giao đề) Ngày thi : 20/03/2021 (Đề thi có 04 trang) TỔNG QUAN ĐỀ THI TỔNG QUAN ĐỀ BÀI File chương Thời Bài Tên bài File dữ liệu vào File kết quả trình gian Tổng bình phương 1 SQUARE.* SQUARE.INP SQUARE.OUT 1 s các chữ số Ước chung lớn 2 MAXGCD.* MAXGCD.INP MAXGCD.OUT 1 s nhất 3 Sơn gạch SONGACH.* SONGACH.INP SONGACH.OUT 1 s 4 Thỏ và cà rốt RABBIT.* RABBIT.INP RABBIT.OUT 1 s 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. Tổng bình phương các chữ số (5 điểm) Cho một số tự nhiên N (N ≤ 1064). Yêu cầu: Hãy viết chương trình tính tổng bình phương các chữ số của số tự nhiên đã cho. Ví dụ: N=12. Tổng bình phương các chữ số của nó là 5 = 12 + 22. Dữ liệu vào: Từ tệp văn bản SQUARE.INP gồm một số N. Kết quả: Ghi ra tệp văn bản SQUARE.OUT gồm một số duy nhất tìm được. Ví dụ: SQUARE.INP SQUARE.OUT 12 5 Ràng buộc: • Có 60% test tương ứng 60% số điểm của bài với N ≤ 106; • Có 20% test tương ứng 20% số điểm của bài với N ≤ 1018; • Có 20% test khác tương ứng với 20% số điểm còn lại của bài với N ≤ 1064. Bài 2. Ước chung lớn nhất (5 điểm)
2. Ví dụ: SONGACH.INP SONGACH.OUT 3 3 0 3 SONGACH.INP SONGACH.OUT 3 2 1 4 Ràng buộc: • Có 30% test tương ứng 30% số điểm của bài với 1 ≤ n, m ≤ 2000, k = 0; • Có 30% test tương ứng 30% số điểm của bài với 1 ≤ n, m, k ≤ 10; • Có 40% test khác tương ứng với 40% số điểm còn lại của bài với 1 ≤ n, m ≤ 2000, 0<k ≤ n-1). Bài 4. Thỏ và cà rốt (5 điểm) Một lưới NxN ô vuông gồm có N hàng và N cột. Các hàng được đánh số từ 1 đến N (từ trên xuống) và các cột đánh số từ 1 đến N( từ trái qua). Một con Thỏ xuất phát từ ô (1, 1) và muốn di chuyển đến ô có đặt củ cà rốt là ô (X, Y). Người ta đặt các chướng ngại vật để Thỏ không được đi qua ở các ô đánh số 1; các ô không đặt chướng ngại vật được đánh số 0 và Thỏ có thể đi qua các ô này. Từ ô đang đứng, Thỏ chỉ có thể di chuyển đến 3 ô kề cạnh: một ô bên dưới và hai ô ở hai bên. Thỏ không thể di chuyển ra ngoài đường biên của lưới. Yêu cầu: Tìm đường đi ngắn nhất (đi qua ít ô nhất) của Thỏ. Dữ liệu vào: Từ tệp văn bản RABBIT.INP gồm: • Dòng đầu ghi số 3 số nguyên dương: N, X, Y (N 1000; X N; Y N ). • N dòng tiếp theo mỗi dòng ghi N số nguyên 0 hoặc 1, mỗi số cách nhau một khoảng trắng. (Riêng số đầu tiên của dòng thứ nhất và số thứ Y của dòng X ghi số 0 của lưới). Kết quả : Ghi ra tệp văn bản RABBIT.OUT gồm: • Một số nguyên dương là số các ô mà Thỏ đi qua (kể cả ô xuất phát và ô đích). Trong trường hợp Thỏ không di chuyển được đến ô đặt củ cà rốt thì phải ghi số 0. Ví dụ: RABBIT.INP RABBIT.OUT 5 3 4 6 0 0 0 0 0
3. (ĐA. gồm có 01 trang) Chấm bài bằng chương trình chấm Themis mới nhất (có kèm theo) cài đặt trên hệ điều hành Windows 10 (64bit) trở lên, các tests đã cài đặt sẵn cấu hình chấm bài. Bài 1: (5 điểm) Có 20 tests, mỗi TEST đúng được 0.25 điểm. Thời gian chạy 1s/ 1test. Bộ nhớ 1024M. TEST SUMN.INP SUMN.OUT 1 1111 4 20 Bài 2: (5 điểm) Có 20 tests, mỗi TEST đúng được 0.25 điểm. Thời gian chạy 1s/ 1test. Bộ nhớ 1024M. TEST MAXGCD.INP MAXGCD.OUT 1 10 3996 3628800 20 Bài 3: (5 điểm) Có 20 tests, mỗi TEST đúng được 0.25 điểm. Thời gian chạy 1s/ 1test. Bộ nhớ 1024M. TEST SONGACH.INP SONGACH.OUT 1 3 3 2 12 20 Bài 4: (5 điểm) Có 25 tests, mỗi TEST đúng được 0.2 điểm. Thời gian chạy 1s/ 1test. Bộ nhớ 1024M. TEST SUBSTR.INP SUBSTR.OUT 7 3 5 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 11 1 0 1 0 0 0 0 1 1 0 1 0 1 1 1 0 1 1 0 1 1 0 1 1 1 1 0 1