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

ĐỀ THI VÒNG SƠ KHẢO – BẢNG B (THCS)

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

Trò chơi xếp bóng với 3n quả bóng như sau: Có n quả bóng màu xanh b₁, b₂, …, bₙ, n quả bóng màu đỏ r₁, r₂, …, rₙ và n quả bóng màu vàng y₁, y₂, …, yₙ. 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 bᵢ vào cùng hộp với bóng màu đỏ rⱼ sẽ được thưởng a × f₁(i, j) điểm.
Nếu xếp bóng màu xanh bᵢ vào cùng hộp với bóng màu vàng yₖ sẽ được thưởng b × f₂(i, k) điểm.
Nếu xếp bóng màu đỏ rⱼ vào cùng hộp với bóng màu vàng yₖ sẽ được thưởng c × f₃(j, k) điểm.
Nếu xếp bóng màu xanh bᵢ, bóng màu đỏ rⱼ, bóng màu vàng yₖ 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 f₁(i, j), f₂(i, k), f₃(j, k), f(i, j, k) không vượt quá 10⁶, 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 ≤ 10⁹);
Dòng thứ hai chứa n² số mô tả các giá trị của f₁(1,1), f₁(1,2), …, f₁(n,n);
Dòng thứ ba chứa n² số mô tả các giá trị của f₂(1,1), f₂(1,2), …, f₂(n,n);
Dòng thứ tư chứa n² số mô tả các giá trị của f₃(1,1), f₃(1,2), …, f₃(n,n);
Dòng thứ năm chứa n³ 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 1` `1 0 0 1` `1 0 0 1` `1 0 0 1` `1 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

Xét phương trình có dạng:

(x² − 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 (x² − 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 (x² − 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| ≤ 10⁹).

Output: Ghi một số nguyên không âm là số nghiệm phân biệt của phương trình (x² − x(a + b) + ab)(x − c) = 0.

Ví dụ:

Input	Output
`1 3 1`	`2`

Bài 3. Dãy số

Xét dãy số nguyên dương a₁, a₂, …, aₙ, ban đầu aᵢ = 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ử aᵢ bằng c (1 ≤ c ≤ 10⁹);
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 ≤ 10⁹; 1 ≤ s ≤ 9; q ≤ 10⁵);
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 3` `2 11 13` `1 13 10` `2 13 13`	`61` `20`

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 ≤ 10³;
Subtask 2 (30%): n, q ≤ 10⁵;
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.

Th.S Trần Huy Phúc

Kỹ sư phần mềm @Adnovum & Bumbii Academy

Học Tiếng Anh với Bumbii English