Bảng B 2024 - Vòng khu vực

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

ĐỀ THI BẢNG B – TRUNG HỌC CƠ SỞVÒNG KHU VỰC

Tổng quan bài thi

Bài	Tên bài
1	Biểu thức ngoặc
2	Dãy số
3	Xếp hậu

Bài 1. Biểu thức ngoặc

Biểu thức ngoặc là xâu chỉ gồm các kí tự (, ), [, ], {, }. Biểu thức ngoặc đúng và bậc của biểu thức ngoặc được định nghĩa một cách đệ qui như sau:

Biểu thức rỗng là biểu thức ngoặc đúng và có bậc bằng 0;
Nếu A là biểu thức ngoặc đúng có bậc bằng k thì (A), [A], {A} cũng là một biểu thức ngoặc đúng có bậc bằng k + 1;
Nếu A và B là hai biểu thức ngoặc đúng và có bậc tương ứng là k₁ và k₂ thì AB cũng là một biểu thức ngoặc đúng có bậc bằng max(k₁, k₂).

Ví dụ, ()[()] là một biểu thức ngoặc đúng có bậc bằng 2 còn {()[{}]} là một biểu thức ngoặc đúng và có bậc bằng 3.

Với hai số nguyên n, k, người ta tiến hành tạo ra tất cả các biểu thức ngoặc đúng có độ dài n và bậc không vượt quá k. Sắp xếp các biểu thức ngoặc theo thứ tự từ điển, chú ý rằng trong bài toán này thứ tự từ điển của các kí tự ngoặc là ( < ) < [ < ] < { < }.

Yêu cầu: Cho n, k và S là một xâu chỉ gồm các kí tự (, ), [, ], {, }, hãy tìm thứ tự của biểu thức ngoặc đúng S.

Input

Dòng đầu chứa hai số nguyên n, k (n ≤ 200; k ≤ 5);
Dòng thứ hai chứa một xâu S độ dài n.

Output

Gồm một dòng chứa một số nguyên là thứ tự của biểu thức ngoặc đúng.

Input	Output
`2 1` `[]`	`2`

Subtask 1 (40 điểm): n ≤ 10;
Subtask 2 (40 điểm): n ≤ 30;
Subtask 3 (20 điểm): Không có ràng buộc nào thêm.

Bài 2. Dãy số

Với dãy số nguyên dương A = (a₁, a₂, …, aₙ) và số nguyên dương k, tạo dãy Aᵏ gồm m = n × k phần tử bằng cách ghép liên tiếp k lần dãy A, cụ thể Aᵏ = (a₁, a₂, …, aₙ, …, a₁, a₂, …, aₙ). Một đoạn d phần tử liên tiếp trên dãy Aᵏ bắt đầu từ phần tử thứ i (1 ≤ i ≤ m − d + 1) gồm các phần tử i, i + 1, …, (i + d − 1) được gọi là đoạn đẹp nếu điều kiện sau thỏa mãn:

2 × min(a_i, a_i+1, …, a_i+d−1) > (a_i + a_i+1 + ⋯ + a_i+d−1) / d

Yêu cầu: Cho A = (a₁, a₂, …, aₙ) và hai số nguyên dương k, d, hãy đếm số chỉ số i (1 ≤ i ≤ m − d + 1) mà đoạn gồm d phần tử liên tiếp bắt đầu từ phần tử i là đoạn đẹp trên dãy Aᵏ.

Input

Dòng đầu chứa ba số nguyên dương n, k, d (n, k ≤ 10⁵; d ≤ n × k);
Dòng thứ hai chứa n số nguyên dương a₁, a₂, …, aₙ (aᵢ ≤ 10⁶).

Output

Gồm một dòng chứa một số nguyên là số chỉ số i cần đếm.

Input	Output
`2 3 3` `1 10`	`2`
`3 10 3` `1 5 10`	`0`

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

Bài 3. Xếp hậu

Trên bàn cờ kích thước n × n, các hàng được đánh số từ 1 đến n từ trên xuống dưới, các cột được đánh số từ 1 đến n từ trái sang phải. Ô nằm giao ở hàng i (1 ≤ i ≤ n), cột j (1 ≤ j ≤ n) được gọi là ô (i, j), ô này có trọng số là wᵢⱼ. Cần đặt đúng k quân hậu lên bàn cờ để không có hai quân hậu nào chiếu nhau. Nhắc lại, hai quân hậu chiếu nhau nếu chúng được đặt trên cùng hàng hoặc trên cùng cột hoặc trên cùng đường chéo.

Yêu cầu: Gọi s là tổng trọng số các ô có quân hậu đặt, tìm cách đặt để s là lớn nhất.

Input

Dòng đầu chứa hai số nguyên n, k (k ≤ n ≤ 8);
Dòng thứ i (1 ≤ i ≤ n) trong n dòng sau, mỗi dòng chứa n số nguyên không âm mô tả trọng số của bảng (các số không vượt quá 10⁶).

Output

Gồm một dòng chứa một số là tổng s lớn nhất đạt được.

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

Subtask 1 (30 điểm): k = 1;
Subtask 2 (30 điểm): k ≤ 3;
Subtask 3 (40 điểm): Không có ràng buộc nào 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