Đề thi chọn học sinh giỏi cấp tỉnh môn Tin học 12 - Bảng A - Năm học 2019-2020 - SGD&ĐT Gia Lai (Có đáp án)

Nội dung text: Đề thi chọn học sinh giỏi cấp tỉnh môn Tin học 12 - Bảng A - Năm học 2019-2020 - SGD&ĐT Gia Lai (Có đáp án)

1. SỞ GIÁO DỤC VÀ ĐÀO TẠO KỲ THI CHỌN HỌC SINH GIỎI GIA LAI LỚP 12 CẤP TỈNH (BẢNG A) NĂM HỌC 2019 - 2020 ĐỀ CHÍNH THỨC Môn thi: TIN HỌC (Đề thi có 03 bài, 04 trang) Thời gian: 180 phút (không kể thời gian phát đề) Ngày thi: 18/10/2019 TỔNG QUAN ĐỀ THI Tên file Tên file Tên file Thời Bài Tên bài chương trình dữ liệu vào dữ liệu ra gian 1 Đố vui - Quiz QUIZ.* QUIZ.INP QUIZ.OUT 2s Khu đất tốt hình 2 SQUARE.* SQUARE.INP SQUARE.OUT 2s vuông - Square 3 Mê cung - Maze MAZE.* MAZE.INP MAZE.OUT 2s Lưu ý: - Dấu * được thay thế bởi PAS hoặc CPP của ngôn ngữ lập trình tương ứng là Pascal hoặc C++. - Thí sinh bắt buộc phải đặt tên file chương trình, file dữ liệu như trên. - Khi hết thời gian làm bài, tại máy tính được sử dụng để làm bài thi, thí sinh tạo một thư mục với tên là số báo danh của mình và đặt các file bài làm (file chương trình .CPP hoặc .PAS) vào thư mục vừa tạo. Sau đó tiến hành ghi nội dung thư mục này vào đĩa CD dưới sự giám sát và hướng dẫn của Cán bộ coi thi. Bài 1. ĐỐ VUI – QUIZ (6.0 điểm) Trong giờ Tin học, để tạo tinh thần thoải mái cho các học sinh, thầy giáo Hùng cùng các học sinh đã chơi một trò chơi. Luật chơi như sau, thầy Hùng sẽ viết ra giấy 1 xâu S gồm các chữ cái in thường trong bảng chữ cái tiếng Anh. Sau đó thầy Hùng sẽ hỏi q truy vấn dưới 2 dạng: - 1 pos c (1 ≤ pos ≤ độ dài xâu S, c là 1 chữ cái in thường trong bảng chữ cái tiếng Anh): các học sinh phải thay thế chữ cái ở vị trí pos bằng c. - 2 L R (1 ≤ L ≤ R ≤ độ dài xâu S): các học sinh phải trả lời xâu con S[L,R] của xâu S có bao nhiêu chữ cái khác nhau. Thầy Hùng còn giải thích thêm, một xâu con S[L,R] của xâu S là dãy các chữ cái S[L]S[L+1] S[R]. Ví dụ xâu S là “abcdefghi” thì xâu “abcd” , “cde”, “fg” là các xâu con của xâu S. Hãy giúp các học sinh trả lời các truy vấn loại 2 của thầy Hùng. Trang 1/4
2. + Dữ liệu vào: Đọc từ tệp QUIZ.INP gồm: - Dòng đầu tiên chứa xâu S. - Dòng thứ hai chứa số nguyên q. - q dòng tiếp theo chứa các truy vấn. Mỗi truy vấn có dạng như đã nêu ở trên và đảm bảo rằng có ít nhất 1 truy vấn thuộc loại 2. + Dữ liệu ra: Ghi ra tệp QUIZ.OUT chứa nội dung là với mỗi truy vấn loại 2 in ra số lượng chữ cái khác nhau trong xâu con được yêu cầu trong truy vấn này. Mỗi truy vấn trả lời trên một dòng. + Ví dụ: QUIZ.INP QUIZ.OUT abacaba 3 5 1 2 1 4 2 1 4 b 1 5 b 2 4 6 2 1 7 + Ràng buộc: - Có 30% số test tương ứng với 1 ≤ |푆| ≤ 103 , 1 ≤ 푞 ≤ 103 - Có 70% số test tương ứng với 103 < |푆| ≤ 105 , 103 < 푞 ≤ 105 Bài 2. KHU ĐẤT TỐT HÌNH VUÔNG - SQUARE (7.0 điểm) Bơ là một loại trái cây có giá trị dinh dưỡng cao và ngày càng được ưa chuộng. JOBS là một nông dân trẻ ở thị trấn SMALL. Để phát triển kinh tế, JOBS đã thuê một mảnh đất hình chữ nhật có kích thước M x N để trồng bơ trong một khoảng thời gian nhất định. Mảnh đất của JOBS được chia thành M x N ô đất, mỗi ô đất là một hình vuông có cạnh là 1 đơn vị. Tại mỗi ô đất JOBS đã tiến hành trồng một cây bơ con. Sau một thời gian, JOBS tự mình điều tra tình trạng phát triển của các cây bơ tại các ô đất đó. Một ô đất có cây bơ phát triển tốt được ghi nhận là 1, ngược lại một ô đất mà tại đó cây bơ kém phát triển hoặc chết được ghi nhận là 0 (Giả thiết rằng tình trạng chăm sóc, nước, phân bón là như nhau cho tất cả các cây). Sau khi có kết quả điều tra, JOBS đứng trước một vấn đề: “Cần biết kích thước (độ dài cạnh) của khu đất tốt hình vuông lớn nhất để chuẩn bị thuê lại sau khi hết thời hạn thuê mảnh đất ban đầu”. Một khu đất tốt là khu đất mà tại đó các cây bơ đều phát triển tốt (Các ô đất trong khu đất tốt đều mang giá trị 1). Em hãy giúp JOBS giải quyết vấn đề trên. + Dữ liệu vào: Tệp SQUARE.INP có nội dung như sau: - Dòng đầu tiên chứa hai số nguyên dương M, N (1 ≤ M, N ≤1000). - M dòng tiếp theo, mỗi dòng chứa N số mang giá trị 0 hoặc 1 ghi lại tình trạng các cây bơ tại các ô đất trong mảnh đất ban đầu. Trang 2/4
3. + Dữ liệu ra: Tệp SQUARE.OUT chứa kích thước (độ dài cạnh) của khu đất tốt hình vuông lớn nhất tìm được. + Ví dụ: SQUARE.INP SQUARE.OUT Giải thích 3 4 2 Hình vuông có góc trái 1 1 0 0 trên ô (1,1) hoặc hình vuông có góc trái trên ô 1 1 1 1 (2,3) là hình vuông có 1 0 1 1 kích thước lớn nhất tìm được. SQUARE.INP SQUARE.OUT Giải thích 5 6 3 Hình vuông có góc trái 1 1 0 0 1 1 trên ô (3,4) là hình vuông có kích thước lớn nhất tìm 1 1 1 0 1 1 được. 1 1 0 1 1 1 0 1 0 1 1 1 1 1 0 1 1 1 + Ràng buộc: - Có 40% số lượng Test tương ứng với: 1 ≤ M, N < 100 - Có 60% số lượng Test tương ứng với: 100 ≤ M, N ≤ 1000 Bài 3. MÊ CUNG - MAZE (7 điểm) Roger đang lập trình một trò chơi khá thú vị để thử thách người chơi là Peter. Trong trò chơi này có một mê cung rộng lớn với N điểm dừng và M con đường hai chiều nối giữa các điểm dừng. Mê cung mà Roger tạo ra luôn đảm bảo giữa hai điểm dừng luôn tồn tại một đường đi trực tiếp hoặc gián tiếp nối với chúng. Để tăng độ thú vị cho trò chơi, trên mỗi con đường trực tiếp nối giữa hai điểm dừng có thể đặt một con quái vật (Boss). Nếu người chơi đi qua những con đường có đặt Boss, nhiệm vụ của họ là chuẩn bị chiến thuật và vũ khí để chiến đấu và chiến thắng Boss. Tại thời điểm bắt đầu của trò chơi, Roger sẽ chọn điểm dừng xuất phát là S và điểm dừng kết thúc là T. Sau đó, nhiệm vụ của Peter là sẽ xuất phát từ điểm dừng S, đi qua các con đường để đến được điểm dừng T và Roger cần phải đặt những con Boss trên những con đường trực tiếp, nằm trên đường đi từ S đến T, mà Peter chắc chắn phải đi qua. Roger luôn tìm được cách chọn S và T sao cho anh ta có thể đặt được nhiều con Boss nhất. Hãy giúp Peter xác định số con Boss mà Roger đã đặt. Trang 3/4
4. + Dữ liệu vào: Đọc từ tệp MAZE.INP gồm: - Dòng đầu tiên chứa hai số nguyên N và M (2 ≤ N ≤ 3.105, 1 ≤ M ≤ 3.105) là số điểm dừng và số con đường trong mê cung. - M dòng tiếp theo, mỗi dòng gồm hai số x và y ( 1 ≤ , ≤ , ≠ ) mô tả đường đi nối giữa hai điểm dừng. - Bộ dữ liệu được đảm bảo rằng không có hai điểm dừng nào được kết nối bởi hai hoặc nhiều hơn hai con đường và mỗi điểm dừng có thể đi đến tất cả các điểm dừng còn lại. + Dữ liệu ra: Ghi ra tệp MAZE.OUT một số nguyên duy nhất là số lượng con Boss mà Roger đã đặt. + Ví dụ: MAZE.INP MAZE.OUT Hình minh họa mê cung Giải thích 5 5 2 Roger chọn S=4, 1 2 T=5 thì để đi từ S 4 1 2 5 đến T Peter buộc 2 3 phải đi qua 2 đoạn 3 1 đường là (4,1) và (2,5). 4 1 3 5 2 + Ràng buộc: - Có 20% số test tương ứng với = ― 1 - Có 80% số test tương ứng với 2 ≤ ≤ 3.105, 1 ≤ ≤ 3.105 ----------HẾT---------- Họ và tên thí sinh........................................................Số báo danh:................................................... Họ và tên, chữ kí của CBCT1:....................................Họ và tên, chữ kí của CBCT2:....................... * Lưu ý: - Thí sinh không được sử dụng tài liệu trong lúc làm bài. - Cán bộ coi thi không giải thích gì thêm. Trang 4/4