Bảng B 2024 - TP Hà Nội (vòng chung kết)

HỘI THI TIN HỌC TRẺ THÀNH PHỐ HÀ NỘI Năm học 2023-2024

ĐỀ THI BẢNG B – TRUNG HỌC CƠ SỞVÒNG CHUNG KẾT

Tổng quan bài thi

Bài	Tên bài
1A	Tìm bộ số
1B	Chia kẹo
1C	Dãy TriSeq
1D	Lớp học

Bài 1A. Tìm bộ số

Cho một số nguyên N. Hãy tìm hai số nguyên a, b thoả mãn:

a × b = N;
c = |a − b| nhỏ nhất.

Dữ liệu vào từ thiết bị vào chuẩn:

Gồm một số nguyên N (|N| ≤ 10¹²).

Kết quả ghi ra thiết bị ra chuẩn:

Gồm một số nguyên c nhỏ nhất thoả mãn đề bài.

Ví dụ:

Dữ liệu	Kết quả	Giải thích
`12`	`1`	Có thể chọn a = 3; b = 4; Kết quả là \|3 − 4\| = 1.

Ràng buộc:

Có 60% số test ứng với 60% số điểm có: |N| ≤ 10³;
20% số test khác ứng với 20% số điểm có: |N| ≤ 10⁶;
20% số test còn lại ứng với 20% số điểm không có ràng buộc gì thêm.

Bài 1B. Chia kẹo

Một lớp học có N học sinh, học sinh thứ i (1 ≤ i ≤ N) có mã học sinh là số nguyên dương aᵢ. Hai học sinh có mã học sinh khác nhau. Cuối năm học, thầy giáo chủ nhiệm phát kẹo thưởng cho cả lớp. Là một giáo viên dạy môn Tin học nên thầy sẽ phát kẹo theo quy tắc sau:

Tất cả N học sinh đứng thành một hàng, học sinh thứ i đứng ở vị trí i tính từ đầu hàng;
Thầy sẽ phát kẹo Q lượt, mỗi lượt:
- Thầy sẽ chọn bốn số nguyên dương l, r, x, v;
- Thầy sẽ đi từ vị trí l đến vị trí r để phát kẹo, khi tới vị trí i (l ≤ i ≤ r) nếu mã học sinh aᵢ của học sinh chia hết cho x thì học sinh đó nhận được v viên kẹo.

Sau Q lượt phát kẹo, thầy muốn biết mỗi bạn học sinh có số kẹo là bao nhiêu.

Dữ liệu vào từ thiết bị vào chuẩn:

Dòng đầu tiên gồm hai số nguyên dương N và Q (1 ≤ N, Q ≤ 2 × 10⁵) mô tả số học sinh và số lượt phát kẹo;
Dòng thứ hai gồm N số nguyên dương aᵢ (1 ≤ i ≤ N; 1 ≤ aᵢ ≤ 5 × 10⁵) mô tả mã học sinh của học sinh thứ i;
Q dòng sau, mỗi dòng gồm bốn số nguyên dương l, r, x, v (1 ≤ l ≤ r ≤ N; 1 ≤ x ≤ 5 × 10⁵; v ≤ 10⁹) mô tả một cách phát kẹo.

Kết quả ghi ra thiết bị ra chuẩn:

Gồm một dòng chứa N số nguyên dương lần lượt là số kẹo của học sinh.

Ví dụ:

Dữ liệu	Kết quả
`6 4` `1 3 6 9 8 12` `1 6 2 2` `4 5 4 3` `2 4 3 1` `3 5 1 2`	`0 1 5 3 7 2`

Giải thích: Ở lần phát kẹo đầu tiên, chỉ các học sinh có mã học sinh chia hết cho 2 mới được nhận 2 cái kẹo. Số kẹo của học sinh lần lượt là (0, 0, 2, 0, 2, 2). Tương tự, ở lượt phát thứ hai, học sinh thứ 5 nhận được 3 cái kẹo. Số kẹo của học sinh lần lượt là (0, 0, 2, 0, 5, 2). Lượt thứ ba, học sinh thứ 2, 3, 4 đều nhận được 1 cái kẹo. Số kẹo của học sinh lần lượt là (0, 1, 3, 1, 5, 2). Lượt cuối cùng, học sinh thứ 3, 4, 5 đều nhận được 2 cái kẹo. Số kẹo của học sinh lần lượt là (0, 1, 5, 3, 7, 2).

Ràng buộc:

Có 20% số test ứng với 20% số điểm có: N, Q ≤ 10³;
20% số test khác ứng với 20% số điểm có: x = 1 với lần phát kẹo.
20% số test khác ứng với 20% số điểm có: x ≤ 2 với lần phát kẹo.
20% số test khác ứng với 20% số điểm có: l = 1, r = N với mọi lần phát kẹo.
20% số test còn lại ứng với 20% số điểm không có ràng buộc gì thêm.

Bài 1C. Dãy TriSeq

Ba số nguyên dương x, y, z thỏa mãn bất đẳng thức tam giác nếu các điều kiện sau thỏa mãn: x + y > z; x + z > y; y + z > x. Một dãy số nguyên dương a₁, a₂, …, aₙ được gọi là dãy TriSeq nếu ba số bất kỳ trong dãy đều thỏa mãn bất đẳng thức tam giác. Với một số nguyên dương n, xét các dãy số thỏa mãn tính chất:

Dãy gồm n phần tử, mỗi phần tử nhận giá trị thuộc [1, n];
Dãy số là dãy TriSeq.

Tiến hành sắp xếp các dãy trên theo thứ tự từ điển, đánh số bắt đầu từ 1. Cụ thể, dãy a₁, a₂, …, aₙ được xếp trước dãy b₁, b₂, …, bₙ nếu tồn tại chỉ số i (i = 1, 2, …, n) sao cho: a₁ = b₁, a₂ = b₂, …, aᵢ₋₁ = bᵢ₋₁ và aᵢ < bᵢ.

Ví dụ, n = 3, ta có 15 dãy được sắp xếp theo thứ tự từ điển như sau:


1) 1, 1, 1	6) 2, 2, 2	11) 3, 2, 2
2) 1, 2, 2	7) 2, 2, 3	12) 3, 2, 3
3) 1, 3, 3	8) 2, 3, 2	13) 3, 3, 1
4) 2, 1, 2	9) 2, 3, 3	14) 3, 3, 2
5) 2, 2, 1	10) 3, 1, 3	15) 3, 3, 3

Yêu cầu: Cho n, giải quyết các bài toán sau:

Đếm số lượng dãy số thỏa mãn;
Cho số số thứ tự t hãy xác định dãy có thứ tự thứ t;
Cho một dãy a₁, a₂, …, aₙ, tìm thứ tự của dãy.

Dữ liệu vào từ thiết bị vào chuẩn:

Dòng thứ nhất chứa số nguyên n;
Dòng thứ hai chứa một số nguyên t;
Dòng thứ ba chứa n số a₁, a₂, …, aₙ mô tả dãy.

Kết quả ghi ra thiết bị ra chuẩn:

Dòng thứ nhất chứa một số là số lượng dãy số thỏa mãn;
Dòng thứ hai chứa n số mô tả dãy có thứ tự thứ t;
Dòng thứ ba chứa một số là thứ tự của dãy a₁, a₂, …, aₙ.

Dữ liệu	Kết quả
`3` `4` `2 1 2`	`15` `2 1 2` `4`

Ràng buộc:

Có 20% số test ứng với 20% số điểm có: n = 3;
40% số test khác ứng với 40% số điểm có: n ≤ 9;
40% số test còn lại ứng với 40% số điểm không có: n ≤ 18.

Bài 1D. Lớp học

Một lớp học có n học sinh, thầy giáo đã đánh giá năng lực học tập của từng học sinh, cụ thể với bạn thứ i (1 ≤ i ≤ n):

Ở môn toán, có năng lực là cᵢ;
Ở môn văn có hai phần là đọc hiểu với năng lực là aᵢ, làm văn với năng lực là bᵢ.

Khi hai bạn i và j làm nhóm với nhau với nhau, thì năng lực làm nhóm của hai bạn là:

Ở môn toán là X(i, j) = cᵢ + cⱼ;
Ở môn văn là Y(i, j) = min(|aᵢ − aⱼ|, |bᵢ − bⱼ|).
Năng lực tổng hợp của hai bạn sẽ là T(i, j) = X(i, j) * Y(i, j).

Yêu cầu: Hãy tính giá trị Q = ∑_{1 ≤ i < j ≤ n} T(i, j).

Dữ liệu vào từ thiết bị vào chuẩn:

Dòng đầu chứa số nguyên dương n;
Dòng thứ hai chứa n số nguyên dương aᵢ;
Dòng thứ ba chứa n số nguyên dương bᵢ;
Dòng thứ tư chứa n số nguyên dương cᵢ.

Các số aᵢ, bᵢ, cᵢ có giá trị không vượt quá 10⁶.

Kết quả ghi ra thiết bị ra chuẩn: một số nguyên là giá trị Q % (10⁹ + 7).

Ví dụ:

Dữ liệu	Kết quả
`5` `1 4 2 5 4` `2 5 5 4 5` `4 1 6 3 2`	`75`

Ràng buộc:

Có 25% số test ứng với 25% số điểm của bài có n ≤ 10³;
Có 25% số test khác ứng với 25% số điểm của bài có n ≤ 10⁵;
Có 25% số test khác ứng với 25% số điểm của bài có n ≤ 5 × 10⁵ và cᵢ = cⱼ với mọi 1 ≤ i < j ≤ n;
Có 25% số test còn lại ứng với 25% số điểm của bài có n ≤ 5 × 10⁵.

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