USACO 2023 - Tháng 12 - Hạng Bạc

Farmer John đã quyết định cho đàn bò biểu diễn nhào lộn! Trước tiên, FJ cân đàn bò và thấy chúng có \(N\) mức cân nặng đôi một khác nhau (\(1\le N\le 2\cdot 10^5\)). Cụ thể, với mỗi \(i\in[1,N]\), có \(a_i\) con bò nặng \(w_i\) (\(1\le a_i\le 10^9\), \(1\le w_i\le 10^9\)).

Tiết mục nổi tiếng nhất của ông là cho các con bò tạo thành những tháp cân bằng. Một tháp là một dãy bò, trong đó mỗi con được xếp lên trên con tiếp theo. Một tháp được gọi là cân bằng nếu mọi con bò có một con khác nằm ngay phía trên đều nặng hơn con bò ngay phía trên đó ít nhất \(K\) (\(1\le K\le 10^9\)). Mỗi con bò chỉ có thể thuộc tối đa một tháp cân bằng.

Nếu FJ muốn tạo không quá \(M\) (\(1\le M\le 10^9\)) tháp bò cân bằng, nhiều nhất bao nhiêu con bò có thể thuộc một tháp nào đó?

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên cách nhau bởi dấu cách: \(N\), \(M\) và \(K\).

\(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên cách nhau bởi dấu cách \(w_i\) và \(a_i\). Đảm bảo tất cả \(w_i\) đôi một khác nhau.

Dữ liệu ra

In số bò lớn nhất có thể nằm trong các tháp cân bằng nếu FJ giúp chúng tạo tháp một cách tối ưu.

Ví dụ

3 5 2
9 4
7 6
5 5

14

3 5 3
5 5
7 6
9 4

9

Phân nhóm

• Trong dữ liệu 3–5, \(M\leq 5000\) và tổng số bò không vượt quá \(5000\).
• Trong dữ liệu 6–11, tổng số bò không vượt quá \(2\cdot 10^5\).
• Dữ liệu 12–17 không có ràng buộc bổ sung.

Nguồn

USACO 2023 December Contest, Silver — Bovine Acrobatics: https://usaco.org/index.php?page=viewproblem2&cpid=1350

Tác giả bài toán: Eric Hsu

Farmer John có \(N\) chuồng (\(3\le N\le 5\cdot 10^5\)), trong đó có \(K\) cặp chuồng đôi một khác nhau được nối với nhau (\(3\le K\le N\)).

Trước tiên, Annabelle gán cho mỗi chuồng một nhãn số nguyên khác nhau trong đoạn \([1,N]\) và quan sát thấy các chuồng mang nhãn \(a_1,\dots,a_K\) được nối thành một chu trình theo thứ tự đó. Tức là, các chuồng \(a_i\) và \(a_{i+1}\) được nối với nhau với mọi \(1\le i<K\), đồng thời \(a_K\) và \(a_1\) cũng được nối với nhau. Tất cả \(a_i\) đôi một khác nhau.

Tiếp theo, Bessie cũng gán cho mỗi chuồng một nhãn số nguyên khác nhau trong đoạn \([1,N]\) và quan sát thấy các chuồng mang nhãn \(b_1,\dots,b_K\) được nối thành một chu trình theo thứ tự đó. Tất cả \(b_i\) đôi một khác nhau.

Một số chuồng (có thể không có chuồng nào hoặc là tất cả các chuồng) được Annabelle và Bessie gán cùng một nhãn. Hãy tính số lượng lớn nhất có thể của các chuồng được Annabelle và Bessie gán cùng một nhãn.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(K\).

Dòng tiếp theo chứa \(a_1,\dots,a_K\).

Dòng tiếp theo chứa \(b_1,\dots,b_K\).

Dữ liệu ra

In số điểm bất động lớn nhất.

Ví dụ

6 3
1 2 3
2 3 1

6

6 3
1 2 3
4 5 6

0

6 4
1 2 3 4
4 3 2 5

4

Phân nhóm

• Dữ liệu 4–5: \(N\le 8\).
• Dữ liệu 6–8: \(N\le 5000\).
• Dữ liệu 9–15: Không có ràng buộc bổ sung.

Nguồn

USACO 2023 December Contest, Silver — Cycle Correspondence: https://usaco.org/index.php?page=viewproblem2&cpid=1351

Tác giả bài toán: Benjamin Qi

Bessie là một con bò robot, hay còn gọi là bò cyborg. Cô đang ở trên một trục số và cố gắng bắn một loạt \(T\) mục tiêu (\(1\leq T\leq 10^5\)) nằm tại các vị trí đôi một khác nhau. Bessie bắt đầu tại vị trí \(0\) và thực hiện một xâu gồm \(C\) lệnh (\(1\leq C\leq 10^5\)), mỗi lệnh là L, F hoặc R:

• L: Bessie di chuyển sang trái một đơn vị.
• R: Bessie di chuyển sang phải một đơn vị.
• F: Bessie bắn. Nếu có một mục tiêu tại vị trí hiện tại của Bessie, mục tiêu đó bị bắn trúng và phá hủy, đồng thời không thể bị bắn trúng lần nữa.

Nếu bạn được phép đổi nhiều nhất một lệnh trong xâu thành một lệnh khác trước khi Bessie bắt đầu thực hiện, số mục tiêu lớn nhất Bessie có thể bắn trúng là bao nhiêu?

Dữ liệu vào

Dòng đầu tiên chứa \(T\) và \(C\).

Dòng tiếp theo chứa vị trí của \(T\) mục tiêu, là các số nguyên đôi một khác nhau trong đoạn \([-C,C]\).

Dòng tiếp theo chứa xâu lệnh độ dài \(C\), chỉ gồm các ký tự F, L và R.

Dữ liệu ra

In số mục tiêu lớn nhất Bessie có thể bắn trúng sau khi đổi nhiều nhất một lệnh trong xâu.

Ví dụ

3 7
0 -1 1
LFFRFRR

3

Lệnh    | Vị trí   | Tổng mục tiêu đã bắn trúng
--------+----------+---------------------------
Bắt đầu |  0       | 0
L       | -1       | 0
F       | -1       | 1
F       | -1       | 1 (không thể phá hủy một mục tiêu nhiều lần)
R       |  0       | 1
F       |  0       | 2
R       |  1       | 2
R       |  2       | 2

Lệnh    | Vị trí   | Tổng mục tiêu đã bắn trúng
--------+----------+---------------------------
Bắt đầu |  0       | 0
L       | -1       | 0
F       | -1       | 1
F       | -1       | 1 (không thể phá hủy một mục tiêu nhiều lần)
R       |  0       | 1
F       |  0       | 2
R       |  1       | 2
F       |  1       | 3

1 5
0
FFFFF

1

5 6
1 2 3 4 5
FFRFRF

3

Phân nhóm

• Dữ liệu 4–6: \(T,C\le 1000\).
• Dữ liệu 7–15: Không có ràng buộc bổ sung.

Nguồn

USACO 2023 December Contest, Silver — Target Practice: https://usaco.org/index.php?page=viewproblem2&cpid=1352

Tác giả bài toán: Suhas Nagar