Bảng B 2024 - TP Hà Nội (vòng sơ khảo)

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 SƠ KHẢO

Tổng quan bài thi

Bài	Tên bài
1A	MAXAA
1B	Tổng chéo
1C	Đoạn con 3
1D	Num9

Bài 1A. MAXAA

Cho ba phép tính +, −, × và một số nguyên A hãy điền một trong ba phép tính vào dấu ? trong biểu thức dưới đây để được B lớn nhất.

A ? A = B

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

Gồm một dòng chứa số nguyên A (−10⁹ ≤ A ≤ 10⁹).

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

Gồm một dòng chứa số nguyên B lớn nhất tìm được.

Ví dụ:

Dữ liệu vào	Kết quả ra
`-5`	`25`

Bài 1B. Tổng chéo

Cho bảng số có kích thước N × N được điền số liên tiếp từ 1 đến N², từ trái qua phải, từ trên xuống dưới. Ví dụ với N = 4, bảng số như sau:


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

Yêu cầu: cho vị trí một ô ở dòng thứ x và cột thứ y, hãy tính tổng hai đường chéo đi qua ô này.

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

Dòng đầu tiên chứa hai số nguyên dương N và Q (N ≤ 10⁹; Q ≤ 10⁵) mô tả kích thước của bảng số và số lượng truy vấn;
Q dòng sau, mỗi dòng gồm hai số nguyên dương x và y (x, y ≤ N) mô tả một truy vấn là vị trí một ô ở dòng thứ x và cột thứ y.

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

Gồm Q dòng, mỗi dòng gồm một số nguyên là kết quả của truy vấn tương ứng. Vì kết quả có thể rất lớn nên chỉ cần in ra phần dư của kết quả cho 10⁹ + 7.

Ví dụ:

Dữ liệu vào	Kết quả ra
`4 2` `2 2` `1 3`	`46` `26`

Giải thích:

Hai bảng 4 x 4. Bảng trái: ô 6 tô đỏ, hai đường chéo qua ô (2, 2) tô xanh lá gồm 1, 6, 11, 16 và 3, 6, 9. Bảng phải: ô 3 tô đỏ, hai đường chéo qua ô (1, 3) tô xanh dương gồm 3, 8 và 3, 6, 9

Ràng buộc:

Có 70% số test ứng với 70% số điểm có: N ≤ 100; Q = 1;
20% số test khác ứng với 20% số điểm có: N ≤ 5000; Q ≤ 10⁵;
10% số test còn lại ứng với 10% số điểm không có ràng buộc gì thêm.

Bài 1C. Đoạn con 3

Cho một dãy số nguyên A gồm N phần tử. Hãy tìm ba đoạn con liên tiếp (có ít nhất một phần tử) không giao nhau của dãy số sao cho tổng các phần tử của ba đoạn con này là lớn nhất.

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

Dòng đầu tiên gồm một số nguyên dương N (3 ≤ N ≤ 10⁵) mô tả số phần tử của dãy số;
Dòng thứ hai gồm N số nguyên Aᵢ (1 ≤ i ≤ N; |Aᵢ| ≤ 10⁹) mô tả các phần tử của dãy số.

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

Gồm một số nguyên là kết quả của bài toán.

Ví dụ:

Dữ liệu	Kết quả	Giải thích
`7` `1 2 -3 4 1 -6 2`	`10`	(1 + 2) + (4 + 1) + (2) = 10

Ràng buộc:

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

Bài 1D. Num9

Cho dãy số nguyên a₁, a₂, …, aₙ. Một cách chọn bộ 9 chỉ số, các chỉ số đôi một khác nhau, (i₁, j₁, k₁, i₂, j₂, k₂, i₃, j₃, k₃) được gọi là tối ưu nếu giá trị a_i₁ × a_j₁ × a_k₁ + a_i₂ × a_j₂ × a_k₂ + a_i₃ × a_j₃ × a_k₃ đạt giá trị lớn nhất trong tất cả các cách chọn.

Ví dụ, với dãy 0, 2, 2, 0, 2, −1, 1, −1, 0, 0, thì cách chọn bộ 9 chỉ số (2, 3, 5, 1, 4, 9, 6, 7, 8) là tối ưu vì giá trị (2 × 2 × 2) + (0 × 0 × 0) + ((−1) × 1 × (−1)) = 9 là giá trị lớn nhất trong tất cả các cách chọn.

Yêu cầu: Cho dãy số nguyên a₁, a₂, …, aₙ, hãy tìm giá trị cách chọn tối ưu.

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

Dòng đầu chứa hai số nguyên n (9 ≤ n ≤ 10⁵);
Dòng thứ hai chứa n số nguyên a₁, a₂, …, aₙ (|aᵢ| ≤ 10⁶).

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

Gồm một dòng, chứa một số nguyên là giá trị của cách chọn tối ưu.

Ví dụ:

Dữ liệu	Kết quả
`10` `0 2 2 0 2 -1 1 -1 0 0`	`9`

Ràng buộc:

Có 50% số test ứng với 50% số điểm có: n = 9;
25% số test khác ứng với 25% số điểm có: n ≤ 18;
25% số test còn lại ứng với 25% số đ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