onthicaptoc.com
SỞ GIÁO DỤC VÀ ĐÀO TẠO
TỈNH QUẢNG NAM
ĐỀ CHÍNH THỨC
(Đề thi có 04 trang)
KỲ THI HỌC SINH GIỎI CẤP TỈNH THPT ĐỢT 1
NĂM HỌC 2022 – 2023
Môn thi: TIN HỌC
Thời gian: 180 phút (không kể thời gian giao đề)
Ngày thi: 07/10/2022
TỔNG QUAN ĐỀ THI
Bài
Tên bài
Tên file
chương trình
Tên file
dữ liệu vào
Tên file
kết quả
Điểm
Thời gian
Bộ nhớ
1
Bộ số học
SOHOC.*
SOHOC.INP
SOHOC.OUT
5
1s
1024M
2
Đếm sỏi
DEMSOI.*
DEMSOI.INP
DEMSOI.OUT
5
1s
1024M
3
Sóc ăn hạt dẻ
HATDE.*
HATDE.INP
HATDE.OUT
5
1s
1024M
4
Hệ thống xe Bus
SBUS.*
SBUS.INP
SBUS.OUT
5
1s
1024M
Lưu ý: Dấu * trong phần tên chương trình tương ứng với ngôn ngữ lập trình mà thí sinh sử dụng, ví dụ PAS, CPP, …
Bài 1. Bộ số học
Cô giáo Hoa đang giảng bài : “Ước số và bội số là một trong những khái niệm quen thuộc trong số học. Với 2 số nguyên A và B bất kỳ, nếu A chia hết cho B, ta nói A là bội số của B và B là ước số của A. Với một bộ K số nguyên dương a1, a2,…, aK bất kỳ, ước số chung lớn nhất của chúng là số nguyên X lớn nhất thỏa mãn mọi ai là bội số của X. Tương tự, bội số chung nhỏ nhất của bộ số này là số nguyên Y nhỏ nhất thỏa mãn mọi ai là ước số của Y”. Bất chợt học sinh Phát trong lớp nghĩ ra một bài toán: “Cho 2 dãy số nguyên p1, p2,…, pM và q1, q2,…, qN. Đặt P= p1*p2*…*pM và Q= q1*q2*…*qN. Đếm số bộ K số nguyên có ước số chung lớn nhất là P và bội số chung nhỏ nhất là Q”.
Yêu cầu: Các bạn là học sinh tuyển chọn của trường hãy giúp Phát giải bài toán này nhé.
Dữ liệu vào: Từ tệp văn bản SOHOC.INP gồm:
* Dòng đầu tiên gồm ba số nguyên dương M, N, K;
* Dòng thứ hai gồm M số nguyên dương p1,p2,…, pM;
* Dòng thứ ba gồm N số nguyên dương q1, q2,…, qN.
Các số trên một dòng của tệp dữ liệu vào được ghi cách nhau bởi dấu cách.
Kết quả: Ghi ra tệp văn bản SOHOC.OUT gồm: Một số nguyên duy nhất là số bộ số thỏa mãn. Kết quả của bài toán chỉ cần in ra phần dư khi chia cho 109+9.
Ví dụ:
SOHOC.INP
SOHOC.OUT
Giải thích
1 2 2
1
2 3
4
P=1; Q=6. 4 bộ 2 số thỏa mãn điều kiện là (1,6), (2,3), (3,2), (6,1).
SOHOC.INP
SOHOC.OUT
Giải thích
2 1 2
2 5
131
0
P=10; Q=131. Do Q không chia hết cho P nên dễ thấy không tồn tại bộ số nào thỏa mãn.
Ràng buộc: Trong tất cả bộ test: K≤109, các số còn lại trong tệp dữ liệu vào có giá trị tuyệt đối không quá 106.
* Có 10% số test ứng với 10% số điểm của bài có M=N=K=1
* Có 30% số test ứng với 30% số điểm của bài có max(P, Q) ≤ 3x103 và K=2;
* Có 20% số test ứng với 20% số điểm của bài có max(P, Q) ≤ 106 và K=2;
* Có 20% số test ứng với 20% số điểm của bài có max(M, N) ≤ 5x103 và K=2;
* Có 20% số test khác ứng với 20% số điểm còn lại của bài.
Bài 2. Đếm sỏi
Cô giáo dẫn một nhóm học sinh tới một sân gạch rộng của trường để vừa chơi vừa học. Sân gạch là một mặt phẳng hai chiều. Mỗi viên gạch là một ô vuông 1x1 đơn vị. Cô giáo nghĩ ra một trò chơi như sau: mỗi lượt cô sẽ đưa ra 4 số nguyên x1, y1, x2, y2 là tọa độ trái dưới (x1, y1) và phải trên (x2, y2) của một hình chữ nhật. Cô sẽ giao nhiệm vụ cho một đứa trẻ trong nhóm học sinh đi rải sỏi vào các viên gạch nằm trong hình chữ nhật đó, mỗi viên gạch rải 1 viên sỏi.
Yêu cầu: Hãy giúp cô giáo trả lời một trong hai câu hỏi sau:
* Câu hỏi 1: Sau N lượt như vậy, hãy cho cô biết số lượng viên gạch đang có K viên sỏi.
* Câu hỏi 2: Nếu cho các bạn học sinh rải thêm tối đa hai lượt nữa sao cho hai hình chữ nhật này không được giao nhau. Hãy giúp cô giáo lựa chọn rải sỏi sao cho số viên gạch có K viên sỏi là nhiều nhất.
Dữ liệu vào: Từ tệp văn bản DEMSOI.INP có cấu trúc như sau:
* Dòng đầu tiên chứa số nguyên M (1 ≤ M ≤ 2), yêu cầu trả lời câu hỏi 1 hoặc 2;
* Dòng thứ 2 chứa hai số nguyên N và K (1 ≤ K ≤ N ≤ 105);
* N dòng tiếp theo, mỗi dòng mô tả một lượt gồm bốn số nguyên x1, y1, x2, y2 là tọa độ trái dưới (x1, y1) và phải trên (x2, y2) của hình chữ nhật.
Kết quả: Ghi ra tệp văn bản DEMSOI.OUT: Một số nguyên là kết quả của bài toán khi trả lời một trong hai câu hỏi ứng với M như sau:
* Nếu M = 1: In số lượng viên gạch đang có K viên sỏi;
* Nếu M = 2: In số lượng viên gạch nhiều nhất có K viên sỏi sau khi rải thêm tối đa 2 lượt nữa.
Ví dụ:
DEMSOI.INP
DEMSOI.OUT
Hình vẽ
1
3 2
1 1 5 5
4 4 7 6
3 3 8 7
8
DEMSOI.INP
DEMSOI.OUT
Hình vẽ
2
3 2
1 1 4 4
3 3 7 6
2 2 8 7
26
Ràng buộc:
* Có 30% số test ứng với 30% số điểm của bài có M = 1 và 0 ≤ x, y ≤ 200;
* Có 20% số test ứng với 20% số điểm của bài có M = 1 và 0 ≤ x, y ≤ 1000;
* Có 20% số test ứng với 20% số điểm của bài có M = 2, N ≤ 100 và 0 ≤ x, y ≤ 200;
* Có 30% số test ứng với 30% số điểm của bài có M = 2, N ≤ 105 và 0 ≤ x, y ≤ 200.
Bài 3. Sóc ăn hạt dẻ
An có nuôi một con sóc, nó rất thích ăn hạt dẻ. An đã huấn luyện cho nó chơi trò chơi như sau: An chuẩn bị N cái khay, các khay cách đều nhau một khoảng cách nhất định. Ban đầu mỗi khay đều đựng một số hạt dẻ. Con sóc sẽ phải mang tất cả hạt dẻ từ khay i sang khay j (khay i sẽ trống sau lần di chuyển của sóc). Nó cứ thực hiện như vậy cho đến khi nào còn đúng K khay có chứa hạt dẻ. Lúc đó nó sẽ được ăn tất cả số hạt dẻ ở trong các khay. Để sóc có thể mang tất cả hạt dẻ từ khay i sang khay j, nó phải tiêu tốn mất Cij năng lượng.
Yêu cầu: Hãy tìm cách giúp con sóc di chuyển hạt dẻ theo quy tắc của trò chơi để tổng năng lượng tiêu tốn là nhỏ nhất.
Dữ liệu vào: Từ tệp văn bản HATDE.INP có cấu trúc như sau:
* Dòng đầu chứa 2 số nguyên dương N, K (1 ≤ K ≤ N ≤ 20).
* N dòng sau, mỗi dòng chứa N số nguyên dương thể hiện mảng năng lượng tiêu tốn C (0 ≤ Cij ≤ 105), trong đó dòng thứ i cột thứ j chứa giá trị Cij. Dĩ nhiên là Cii=0 và 1 ≤ i, j ≤ N.
Kết quả: Ghi ra tệp văn bản HATDE.OUT
* Ghi ra năng lượng tiêu tốn nhỏ nhất của con sóc để thực hiện yêu cầu trên.
Ví dụ:
HATDE.INP
HATDE.OUT
Giải thích
3 3
0 1 1
1 0 1
1 1 0
0
Không cần di chuyển hạt dẻ từ khay này sang khay kia. Vì số khay chứa hạt dẻ ban đầu đã bằng K.
5 2
0 5 4 3 2
7 0 4 4 4
3 3 0 1 2
4 3 1 0 5
4 5 5 5 0
5
Ta có 5 khay, ta sẽ di chuyển từ khay 4 sang 3 (C43 = 1), sau đó di chuyển từ khay 3 sang 5 ( C35 = 2), và cuối cùng di chuyển từ 1 sang 5 ( C15 = 2).
Tổng chi phí là 1 + 2 + 2= 5.
Còn hai khay chứa hạt dẻ (khay 2 và 5).
Ràng buộc:
* Có 40% số test ứng với 40% số điểm của bài có N ≤ 10;
* Có 30% số test ứng với 30% số điểm của bài có N ≤ 15;
* Có 30% số test khác ứng với 30% số điểm còn lại của bài có N ≤ 20.
Bài 4. Hệ thống xe Bus
Cát Vàng là một điểm du lịch nổi tiếng, tại đây có một hệ thống giao thông chạy bằng xe Bus năng lượng để bảo vệ môi trường và thuận tiện. Từ hai địa điểm bất kỳ có thể đi bằng xe Bus và chỉ có một cách đi duy nhất. Dễ thấy: Hệ thống xe Bus tạo thành một cây: các địa điểm xe Bus là nút V và các tuyến đường thuộc cạnh E của đồ thị G=(V,E).
Ban đầu, giữa hai địa điểm bất kỳ có ít nhất một tuyến xe Bus chạy. Nhưng với sự phát triển của công ty và các loại phương tiện giao thông khác một số tuyến bị hủy bỏ vì gần như không còn du khách nào đi qua. Cho nên công ty quyết định tháo dỡ những đoạn đường này.
Bài toán đặt ra: Cho số nguyên dương N là số địa điểm xe Bus, các địa điểm được đánh số từ 1 tới N. Có N-1 đoạn đường nối trực tiếp từ ui tới vi và ngược lại (). Cho M số tuyến đường đang hoạt động và M cặp số (x,y), mỗi cặp số xác định một tuyến đường từ x tới y theo đường ngắn nhất.
Yêu cầu: Với bài toán đặt ra hãy xác định số các đoạn đường cần tháo dỡ.
Dữ liệu vào: Từ tệp văn bản SBUS.INP gồm:
* Dòng đầu tiên là số nguyên dương T (T là số bộ dữ liệu trong tệp);
* Mỗi bộ dữ liệu gồm:
* Dòng đầu tiên ghi số nguyên dương ;
* N-1 dòng tiếp theo, mỗi dòng ghi hai số u, v mô tả đường nối giữa hai địa điểm u và v (1 ≤ u, v ≤ N) các số cách nhau bởi dấu cách;
* Dòng tiếp theo ghi số M
Mỗi dòng trong M dòng tiếp theo chứa hai số nguyên x, y (1 ≤ x, y ≤ N) các số cách nhau bởi dấu cách;
Kết quả: Ghi ra tệp văn bản SBUS.OUT gồm: T dòng mỗi dòng là kết quả thứ tự tương ứng với thứ tự bộ dữ liệu trong tệp vào (số các đoạn đường cần tháo dỡ).
Ví dụ:
SBUS.INP
SBUS.OUT
Hình vẽ
1
5
1 2
2 3
2 4
2 5
2
2 4
1 5
1
SBUS.INP
SBUS.OUT
Hình vẽ
1
5
1 2
2 3
3 5
5 4
1
2 4
1
Ràng buộc:
* Có 60% số test ứng với 60% số điểm của bài có N, M ≤ 3x103 và T=1;
* Có 20% số test ứng với 20% số điểm của bài có N, M ≤ 3x104 và T=1;
* Có 20% số test khác ứng với 20% số điểm còn lại của bài có N, M ≤ 3x104 và T ≤ 5.
--------------- 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: ……........
onthicaptoc.com

onthicaptoc.com De thi HSG Tin chuyen 12 Quang Nam 2023