Bảng B 2025 - Vòng sơ khảo TP Hà Nội
HỘI THI TIN HỌC TRẺ THÀNH PHỐ HÀ NỘI Năm 2025
Tổng quan bài thi
Phần tiêu đề “Tổng quan bài thi”| Bài | Tên bài |
|---|---|
| 1 | Xếp bóng |
| 2 | Phương trình |
| 3 | Dãy số |
Bài 1. Xếp bóng
Phần tiêu đề “Bài 1. Xếp bóng”Trò chơi xếp bóng với 3n quả bóng như sau: Có n quả bóng màu xanh b1, b2, …, bn, n quả bóng màu đỏ r1, r2, …, rn và n quả bóng màu vàng y1, y2, …, yn. Nhiệm vụ của người chơi là xếp 3n quả bóng vào n hộp, mỗi hộp có đúng 3 quả, một quả màu xanh, một quả màu đỏ, một quả màu vàng để nhận được điểm thưởng theo quy tắc:
- Nếu xếp bóng màu xanh bi vào cùng hộp với bóng màu đỏ rj sẽ được thưởng a × f1(i, j) điểm.
- Nếu xếp bóng màu xanh bi vào cùng hộp với bóng màu vàng yk sẽ được thưởng b × f2(i, k) điểm.
- Nếu xếp bóng màu đỏ rj vào cùng hộp với bóng màu vàng yk sẽ được thưởng c × f3(j, k) điểm.
- Nếu xếp bóng màu xanh bi, bóng màu đỏ rj, bóng màu vàng yk cùng một hộp sẽ được thưởng w × f(i, j, k) điểm.
Yêu cầu: cho n, a, b, c, w và các giá trị không âm f1(i, j), f2(i, k), f3(j, k), f(i, j, k) không vượt quá 106, hãy tìm cách xếp bóng để đạt được tổng điểm lớn nhất.
Input:
- Dòng đầu chứa các số nguyên n, a, b, c, w (0 < a, b, c, w ≤ 109);
- Dòng thứ hai chứa n2 số mô tả các giá trị của f1(1,1), f1(1,2), …, f1(n,n);
- Dòng thứ ba chứa n2 số mô tả các giá trị của f2(1,1), f2(1,2), …, f2(n,n);
- Dòng thứ tư chứa n2 số mô tả các giá trị của f3(1,1), f3(1,2), …, f3(n,n);
- Dòng thứ năm chứa n3 số mô tả các giá trị của f(1,1,1), f(1,1,2), …, f(n,n,n).
Output: Gồm một dòng chứa một số nguyên là tổng điểm lớn nhất đạt được.
Ví dụ:
| Input | Output |
|---|---|
2 1 1 1 11 0 0 11 0 0 11 0 0 11 0 0 0 0 0 0 1 | 8 |
- Subtask 1 (50%): n = 2;
- Subtask 2 (25%): n ≤ 5;
- Subtask 3 (25%): n ≤ 10.
Bài 2. Phương trình
Phần tiêu đề “Bài 2. Phương trình”Xét phương trình có dạng:
(x2 − x(a + b) + ab)(x − c) = 0, với a, b, c là hằng số.
Ví dụ, a = 1; b = 3; c = 1, ta có phương trình (x2 − 4x + 3)(x − 1) = 0, phương trình này có hai nghiệm phân biệt là x = 1 và x = 3.
Yêu cầu: Cho ba số nguyên a, b, c, hãy đếm số nghiệm phân biệt của phương trình (x2 − x(a + b) + ab)(x − c) = 0.
Input: Gồm một dòng chứa ba số nguyên a, b, c (|a|, |b|, |c| ≤ 109).
Output: Ghi một số nguyên không âm là số nghiệm phân biệt của phương trình (x2 − x(a + b) + ab)(x − c) = 0.
Ví dụ:
| Input | Output |
|---|---|
1 3 1 | 2 |
Bài 3. Dãy số
Phần tiêu đề “Bài 3. Dãy số”Xét dãy số nguyên dương a1, a2, …, an, ban đầu ai = i (1 ≤ i ≤ n). Cho chữ số s (1 ≤ s ≤ 9) và q thao tác trên dãy, mỗi thao tác thuộc một trong hai loại sau:
- Thao tác loại 1 có dạng
1 i c, có nghĩa là cập nhật phần tử ai bằng c (1 ≤ c ≤ 109); - Thao tác loại 2 có dạng
2 L R, có nghĩa là cần tính giá trị w = f(L)·a_L + f(L+1)·a_(L+1) + … + f(R)·a_R, trong đó f(i) nhận giá trị bằng 2 nếu i chia hết cho s hoặc trong biểu diễn số i có xuất hiện chữ số s, ngược lại f(i) nhận giá trị bằng 1.
Yêu cầu: Với mỗi thao tác loại 2 đưa ra giá trị w.
Input:
- Dòng đầu chứa ba số nguyên dương n, s, q (n ≤ 109; 1 ≤ s ≤ 9; q ≤ 105);
- Dòng thứ k (1 ≤ k ≤ q) trong q dòng sau chứa ba số nguyên mô tả thao tác thứ k.
Output: Gồm nhiều dòng, mỗi dòng ghi giá trị w tính được của thao tác loại 2 lần lượt tương ứng với dữ liệu vào.
Ví dụ:
| Input | Output |
|---|---|
13 3 32 11 131 13 102 13 13 | 6120 |
Giải thích:
- Thao tác thứ nhất: w = 11 + 2 × 12 + 2 × 13 = 61.
- Dãy số sau thao tác thứ hai: (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 10).
- Thao tác thứ ba: w = 2 × 10 = 20.
Ràng buộc:
- Subtask 1 (30%): n, q ≤ 103;
- Subtask 2 (30%): n, q ≤ 105;
- Subtask 3 (20%): Không có thao tác loại 1;
- Subtask 4 (20%): Không có ràng buộc nào thêm.