Bảng B 2021 - Vòng sơ khảo quốc gia

HỘI THI TIN HỌC TRẺ TOÀN QUỐC
Năm 2021

ĐỀ THI VÒNG SƠ KHẢO QUỐC GIA - BẢNG B – TRUNG HỌC CƠ SỞ
Thời gian làm bài: 120 phút, không kể thời gian phát đề
Ngày thi: 08/08/2021

Tổng quan:

Tên bài	File chương trình	Thời gian chạy	Điểm
Bài 1	`tmpair.*`	1 giây	100 điểm
Bài 2	`divisor.*`	1 giây	100 điểm
Bài 3	`balance.*`	1 giây	100 điểm

Dấu * được thay thế bởi pas/cpp/py tương ứng với ngôn ngữ lập trình Pascal/C++/Python mà thí sinh sử dụng.

Bài 1. Cặp số đồng đội (100 điểm)

Một cặp số nguyên dương (a, b) mà a chia hết cho b hoặc b chia hết cho a được gọi là cặp số đồng đội. Cặp số đồng đội (a, b) và cặp số đồng đội (u, v) được gọi là giống nhau khi a = u và b = v.

Yêu cầu: Cho số nguyên dương N (2 ≤ N ≤ 10⁹), hãy đếm số cặp số đồng đội mà a + b = N.

Dữ liệu: Vào từ thiết bị vào chuẩn gồm một số nguyên dương N duy nhất.

Kết quả: Ghi ra thiết bị ra chuẩn một số nguyên duy nhất là số cặp số đồng đội thoả mãn.

Ví dụ:

Dữ liệu vào	Kết quả ra	Giải thích
`10`	`5`	Các cặp số đồng đội thỏa mãn: (1, 9), (2, 8), (5, 5), (8, 2), (9, 1)

Ràng buộc:

50% số test ứng với 50% số điểm thỏa mãn: N ≤ 10³;
30% số test khác ứng với 30% số điểm thỏa mãn: 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.

Kiểm tra lại với ví dụ: N = 10 → ước của 10 (trừ 10) = 5 → tập a hợp lệ = 5 ∪ 5 = 9 → 5 phần tử. Khớp với kết quả mẫu.

Bài 2. Ước số (100 điểm)

Một số nguyên dương n được phân tích thành thừa số nguyên tố: n = p₁^k₁ × p₂^k₂ × ... × pₘ^kₘ.

Yêu cầu: Cho hai số nguyên không âm A ≤ B, đếm số lượng ước của n thuộc đoạn [A, B].

Dữ liệu:

Dòng đầu chứa số nguyên dương m;
m dòng tiếp theo, dòng thứ i chứa hai số nguyên dương pᵢ và kᵢ (pᵢ, kᵢ không vượt quá 10⁹, các pᵢ là số nguyên tố đôi một khác nhau);
Ba dòng cuối ứng với ba câu hỏi, mỗi dòng chứa hai số nguyên không âm A, B.

Kết quả: Ba dòng, mỗi dòng ghi số ước tìm được cho câu hỏi tương ứng.

Ví dụ: với n = 2⁴ × 3⁴ × 5⁴ = 810000:

Dữ liệu vào	Kết quả ra
`3` `2 4` `3 4` `5 4` `1 5` `1 10` `1 5`	`5` `9` `5`

Ràng buộc:

40% số test có m ≤ 5; 0 ≤ A ≤ B ≤ 10⁶;
40% số test có m ≤ 10; 0 ≤ A ≤ B ≤ 10⁹;
20% số test còn lại có m ≤ 25; 0 ≤ A ≤ B ≤ 10⁹.

Bài 3. Cân đĩa (100 điểm)

Cho một cân hai đĩa và n quả cân có khối lượng đôi một khác nhau w₁, w₂, …, wₙ. Đặt lần lượt từng quả cân lên một trong hai đĩa, đảm bảo tổng khối lượng bên trái luôn nhỏ hơn hoặc bằng tổng khối lượng bên phải tại mọi thời điểm.

Yêu cầu: Đếm số cách xếp n quả cân thỏa mãn. Hai cách khác nhau nếu thứ tự xếp khác nhau hoặc có một quả cân nằm ở đĩa khác nhau.

Dữ liệu: Dòng 1 chứa n; dòng 2 chứa n số nguyên dương w₁,…,wₙ.

Kết quả: Một số nguyên là số cách xếp thỏa mãn.

Ví dụ:

Dữ liệu vào	Kết quả ra
`2` `1 2`	`3`
`3` `10 11 12`	`15`

Ràng buộc:

40% số test có n ≤ 7, wᵢ ≤ 1000;
40% số test có n ≤ 14, wᵢ ≤ 1000;
20% số test còn lại có n ≤ 28, wᵢ = 2^(i−1).

Kiểm tra lại với ví dụ: n=2, w=[1,2] → 3 cách; n=3, w=[10,11,12] → 15 cách. Khớp với đề bài.

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