Bảng B 2023 - Vòng chung kết toàn quốc

HỘI THI TIN HỌC TRẺ TOÀN QUỐC Năm 2023
ĐỀ CHÍNH THỨC

ĐỀ THI BẢNG B – TRUNG HỌC CƠ SỞ Thời gian làm bài 150 phút, không kể thời gian phát đề
Địa điểm thi: Trường THPT Hòn Gai

Tổng quan

	Tên bài	Mã bài	Điểm
Bài 1	Tìm số	fn.*	100 điểm
Bài 2	Tìm điểm	fp.*	100 điểm
Bài 3	Trò chơi kAND	kand.*	100 điểm

Hãy lập trình giải các bài toán sau:

Bài 1. Tìm số (100 điểm)

Cho số nguyên không âm n, cần tìm số m nhỏ nhất thỏa mãn điều kiện:

Số m lớn hơn hoặc bằng n;
Tổng các chữ số của m nhỏ hơn tổng các chữ số của n;

Dữ liệu: Vào từ thiết bị vào chuẩn có dạng:

Dòng đầu chứa số nguyên dương t là số bộ dữ liệu;
Dòng thứ i (1 ≤ i ≤ t) chứa một số nguyên không âm n.

Kết quả: Ghi ra thiết bị ra chuẩn gồm t dòng, mỗi dòng là số m tương ứng tìm được, nếu không tồn tại số m đưa ra −1.

Ví dụ:

Input	Output
`2` `5` `59`	`10` `60`

Subtask 1 (60 điểm): n ≤ 10⁶; t ≤ 3;
Subtask 2 (20 điểm): n ≤ 10⁶; t ≤ 3 × 10⁴;
Subtask 3 (20 điểm): n ≤ 10¹⁶; t ≤ 3 × 10⁴.

Bài 2. Tìm điểm (100 điểm)

Cho n + 1 hình chữ nhật trên mặt phẳng Oxy, các hình chữ nhật đều có các cạnh song song hoặc vuông góc với trục toạ độ. Hãy tìm điểm (x, y) nằm trong ít nhất n hình chữ nhật đã cho. Điểm (x, y) được gọi là nằm trong hình chữ nhật xác định bởi hai điểm (x₁, y₁) và (x₂, y₂) nếu:

min(x₁, x₂) ≤ x ≤ max(x₁, x₂);
min(y₁, y₂) ≤ y ≤ max(y₁, y₂).

Dữ liệu: Vào từ thiết bị vào chuẩn có dạng:

Dòng đầu chứa số nguyên n (1 ≤ n ≤ 2 × 10⁵);
n + 1 dòng tiếp theo, mỗi dòng chứa bốn số nguyên x₁, y₁, x₂, y₂ (0 ≤ x₁, x₂, y₁, y₂ ≤ 10⁹) mô tả hai điểm (x₁, y₁) và (x₂, y₂) là hai góc của hình chữ nhật, dữ liệu đảm bảo hai điểm này là phân biệt.

Kết quả: Ghi ra thiết bị ra chuẩn hai số nguyên x, y là toạ độ của điểm nằm trong ít nhất n hình chữ nhật, nếu có nhiều điểm thoả mãn thì đưa ra điểm có x nhỏ nhất, nếu có nhiều điểm thoả mãn có cùng x nhỏ nhất thì đưa ra điểm có y nhỏ nhất. Nếu không có điểm nào thỏa mãn chỉ ghi −1.

Ví dụ:

Input	Output
`2` `1 1 2 3` `2 2 3 1` `3 6 0 4`	`2 1`

Subtask 1 (25 điểm): x₁, x₂, y₁, y₂ ≤ 20;
Subtask 2 (25 điểm): x₁, x₂, y₁, y₂ ≤ 2000;
Subtask 3 (25 điểm): n ≤ 2000;
Subtask 4 (25 điểm): Không có ràng buộc gì thêm.

Bài 3. Trò chơi kAND (100 điểm)

Alice và Bob cùng chơi một trò chơi trên dãy số nguyên. Alice luôn muốn nhanh chóng tìm được một đoạn gồm các phần tử liên tiếp mà khi tính AND (&) của các phần tử đó bằng 0. Bob thì tìm cách thay đổi các số để làm khó Alice. Cụ thể, Bob muốn nhờ bạn lập trình giải bài toán sau: Cho số nguyên k (1 ≤ k ≤ n) và hai dãy số a và c cùng có độ dài n. Với mỗi vị trí i (1 ≤ i ≤ n), ta có thể thay đổi aᵢ thành giá trị bất kì với chi phí là cᵢ. Tìm tổng chi phí nhỏ nhất để thay đổi dãy a sao cho aᵢ & aᵢ₊₁ & … & aᵢ₊ₖ₋₁ = 0 với mọi 1 ≤ i ≤ n − k + 1.

Nhắc lại, Phép toán AND (có kí hiệu là &) được định nghĩa như sau: Kết quả của phép toán AND giữa hai số nguyên không âm x và y là một số nguyên không âm z trong đó bit thứ i trong biểu diễn nhị phân của z sẽ là 1 khi và chỉ khi bit thứ i trong biểu diễn nhị phân của x và y đồng thời bằng 1, ngược lại bit thứ i trong biểu diễn nhị phân của z sẽ là 0.

Dữ liệu: Vào từ thiết bị vào chuẩn với dòng đầu tiên là một số nguyên t (1 ≤ t ≤ 10⁶) cho biết số bộ dữ liệu, tiếp theo mỗi bộ có khuôn dạng:

Dòng đầu tiên gồm hai số nguyên n và k (1 ≤ k ≤ n ≤ 10⁶).
Dòng thứ hai gồm n số nguyên a₁, a₂, …, aₙ (0 ≤ aᵢ < 2³⁰).
Dòng cuối cùng gồm n số nguyên c₁, c₂, …, cₙ (0 ≤ cᵢ < 2³⁰).

Dữ liệu đảm bảo tổng các giá trị của n trong các bộ dữ liệu không vượt quá 10⁶.

Kết quả: Ghi ra thiết bị ra chuẩn gồm t dòng, mỗi dòng tương ứng là tổng chi phí nhỏ nhất tìm được của bộ dữ liệu xuất hiện trong dữ liệu vào.

Ví dụ:

Input	Output
`1` `5 2` `1 2 3 2 1` `3 2 5 2 3`	`4`

Subtask 1 (20 điểm): Tổng các giá trị của n trong t bộ dữ liệu không vượt quá 20;
Subtask 2 (20 điểm): cᵢ ≤ 1 với mọi 1 ≤ i ≤ n;
Subtask 3 (30 điểm): Tổng các giá trị của n trong t bộ dữ liệu không vượt quá 5000;
Subtask 4 (30 điểm): Không có ràng buộc gì 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