SỞ GIÁO DỤC VÀ ĐÀO TẠO

TỈNH QUẢNG NAM

(Đề 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 a₁, a₂,…, a_Kbấ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 a_i 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 a_i 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 p₁, p₂,…, p_Mvà q₁, q₂,…, q_N. Đặt P= p₁*p₂*…*p_M và Q= q₁*q₂*…*q_N. Đế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 p₁,p₂,…, p_M;

- Dòng thứ ba gồm N số nguyên dương q₁, q₂,…, q_N.

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 10⁹+9.

Ví dụ:

SOHOC.INP

SOHOC.OUT

Giải thích

1 2 2

2 3

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

Ràng buộc: Trong tất cả bộ test: K≤10⁹, các số còn lại trong tệp dữ liệu vào có giá trị tuyệt đối không quá 10⁶.

· 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) ≤ 3x10³ và K=2;

· Có 20% số test ứng với 20% số điểm của bài có max(P, Q) ≤ 10⁶ và K=2;

· Có 20% số test ứng với 20% số điểm của bài có max(M, N) ≤ 5x10³ 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 x₁, y₁, x₂, y₂ là tọa độ trái dưới (x₁, y₁) và phải trên (x₂, y₂) 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 ≤ 10⁵);

- N dòng tiếp theo, mỗi dòng mô tả một lượt gồm bốn số nguyên x₁, y₁, x₂, y₂ là tọa độ trái dưới (x₁, y₁) và phải trên (x₂, y₂) 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 ≤ 10⁵ 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 C_ij 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 ≤ C_ij ≤ 10⁵), trong đó dòng thứ i cột thứ j chứa giá trị C_ij. Dĩ nhiên là C_ii=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

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

Ta có 5 khay, ta sẽ di chuyển từ khay 4 sang 3 (C₄₃ = 1), sau đó di chuyển từ khay 3 sang 5 ( C₃₅= 2), và cuối cùng di chuyển từ 1 sang 5 ( C₁₅ = 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ừ u_i tới v_i 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 ≤ 3x10³ và T=1;

· Có 20% số test ứng với 20% số điểm của bài có N, M ≤ 3x10⁴ 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 ≤ 3x10⁴ 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: ……........

Đề Thi HSG Tin 12 Chuyên Sở Giáo Dục Quảng Nam 2022 - 2023

2 giây trước

Xem tiếp toàn bộ tài liệu