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

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

ĐỀ THI TIN HỌC TRẺ TOÀN QUỐCBẢNG B, C2 – VÒNG CHUNG KẾT

Tổng quan bài thi

Câu	Tên bài
1	Xếp que diêm
2	Tô màu bảng
3	Đa giác đều
4	Chia dãy
5	Dãy ngoặc đúng

Câu 1. Xếp que diêm

Có thể dùng các que diêm để xếp thành các số từ 0 đến 9 như sau:

Các chữ số 0 đến 9 xếp bằng que diêm kiểu đồng hồ điện tử 7 vạch: 0 dùng 6 que, 1 dùng 2, 2 dùng 5, 3 dùng 5, 4 dùng 4, 5 dùng 5, 6 dùng 6, 7 dùng 4 (có thêm vạch trái phía trên), 8 dùng 7, 9 dùng 6

Cho một số tự nhiên N (100 ≤ N ≤ 999) mà các chữ số của nó được xếp bởi các que diêm theo cách như trên. Vẫn với số que diêm như vậy thì có thể xếp thành số nhỏ nhất và số lớn nhất có ba chữ số là số nào?

Chú ý: kết quả tạo thành không có số 0 ở đầu.

Dữ liệu nhập vào từ bàn phím:

Dòng thứ nhất chứa một số tự nhiên N (100 ≤ N ≤ 999) là số ban đầu.

Kết quả ghi ra màn hình:

Dòng thứ nhất là số bé nhất tìm được;
Dòng thứ hai là số lớn nhất tìm được.

Ví dụ:

Dữ liệu	Kết quả	Giải thích
`123`	`104` `971`	Số lượng các que diêm đều là 12.

Câu 2. Tô màu bảng

Cho bảng kích thước n × m gồm n dòng và m cột. Hãy đếm số cách tô mỗi ô của bảng thành một trong hai màu trắng hoặc đen, sao cho không xuất hiện ba ô liên thông với nhau được tô cùng một màu. Ba ô liên thông có dạng như các hình sau:

Sáu hình ba ô liên thông: ba ô thẳng đứng, ba ô nằm ngang, và bốn hình chữ L gồm ba ô của một hình vuông 2 × 2

Dữ liệu: Vào từ thiết bị vào chuẩn gồm một dòng chứa hai số nguyên n, m (1 ≤ n, m ≤ 100).

Kết quả: Ghi ra một số nguyên là số cách tô lấy số dư cho 10⁹ + 7.

Ví dụ:

Input	Output
`2 2`	`6`

Subtask 1 (42 điểm): n, m ≤ 5;
Subtask 2 (21 điểm): n = 2;
Subtask 3 (27 điểm): n ≤ 5;
Subtask 4 (10 điểm): Không có ràng buộc gì thêm.

Câu 3. Đa giác đều

Cho một đa giác đều n đỉnh, các đỉnh được đánh số từ 1 đến n theo chiều kim đồng hồ. Trong đó có k đỉnh được tô màu. Hãy cho biết có bao nhiêu cách chọn ba đỉnh khác nhau được tô màu mà tam giác được xác định bởi ba đỉnh này chứa tâm của đa giác đã cho (có thể nằm trên cạnh của tam giác).

Lục giác đều đánh số đỉnh 1 đến 6 theo chiều kim đồng hồ, tam giác đỏ nối các đỉnh 1, 3, 5 chứa tâm lục giác

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

Dòng đầu chứa hai số nguyên dương n, k (3 ≤ k ≤ n ≤ 10⁶);
Dòng thứ hai chứa k số nguyên p₁, p₂, …, p_k (1 ≤ p₁ < p₂ < ⋯ ≤ n) mô tả các đỉnh được chọn để tô màu.

Kết quả: Ghi ra một số nguyên là số cách chọn ba đỉnh thoả mãn.

Ví dụ:

Input	Output	Giải thích
`6 4` `1 3 4 5`	`3`	Ba bộ thoả mãn: - (1, 3, 4) - (1, 3, 5) - (1, 4, 5)

Subtask 1 (25 điểm): n, k ≤ 500;
Subtask 2 (25 điểm): n, k ≤ 5000;
Subtask 3 (25 điểm): k = n;
Subtask 4 (25 điểm): Không có ràng buộc gì thêm.

Câu 4. Chia dãy

Cho dãy số nguyên dương a₁, a₂, …, a_n. Hãy chia dãy này thành các đoạn liên tiếp:

Tổng các phần tử của mỗi đoạn không vượt quá s;
Gọi chi phí của một đoạn được chia ra bắt đầu từ l đến r là: c(l, r) = max(a_l, a_l+1, …, a_r) + (r − l)

Hãy tìm cách chia dãy thoả mãn sao cho tổng chi phí là nhỏ nhất.

Với dãy [3, 1, 5, 2, 1, 4] và s = 7 ta có thể chia thành các đoạn [3, 1], [5], [2, 1, 4] với tổng chi phí là 3 + 1 + 5 + 0 + 4 + 2 = 15.

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

Dòng đầu chứa hai số nguyên n, s (1 ≤ n ≤ 2 × 10⁶; 1 ≤ s ≤ 10¹⁸);
Dòng thứ hai chứa n số nguyên a₁, a₂, …, a_n (1 ≤ a_i ≤ min(s, 10⁹) ∀1 ≤ i ≤ n).

Kết quả: Ghi ra một số nguyên là tổng chi phí theo cách chia tối ưu.

Ví dụ:

Input	Output
`6 7` `3 1 5 2 1 4`	`15`

Subtask 1 (20 điểm): n ≤ 500;
Subtask 2 (20 điểm): n ≤ 5000;
Subtask 3 (30 điểm): n ≤ 2 × 10⁵;
Subtask 4 (30 điểm): Không có ràng buộc gì thêm.

Câu 5. Dãy ngoặc đúng

Một dãy ngoặc đúng được định nghĩa như sau:

Xâu rỗng là một dãy ngoặc đúng;
Nếu xâu A là một dãy ngoặc đúng thì (A) cũng là một dãy ngoặc đúng;
Nếu xâu A và xâu B là hai dãy ngoặc đúng thì xâu AB là một dãy ngoặc đúng.

Cho một xâu S độ dài N chỉ gồm các kí tự ’(’ và ’)’, các kí tự được đánh số từ 1 đến N theo chiều từ trái qua phải. Cho Q truy vấn, mỗi truy vấn có dạng l r (l ≤ r) với ý nghĩa cần tính số cặp (u, v) (l ≤ u ≤ v ≤ r) mà xâu con của S gồm các kí tự liên tiếp từ u đến v tạo thành một dãy ngoặc đúng.

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

Dòng đầu tiên ghi xâu S chỉ gồm các kí tự ’(’ và ’)’ (|S| ≤ 10⁵);
Dòng thứ hai chứa số nguyên dương Q (Q ≤ 10⁵);
Tiếp theo là Q dòng, mỗi dòng mô tả một truy vấn gồm hai số nguyên l, r (1 ≤ l ≤ r ≤ |S|).

Kết quả: Với mỗi truy vấn, in ra số lượng xâu con tạo thành dãy ngoặc đúng tương ứng.

Ví dụ:

Input	Output
`()()(())(` `5` `1 2` `2 3` `1 6` `6 9` `1 9`	`1` `0` `3` `1` `7`

Subtask 1 (20 điểm): Q ≤ 50, |S| ≤ 100;
Subtask 2 (20 điểm): Q ≤ 100, |S| ≤ 1000;
Subtask 3 (40 điểm): Q ≤ 1000;
Subtask 4 (20 đ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