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

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

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. 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 ≤ i < K) gồm các kí tự từ thứ L_i đến kí tự thứ R_i của xâu S (1 ≤ L_i ≤ R_i ≤ |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 ≤ |S|);

• Dòng thứ hai chứa xâu S chỉ gồm các kí tự 'a' đến 'z' (2^K × |S| ≤ 2 × 10⁵);

• Dòng thứ i (1 ≤ i ≤ K - 1) trong K - 1 dòng tiếp theo chứa hai số nguyên dương L_i, R_i (1 ≤ L_i ≤ R_i ≤ |S|).

Output

• Ghi ra thiết bị ra chuẩn một dòng chứa một số là số lượng cách chọn đoạn thỏa mãn.

Sample Input 1

1 1
abab

Sample Output 1

4

Sample Input 2

2 2
abab
2 3

Sample Output 2

2

Subtasks

• Subtask 1 (20 điểm): K = 1; |S| ≤ 2000;

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

• Subtask 3 (20 điểm): K ≤ 7; |S| ≤ 2000;

• Subtask 4 (20 điểm): K ≤ 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 2. 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 ≥ n - 1) dây nối giữa các máy tính, dây nối thứ k (1 ≤ k ≤ m) nối hai máy tính u_k, v_k (u_k ≠ 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 × 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 ≤ 10⁵; n - 1 ≤ m ≤ 2 × 10⁵);

• Dòng thứ k (1 ≤ k ≤ m) trong m dòng tiếp theo chứa ba số nguyên dương u_k, v_k, c_k (c_k ≤ 10⁶).

Output

• Ghi ra thiết bị ra chuẩn một dòng chứa một số là chi phí ít nhất tìm được.

\Needspace{8\baselineskip}

Sample Input 1

3 3
1 2 1
1 2 2
1 3 1

Sample Output 1

0

\Needspace{12\baselineskip}

Sample Input 2

3 3
1 2 1
1 2 2
1 2 3

Sample Output 2

1

Subtasks

• Subtask 1 (40 điểm): c_i = 1;

• Subtask 2 (30 điểm): m, n ≤ 1000;

• Subtask 3 (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 3. 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 × 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 sẽ xuất phát từ ô (1, 1), quay hướng tới phía ô (1, n) và di chuyển trên bảng. Việc di chuyển phải tuân thủ các quy tắc được mô tả trên hình trên, cụ thể: từ ô đang đứng, căn cứ vào hướng đang hướng tới được chỉ ra bởi mũi tên ⇒, thực hiện bước di chuyển sang ô kề cạnh đang hướng tới, hoặc sang ô kề cạnh nằm bên phải (các hướng có thể di chuyển được chỉ ra bởi các mũi tên →). 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₁ 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.

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 ≤ 30; k ≤ 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

• Kết quả ghi ra thiết bị ra chuẩn một số nguyên là số lượng đường đi đếm được chia dư cho 998244353.

Sample Input 1

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

Sample Output 1

4

Subtasks

• Subtask 1 (30% số điểm): m, n ≤ 5;

• Subtask 2 (30% số điểm): k = 1;

• Subtask 3 (40% số đ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. Bán hàng tối ưu

Alice có n món đồ cổ và muốn bán tất cả trong m ngày. Cô đã tìm hiểu và biết được c_it là số tiền mà cô sẽ nhận được nếu bán món đồ i (1 ≤ i ≤ n) ở ngày t (1 ≤ t ≤ m) hoặc c_it = -1 nếu không ai muốn mua món đồ i ở ngày t. Một số món đồ cổ phát bán trước một số món đồ khác, có k ràng buộc như vậy, mỗi ràng buộc có dạng (u, v) và có nghĩa là món đồ u phải được bán trước ít nhất một ngày so với ngày bán món đồ v. Alice muốn lên kế hoạch bán tối ưu để có thể thu được số tiền lớn nhất. Chú ý rằng, mỗi ngày Alice có thể bán nhiều hơn một món đồ miễn là các món đồ liên quan đến các ràng buộc được thỏa mãn.

Yêu cầu: Giúp Alice tính số tiền nhiều nhất có thể thu được nếu Alice bán được tất cả n món đồ.

Input

• Dòng đầu tiên ghi ba số nguyên dương n, m, k (n, m, k ≤ 100);

• Tiếp theo là n dòng, dòng thứ i (1 ≤ i ≤ n) chứa m số nguyên c_i1, c_i2, ..., c_im (-1 ≤ c_it ≤ 100);

• Tiếp theo là k dòng, mỗi dòng chứa hai số nguyên dương u, v (1 ≤ u, v ≤ n) cho biết món đồ u phải trước ít nhất một ngày so với ngày bán món đồ v. Dữ liệu đảm bảo có cách bán hết cả n món đồ.

Output

Số tiền nhiều nhất có thể thu được trong kế hoạch bán tối ưu tất cả các món đồ.

Sample Input 1

3 2 2
100 -1
100 80
100 90
1 2
1 3

Sample Output 1

270

Subtasks

• Subtask 1 (25 điểm): n ≤ 15;

• Subtask 2 (35 điểm): Trong k ràng buộc không có hai ràng buộc nào có cùng giá trị v;

• Subtask 3 (40 đ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.