Duyên hải Bắc Bộ 2024 - Khối 10 — đề thi, lời giải và phòng thi thử

Duyên hải Bắc Bộ 2024 - Khối 10

Nguồn: ClueOJ statement pages printed to PDF and merged in exam order; not an original scan

Chuyển nhập/xuất tệp sang stdin/stdout khi chạy trên website.

Câu 1. Tập số

Trên tập số ${1, 2, ..., n}$ , Alice tiến hành xóa đi $k$ ( $k < n$ ) số $a 1, a 2, ..., a k$ để nhận được tập $S$ . Một cách chọn các số trên tập $S$ được gọi là cách chọn tối ưu bậc $d$ nếu:

Hiệu hai số bất kì được chọn có giá trị tuyệt đối lớn hơn $d$ ;

Số lượng số được chọn là lớn nhất.

Ví dụ, trên tập số ${1, 2, 3, 4, 5, 6, 7, 8}$ , xóa đi ba số 2, 3, 8 được tập $S = {1, 4, 5, 6, 7}$ , ba tập ${1, 4, 6}$ , ${1, 4, 7}$ và ${1, 5, 7}$ đều là cách chọn tối ưu bậc 1.

Yêu cầu: Cho $n, k, d$ và dãy $a 1, a 2, ..., a k$ , hãy giúp Alice tính số lượng số chọn được trong cách chọn tối ưu bậc $d$ và số cách chọn tối ưu. Chú ý, hai cách chọn được gọi là khác nhau nếu tồn tại một số của $S$ thuộc trong cách chọn này nhưng không thuộc trong cách chọn kia.

Input

Dòng đầu chứa ba số nguyên dương $n, k, d$ ( $k < n \leq 107; k \leq 105; d \leq n$ );

Dòng thứ hai chứa $k$ số nguyên dương phân biệt $a 1, a 2, ..., a k$ ( $a i \leq n, 1 \leq i \leq k$ ).

Output

Hai dòng, dòng thứ nhất là số lượng số chọn được trong cách chọn tối ưu, dòng thứ hai là số cách chọn tối ưu chia dư cho $(10 9 + 7)$ .

Sample Input 1

8 3 1
2 3 8

Sample Output 1

3
3

Subtasks

Subtask 1 (20 điểm): $n - k \leq 20$ ;

Subtask 2 (25 điểm): $n - k \leq 200$ ;

Subtask 3 (25 điểm): $n - k \leq 2 \times 105$ ;

Subtask 4 (30 điểm): Không có ràng buộc gì thêm.

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 2. Mật khẩu

Alice muốn đặt mật khẩu cho một ứng dụng mà cô mới xây dựng. Cô đã chọn xâu kí tự $S$ (kí hiệu $|S|$ là độ dài xâu $S$ ) và dự định chọn $K$ đoạn trên xâu $S$ (các đoạn gồm ít nhất một kí tự và không nhất thiết rời nhau) rồi ghép các đoạn theo một thứ tự nào đó để nhận được xâu đối xứng. Nhắc lại, xâu đối xứng là xâu đọc từ trái qua phải cũng như đọc từ phải qua trái, ví dụ "abba", "sos" là xâu đối xứng, còn xâu "abab" thì không phải là xâu đối xứng. Alice đã chọn $K - 1$ đoạn, đoạn thứ $i$ ( $1 \leq i < K$ ) gồm các kí tự từ thứ $L i$ đến kí tự thứ $R i$ của xâu $S$ ( $1 \leq L i \leq R i \leq |S|$ ). Khi chọn đoạn thứ $K$ , Alice muốn chọn một đoạn có độ dài $m$ mà với đoạn đó Alice có thể ghép với $K - 1$ đoạn đã chọn theo một thứ tự nào đó để nhận được một xâu đối xứng.

Yêu cầu: Cho xâu $S$ và $(K - 1)$ cặp số $L i, R i$ , hãy đếm số cách chọn đoạn thỏa mãn.

Input

Dòng đầu chứa hai số nguyên dương $K, m$ ( $m \leq |S|$ );

Dòng thứ hai chứa xâu $S$ chỉ gồm các kí tự $'a'$ đến $'z'$ ( $2 K \times |S| \leq 2 \times 105$ );

Dòng thứ $i$ ( $1 \leq i \leq K - 1$ ) trong $K - 1$ dòng tiếp theo chứa hai số nguyên dương $L i, R i$ ( $1 \leq L i \leq R i \leq |S|$ ).

Output

Số lượng cách chọn đoạn thỏa mãn.

Sample Input 1

1 1
abab

Sample Output 1

Sample Input 2

2 2
abab
2 3

Sample Output 2

Subtasks

Subtask 1 (20 điểm): $K = 1; |S| \leq 2000$ ;

Subtask 2 (20 điểm): $K = 1$ ;

Subtask 3 (20 điểm): $K \leq 7; |S| \leq 2000$ ;

Subtask 4 (20 điểm): $K \leq 7$ ;

Subtask 5 (20 điểm): $K = 14$ .

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 3. Mạng công ty

Công ty của Alice có $n$ máy tính, các máy tính được đánh số từ 1 đến $n$ . Hiện tại đang có $m$ ( $m \geq n - 1$ ) dây nối giữa các máy tính, dây nối thứ $k$ ( $1 \leq k \leq m$ ) nối hai máy tính $u k, v k$ ( $u k \neq v k$ ) và giúp truyền tin theo cả hai chiều giữa hai máy, có thể có nhiều dây nối giữa hai máy tính. Hiện tại, $n$ máy tính có thể không liên thông với nhau, Alice có thể tháo dây nối để đấu nối lại với mong muốn làm cho $n$ máy tính liên thông, cụ thể, cô có thể thực hiện:

Tháo một đầu nối của dây thứ $k$ để đấu nối sang máy tính khác, hành động này mất chi phí $c k$ ;

Tháo cả hai đầu nối của dây thứ $k$ để đấu nối sang hai máy tính khác, hành động này mất chi phí $2 \times c k$ .

Yêu cầu: Hãy giúp Alice tính chi phí ít nhất cần thực hiện để liên thông được $n$ máy tính.

Input

Dòng đầu chứa hai số nguyên dương $n, m$ ( $n \leq 105; n - 1 \leq m \leq 2 \times 105$ );

Dòng thứ $k$ ( $1 \leq k \leq m$ ) trong $m$ dòng tiếp theo chứa ba số nguyên dương $u k, v k, c k$ ( $c k \leq 106$ ).

Output

Chi phí ít nhất tìm được.

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Subtasks

Subtask 1 (50 điểm): $c i = 1$ ;

Subtask 2 (25 điểm): $m, n \leq 1000$ ;

Subtask 3 (25 điểm): Không có ràng buộc gì thêm.

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 4. Mê cung ngoặc

Một mê cung được mô tả bằng bảng chữ hình chữ nhật kích thước $m \times n$ . Các hàng của bảng được đánh số từ 1 đến $m$ từ trên xuống dưới, các cột của bảng được đánh số từ 1 đến $n$ từ trái qua phải. Ô nằm trên giao của hàng $i$ và cột $j$ được gọi là ô $(i, j)$ . Mỗi ô của lưới chứa một kí tự ngoặc mở '(' hoặc ngoặc đóng ')'.

Người chơi xuất phát từ ô $(1, 1)$ , ban đầu hướng sang phải về phía ô $(1, n)$ . Từ ô đang đứng, người chơi có thể đi sang ô kề theo hướng đang nhìn hoặc rẽ phải $90 circ$ rồi đi sang ô kề theo hướng mới. Các lựa chọn được liệt kê trong bảng sau:

Hướng đang nhìn	Đi thẳng	Rẽ phải
Đông (sang phải)	Đông	Nam
Nam (đi xuống)	Nam	Tây
Tây (sang trái)	Tây	Bắc
Bắc (đi lên)	Bắc	Đông

Mỗi ô chỉ được đi qua nhiều nhất một lần. Người chơi có thể dừng di chuyển tại một ô nào đó để kết thúc trò chơi.

Khi kết thúc trò chơi, người chơi nhận được một xâu kí tự $T$ gồm các kí tự trong các ô trên đường đi được xếp liên tiếp nhau. Người chơi giành chiến thắng nếu xâu $T$ là một biểu thức ngoặc đúng bậc $k$ .

Nhắc lại, định nghĩa biểu thức ngoặc đúng và bậc của biểu thức ngoặc:

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)$ 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 1$ và $k 2$ thì $AB$ cũng là một biểu thức ngoặc đúng có bậc bằng $max (k 1, k 2)$ .

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.

Yêu cầu: Cho bảng chữ và số nguyên dương $k$ , đếm số lượng đường đi khác nhau giúp người chơi giành chiến thắng. Hai đường đi được gọi là khác nhau nếu tồn tại một ô thuộc đường đi này nhưng không thuộc đường đi kia.

Input

Dòng đầu tiên ghi ba số nguyên dương $m, n, k$ ( $m, n \leq 30; k \leq 10$ );

Tiếp theo là $m$ dòng mô tả bảng chữ, mỗi dòng gồm đúng $n$ kí tự, mỗi kí tự là ngoặc mở '(' hoặc ngoặc đóng ')'.

Output

Số lượng đường đi đếm được chia dư cho $109 +7$ .

Sample Input 1

3 3 1
())
)()
)))

Sample Output 1

Subtasks

Subtask 1 (50 điểm): $m, n \leq 5$ ;

Subtask 2 (25 điểm): $k = 1$ ;

Subtask 3 (25 điểm): Không có ràng buộc gì thêm.

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Cấu trúc đề và tiến độ