Đề thi chọn đội tuyển dự thi học sinh giỏi Quốc gia năm 2019 môn Tin học Lớp 12 - Sở GD&ĐT tỉnh Bắc Ninh

Nội dung text: Đề thi chọn đội tuyển dự thi học sinh giỏi Quốc gia năm 2019 môn Tin học Lớp 12 - Sở GD&ĐT tỉnh Bắc Ninh

1. UBND TỈNH BẮC NINH ĐỀ THI CHỌN ĐỘI TUYỂN SỞ GIÁO DỤC VÀ ĐÀO TẠO DỰ THI HỌC SINH GIỎI QUỐC GIA THPT NĂM 2019 Môn thi: Tin học ĐỀ CHÍNH THỨC Thời gian làm bài: 180 phút (không kể thời gian giao đề) Ngày thi thứ nhất: 04 tháng 10 năm 2018 (Đề thi gồm 03 trang) Stt Tên bài Tên file INPUT OUTPUT Điểm 1 Luyện thi PRACTICE.* PRACTICE.INP PRACTICE.OUT 7 2 Trò chơi tìm số CTIMSO.* CTIMSO.INP CTIMSO.OUT 7 3 Cấm đường DISENTR.* DISENTR.INP DISENTR.OUT 6 Chú ý: * tương ứng với phần mở rộng phần mềm thí sinh sử dụng Bài 1. Luyện thi Để chuẩn bị cho kì thi chọn đội tuyển HSG sắp tới, nhà trường quyết định giao cho học sinh n bộ đề (1 ≤ n ≤ 105) để các học sinh tự đánh giá kỹ năng của mình. Các đề được đánh số từ 1 đến n. Mỗi bài tập nhằm rèn luyện một số kỹ năng cho học sinh để tham gia kỳ thi sắp tới. Nhằm định hướng cho quá trình tự luyện tập được hiệu quả, mỗi bộ đề có một yêu cầu tối thiểu về trình độ kỹ năng. Để giải được bộ đề thứ i, bạn cần có trình độ kỹ năng tối thiểu là i.a Điều này có nghĩa là học sinh có thể làm được đề thứ i khi và chỉ khi có trình độ kỹ năng bằng hoặc lớn hơni .a Nếu 9 giải được bộ đề thứ i thì trình độ kỹ năng của học sinh sẽ tăng thêm một lượng là ib (1 ≤ ai, bi≤ 10 ). Giả sử ban đầu, trình độ kỹ năng của bạn trước khi làm đề là c (0 ≤ c ≤ 109). Các bộ đề có thể được làm theo trình tự bất kỳ tùy chọn. Ví dụ: Với trình độ kỹ năng ban đầu n= 4, c=1 và các giá trị a i, bi tương ứng là (1, 10), (21, 5), (1, 10), (100, 100), bạn sẽ giải bộ đề 1, sau đó làm bộ đề 3 và cuối cùng làm bộ đề 2. Như vậy bạn sẽ làm được tất cả là 3 bài. Yêu cầu: Cho các số nguyên n, c và các cặp giá trị ai, bi (1 ≤ i ≤ n). Hãy xác định số lượng bộ đề tối đa có thể được giải. Dữ liệu: Nhập từ file văn bản PRACTICE.INP: Dòng đầu tiên chứa 2 số nguyên n và c. Dòng thứ i trong n dòng tiếp theo (1 ≤ i ≤ n) chứa 2 số nguyên ai và bi. Các số trên cùng một dòng được ghi cách nhau bởi 1 khoảng trắng. Dữ liệu: Ghi ra file văn bản PRACTICE.OUT: Là một số nguyên xác định số lượng bài tối đa có thể được giải. Ví dụ: PRACTICE.INP PRACTICE.OUT 4 1 3 1 10 21 5 1 10 100 100 1
2. Bài 2. Trò chơi tìm số Tú và Trà rất thích chơi với những con số. Hôm nay, Tú đố Trà bài toán như sau: Cho 2 số nguyên dương N và M. Nhiệm vụ của Trà là tìm số nguyên dương K lớn nhất có thể sao cho N! chia hết cho MK. Bài toán hơi khó đối với Trà và Trà tìm đến các bạn chuyên tin, hãy lập trình giúp bạn ấy. Dữ liệu: Vào từ file văn bản CTIMSO.INP: Dữ liệu trên một dòng là 2 số N, M cách nhau bởi dấu cách, 2 ≤ N, M ≤ 231. Kết quả: Ghi ra file văn bản CTIMSO.OUT: Số K duy nhất là kết quả của bài toán. Ràng buộc: Có 30% số lượng test: 2 ≤ N ≤ 20, 2 ≤ M ≤ 231; Có 30% số lượng test: N là lũy thừa của 2, M = 2; 40% số lượng test còn: 2 ≤ N, M ≤ 231; Ví dụ: CTIMSO.INP CTIMSO.OUT 6 8 1 8 8 2 Bài 3. Cấm đường Hệ thống giao thông thành phố Bắc Ninh gồm 푛 nút giao thông đánh số 1,2, , n kết nối bởi m đường hai chiều, mỗi con đường tốn thời gian di chuyển nhất định, lượng thời gian này đúng với mọi phương tiện giao thông vì thành phố quy định tốc độ di chuyển cố định trong toàn hệ thống. Hàng ngày Bắc cần di chuyển từ nút giao thông s đến nút giao thông t. Tuy nhiên, khi chuẩn bị xuất phát thì cậu mới biết hôm nay có đoàn ngoại giao nước ngoài đến làm việc nên một số con đường sẽ bị chặn tạm thời. Cụ thể, hành trình của đoàn ngoại giao là (푤1, 푤2, , 푤 ) hành trình này đảm bảo thông suốt và không có con đường nào xuất hiện quá một lần. Đối với mỗi con đường trong hành trình, tạm kí hiệu là ( , ), kể từ khi đoàn ngoại giao xuất hiện ở cho đến khi ra khỏi , không có phương tiện nào được phép tiến vào cả từ lẫn , các phương tiện có mặt trên đường từ trước đó vẫn có thể tham gia giao thông như bình thường. Bắc xuất phát muộn hơn đoàn ngoại giao phút, hãy xác định thời điểm cậu đến đích sớm nhất có thể. Dữ liệu: Vào từ file văn bản DISENTR.INP Dòng 1: Hai số nguyên 푛, (2 ≤ 푛 ≤ 103 ; 2 ≤ ≤ 104). Dòng 2: Bốn số nguyên 푠, t, , (0 ≤ , ≤ 103). Dòng 3: số nguyên 푤1, 푤2, , 푤 . Dòng 4 đến dòng + 3: Mỗi dòng ba số nguyên , 푣, 푙 (1 ≤ 푙 ≤ 10 3 ) thể hiện một con đường nối hai nút giao thông , 푣 tốn thời gian di chuyển 푙 phút, không có cặp nút giao thông nào được nối bởi nhiều hơn một con đường. 2
3. Kết quả: Ghi ra file văn bản DISENTR.OUT Một số nguyên dương là số phút di chuyển tối thiểu của Bắc. Ví dụ DISENTR.INP DISENTR.OUT 6 5 21 1 6 20 4 5 3 2 4 1 2 2 2 3 8 2 4 3 3 6 10 3 5 15 8 9 40 1 5 5 5 1 2 3 4 5 1 2 8 2 7 4 2 3 10 6 7 40 3 6 5 6 8 3 4 8 4 4 5 5 3 4 23 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 : 3