HSG THPT Thanh Hóa 2023-2024

SỞ GIÁO DỤC VÀ ĐÀO TẠO THANH HÓA ĐỀ CHÍNH THỨC

KÌ THI CHỌN HỌC SINH GIỎI CẤP TỈNH Năm học 2023 - 2024
Môn thi: Tin học - THPT
Thời gian làm bài: 150 phút, không kể thời gian phát đề
(Đề thi có 3 trang, gồm 5 câu)

---

Tổng quan bài thi

Câu	Tên bài	Tệp chương trình	Tệp dữ liệu vào	Tệp kết quả ra
Câu 1	Chia hết cho 7	CAU1.*	CAU1.INP	CAU1.OUT
Câu 2	Hạnh phúc	CAU2.*	CAU2.INP	CAU2.OUT
Câu 3	Bông tuyết	CAU3.*	CAU3.INP	CAU3.OUT
Câu 4	Khoá số	CAU4.*	CAU4.INP	CAU4.OUT
Câu 5	Phần dư	CAU5.*	CAU5.INP	CAU5.OUT

Dữ liệu vào là đúng đắn, không cần phải kiểm tra. Trong các tệp dữ liệu vào/ra, nếu dữ liệu trên cùng một dòng thì được cách nhau bởi ít nhất 1 dấu cách. Dấu (*) trong tên tệp chương trình biểu thị đuôi tệp tùy thuộc vào ngôn ngữ lập trình sử dụng là CPP hoặc PY.

Câu 1. Chia hết cho 7 (6 điểm)

Một số nguyên dương X gồm n chữ số dạng a₁a₂…a_n có trọng số S(X) được tính theo công thức:

S(X) = 1 × a₁ + 2 × a₂ + … + n × a_n.

Ví dụ, X = 2025 có trọng số là S(2025) = 1 × 2 + 2 × 0 + 3 × 2 + 4 × 5 = 28.

Yêu cầu: Cho số nguyên dương X trong đó có một chữ số bị mờ biểu diễn bằng dấu ’?’. Hãy tìm chữ số có giá trị nhỏ nhất trong các chữ số từ ‘0’ đến ‘9’ để thay vào vị trí dấu ’?’ sao cho S(X) chia hết cho 7.

Dữ liệu: Vào từ tệp CAU1.INP chứa số nguyên dương X (X < 10¹⁰⁰) trong đó có 1 chữ số bị mờ biểu diễn bằng dấu ’?’.

Kết quả: Ghi ra tệp CAU1.OUT một chữ số nhỏ nhất có thể thay vào dấu ’?’, nếu không tồn tại chữ số nào thoả mãn thì ghi −1. Số X không được chứa chữ số ‘0’ vô nghĩa ở đầu.

Ví dụ:

CAU1.INP	CAU1.OUT	Giải thích
202?	5	Số 2025 có S(2025) = 28 chia hết cho 7.
?7	7	Vì dấu ’?’ đứng đầu không thể thay bằng chữ số 0, nên X = 77 có S(77) = 21 chia hết cho 7.
800000?	-1	Không có chữ số nào thay thế dấu ’?’ thoả mãn S(X) chia hết cho 7.

Câu 2. Hạnh phúc (5 điểm)

Một trường học có n học sinh, học sinh thứ i có độ hạnh phúc h_i. Nếu hai học sinh i và j bắt tay nhau (i ≠ j, 1 ≤ i, j ≤ n) sẽ tạo ra độ hạnh phúc là h_i × h_j. Học sinh i và học sinh j chỉ được tính là bắt tay nhau một lần duy nhất.

Yêu cầu: Tính tổng độ hạnh phúc của toàn trường nếu tất cả học sinh đều bắt tay nhau.

Dữ liệu: Vào từ tệp CAU2.INP gồm:

• Dòng đầu là số nguyên n là số học sinh toàn trường (2 ≤ n ≤ 30000);
• Dòng tiếp theo chứa n số nguyên dương h₁, h₂, …, h_n lần lượt là độ hạnh phúc của từng học sinh (0 < h_i ≤ 30000).

Kết quả: Ghi ra tệp CAU2.OUT một số duy nhất là tổng độ hạnh phúc của toàn trường nếu tất cả học sinh đều bắt tay nhau.

Ví dụ:

CAU2.INP	CAU2.OUT	Giải thích
4 2 5 1 2	33	Tổng độ hạnh phúc là 2×5 + 2×1 + 2×2 + 5×1 + 5×2 + 1×2 = 33

Ràng buộc:

• Có 80% số test ứng với 80% số điểm của bài có n, h_i ≤ 3000;
• Có 20% số test ứng với 20% số điểm của bài có n, h_i ≤ 30000.

Câu 3. Bông tuyết (4 điểm)

Vương quốc Băng giá có n² bông tuyết được đánh số từ 1 đến n². Bông tuyết thứ i có khối lượng a_i. Elsa chạm vào một bông tuyết bất kì có khối lượng w thì lập tức tất cả các bông tuyết có cùng khối lượng w sẽ tan biến.

Yêu cầu: Cho biết khối lượng của n² bông tuyết. Xác định tổng khối lượng lớn nhất của các bông tuyết chưa tan.

Dữ liệu: Vào từ tệp văn bản CAU3.INP gồm:

• Dòng thứ nhất chứa số nguyên dương n;
• Dòng thứ hai chứa n² số nguyên dương a₁, a₂, …, a(n²) (0 < n ≤ 1500, 0 < a_i ≤ 10⁹, 1 ≤ i ≤ n²).

Kết quả: Ghi ra tệp CAU3.OUT một số nguyên duy nhất là giá trị lớn nhất của tổng khối lượng các bông tuyết chưa tan.

Ví dụ:

CAU3.INP	CAU3.OUT	Giải thích
3 1 2 4 1 1 1 1 1 2	10	- Chạm vào bông tuyết có khối lượng w = 1, tổng khối lượng chưa tan là 2 + 4 + 2 = 8. - Chạm vào bông tuyết có khối lượng w = 2, tổng khối lượng chưa tan là 1 + 4 + 1 + 1 + 1 + 1 + 1 = 10. - Chạm vào bông tuyết có khối lượng w = 4, tổng khối lượng chưa tan là 1 + 2 + 1 + 1 + 1 + 1 + 1 + 2 = 10. Vậy tổng khối lượng lớn nhất chưa tan là 10.

Ràng buộc:

• Có 25% số test ứng với 25% số điểm của bài có n ≤ 50, 0 < a_i ≤ 10³;
• Có 25% số test ứng với 25% số điểm của bài có n ≤ 500, 0 < a_i ≤ 10⁶, các a_i có giá trị phân biệt;
• Có 25% số test ứng với 25% số điểm của bài có n ≤ 500, 0 < a_i ≤ 10⁶;
• Có 25% số test ứng với 25% số điểm của bài có n ≤ 1500, 0 < a_i ≤ 10⁹.

Câu 4. Khoá số (3 điểm)

Wednesday và các bạn bị nhốt vào một căn phòng với rất nhiều cạm bẫy. Tuy nhiên, là một người thông minh và dũng cảm, Wednesday đã giúp cả nhóm vượt qua được hầu như tất cả khó khăn để đến cửa ra của căn phòng. Ở cửa ra có một chiếc ổ khóa với kết cấu rất kì dị. Trên chiếc ổ khóa có m vòng khóa, mỗi vòng ghi n số nguyên (2 ≤ m ≤ 5; 1 ≤ n ≤ 10⁵). Vòng số thứ i sẽ chứa n số nguyên a_i,₁; a_i,₂; …; a_i,_n (|a_i,_j| ≤ 10⁹; 1 ≤ i ≤ m; 1 ≤ j ≤ n). Các vòng số có thể xoay tròn. Mỗi bước xoay, trên mỗi vòng số chỉ hiện đúng một số. Để mở được ổ khóa Wednesday cần phải xoay các vòng số sao cho tổng m số hiện trên m vòng số này đúng bằng S (|S| ≤ 10⁹).

Yêu cầu: Cho các giá trị trên m vòng số, hãy giúp Wednesday đếm xem có bao nhiêu cách xoay để mở được ổ khóa này.

Dữ liệu: Vào từ tệp CAU4.INP:

• Dòng đầu tiên ghi ba số nguyên m, n, S như mô tả ở đề bài.
• m dòng tiếp theo mỗi dòng ghi n số nguyên cho biết các giá trị trên từng vòng số.

Kết quả: Ghi ra tệp CAU4.OUT một số nguyên duy nhất là số cách để mở được ổ khóa đặc biệt này.

Ví dụ:

CAU4.INP	CAU4.OUT
2 3 5 1 2 1 3 4 4	5
4 10 6 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9	70
5 2 2 1 2 1 2 1 2 1 2 -2 -2	2

Chú ý

Ví dụ thứ hai ghi đáp số 70 theo đề gốc. Đếm trực tiếp số cách chọn 4 chữ số từ 0 đến 9 có tổng bằng 6 thì được 84, nên đáp số 70 trong đề gốc có thể bị in nhầm.

Ràng buộc:

• Có 30% số test ứng với 30% số điểm của bài có m = 2, n ≤ 10⁵;
• Có 40% số test ứng với 40% số điểm của bài có m = 4, n ≤ 10³;
• Có 30% số test ứng với 30% số điểm của bài có m = 5, n ≤ 400.

Câu 5. Phần dư (2 điểm)

Cho số nguyên tố k, tìm số nguyên dương m nhỏ nhất sao cho k × m tạo thành một số có tất cả các chữ số giống nhau.

Yêu cầu: Tìm phần dư nhận được trong phép chia m cho 10⁹ + 7.

Dữ liệu: Vào từ tệp văn bản CAU5.INP một số nguyên tố k (1 ≤ k ≤ 10⁹).

Kết quả: Ghi ra tệp văn bản CAU5.OUT một số nguyên là đáp số của bài toán.

Ví dụ:

CAU5.INP	CAU5.OUT
13	8547
23	797103822

Ràng buộc:

• Có 50% số test ứng với 50% số điểm của bài có k × m ≤ 10⁹;
• Có 50% số test ứng với 50% số điểm của bài không có ràng buộc gì thêm.

---

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.