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

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

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 ĐỀ DỰ BỊ 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 Độ đẹp dãy số - 1 MAXDIFF.* MAXDIFF.INP MAXDIFF.OUT 2s MaxDiff Dãy số đẹp - 2 BEAUTARR.* BEAUTARR.INP BEAUTARR.OUT 2s BeautArr 3 Đường đi - DFS DFS.* DFS.INP DFS.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 .PAS hoặc .CPP) 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. ĐỘ ĐẸP DÃY SỐ - MAXDIFF (6.0 điểm) Cho một dãy số nguyên A gồm N phần tử. Các phần tử trong dãy được sắp xếp theo trình tự tăng dần, tức là Ai ≤ Ai+1 với mọi 1 ≤ i ≤ N. Ta định nghĩa độ đẹp của dãy A là khoảng cách lớn nhất giữa hai phân từ liên tiếp bất kì trong dãy. Nói cách khác, độ đẹp của dãy A là giá trị Ai+1 - Ai với mọi 1 ≤ i < N. Hãy xóa một phần tử bất kì trong dãy A sao cho độ đẹp của dãy nhận được là lớn nhất có thể. + Dữ liệu vào: Tệp MaxDiff.inp có nội dung sau: - Dòng đầu tiên gồm số nguyên N (3 ≤ N≤ 1000) là số phần tử trong dãy. 9 - Dòng thứ hai gồm N số nguyên A1, A2, . . . , An (1 ≤ Ai ≤ 10 ) là giá trị của N phần tử trong dãy A.
2. + Dữ liệu ra: Tệp MaxDiff.out chứa độ đẹp lớn nhất của dãy A sau khi xóa đi một phần tử bất kì. + Ví dụ: MaxDiff.inp MaxDiff.out Giải thích 4 3 Xóa đi phần tử thứ 2 trong dãy A. Dãy 2 4 5 6 sau khi xóa là [2, 5, 6] và có độ đẹp là 3. MaxDiff.inp MaxDiff.out Giải thích 5 2 Ta sẽ xóa đi phần tử thứ 4 trong dãy A. 1 2 2 3 4 Dãy sau khi xóa là [1, 2, 2, 4] và có độ đẹp là 2. MaxDiff.inp MaxDiff.out Giải thích 5 0 Xóa đi bất kì phần tử nào thì độ đẹp của 1 1 1 1 1 dãy bao giờ cũng bằng 0 + Ràng buộc: Không. Bài 2. DÃY SỐ ĐẸP - BEAUTARR (7.0 điểm) Một dãy số được gọi là “đẹp” nếu mọi phần tử trong dãy đó đều có số lần xuất hiện không vượt quá 2. Ví dụ: • [1, 5, 2, 4, 3], [6, 10, 10, 6] và [9] là các dãy số đẹp. • [3, 3, 3, 4, 4], [7, 7, 8, 7] và [100, 100, 100] không phải là các dãy đẹp. Cho dãy A độ dài N , hãy đếm số cặp chỉ số (l, r) với 1≤ l ≤ r ≤ N sao cho dãy con Al, Al+1, . . . , Ar là dãy đẹp. + Dữ liệu vào: Tệp BeautArr.inp có nội dung như sau: - Dòng đầu tiên: gồm số nguyên N (1≤ N ≤ 500000) – độ dài dãy A. - Dòng thứ hai: gồm N số nguyên A1, A2, . . . AN (1 ≤ Ai ≤ 500000) – các phần tử của dãy A. + Dữ liệu ra: Tệp BeautArr.out chứa một số nguyên duy nhất là số cặp chỉ số (l,r) thõa mãn yêu cầu đề bài.
3. + Ví dụ: BeautArr.inp BeautArr.out Giải thích 4 9 * Có 9 cặp chỉ số thõa mãn yêu cầu đề bài: 1 2 1 1 • l = 1, r = 1 (dãy [1]) • l = 1, r = 1 (dãy [1]) • l = 1, r = 2 (dãy [1, 2]) • l = 1, r = 3 (dãy [1, 2, 1]) • l = 2, r = 2 (dãy [2]) • l = 2, r = 3 (dãy [2, 1]) • l = 2, r = 4 (dãy [2, 1, 1]) • l = 3, r = 3 (dãy [1]) • l = 4, r = 4 (dãy [1]) BeautArr.inp BeautArr.out Giải thích 6 18 * Có 18 cặp chỉ số thõa mãn yêu cầu đề bài. 4 5 4 5 4 5 + Ràng buộc: - Có 20% bộ Test ứng với: N ≤ 50, Ai ≤ 50 - Có 15% bộ Test ứng với: N ≤ 500, Ai ≤ 500 - Có 15% bộ Test ứng với: N ≤ 5000, Ai ≤ 5000 - Có 50% bộ Test ứng với: Không có ràng buộc gì thêm Bài 3. ĐƯỜNG ĐI – DFS (7.0 điểm) Thị trấn NEW LAND có N ngôi làng (1 ≤ N ≤ 300000), có M con đường nối giữa các ngôi làng (1 ≤ M ≤ 500000). Hiện tại, giữa hai ngôi làng U, V (1 ≤ U,V ≤ N) có thể tồn tại đường đi trực tiếp, gián tiếp hoặc không tồn tại đường đi. Đường đi trực tiếp giữa các ngôi làng là đường đi hai chiều. Alice là một công dân sinh sống trong ngôi làng thứ 1 ở thị trấn NEW LAND. Bà ta mới được bầu làm thị trưởng. Bà ta cần giải quyết một vấn đề: “Tồn tại đường đi trực tiếp hoặc gián tiếp từ ngôi làng thứ 1 đến tất cả các ngôi làng còn lại trong thị trấn?” Em hãy giúp bà ta giải quyết vấn đề trên. + Dữ liệu vào: Tệp Dfs.inp có nội dung như sau: - Dòng đầu chứa hai số tự nhiên N, M.
4. - M dòng tiếp theo, mỗi dòng chứa hai số nguyên u, v thể hiện có một cạnh nối đỉnh u với đỉnh v (1 ≤ u, v ≤ N; u ≠ v) + Dữ liệu ra: Tệp Dfs.out gồm một số duy nhất 1 (tồn tại đường đi) hoặc 0 (không tồn tại đường đi) + Ví dụ: Dfs.inp Dfs.out Minh họa đồ thị 10 12 1 1 10 10 2 10 3 2 4 4 5 5 2 3 6 6 7 7 3 7 8 8 9 9 7 + Ràng buộc: - Có 60% bộ Test ứng với: N < 5000, M < 5000 - Có 40% bộ Test ứng với: N ≥ 5000, M ≥ 5000 ----------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.