USACO 2025 - Tháng 2 - Hạng Bạc

Farmer John có \(N\) (\(1\leq N\leq 2\cdot 10^5\)) con bò trong một hàng \(a\). Con bò thứ \(i\) tính từ đầu hàng \(a\) được gắn nhãn là số nguyên \(a_i\) (\(1\leq a_i\leq N\)). Nhiều con bò có thể mang cùng một nhãn.

FJ sẽ tạo một hàng khác \(b\) theo cách sau:

• Ban đầu, \(b\) rỗng.
• Trong khi \(a\) chưa rỗng, lấy con bò ở đầu hàng \(a\) ra và có thể thêm con bò đó vào cuối hàng \(b\).

FJ muốn tạo hàng \(b\) sao cho dãy nhãn trong \(b\) từ đầu đến cuối là lớn nhất theo thứ tự từ điển (xem ghi chú).

Trước khi tạo hàng \(b\), ông có thể thực hiện thao tác sau nhiều nhất một lần:

• Chọn một con bò trong hàng \(a\) và chuyển nó đến bất kỳ vị trí nào nằm trước vị trí hiện tại của nó.

Giả sử FJ thực hiện tối ưu thao tác nói trên nhiều nhất một lần, hãy in ra dãy nhãn lớn nhất theo thứ tự từ điển của \(b\) mà ông có thể đạt được.

Mỗi dữ liệu vào gồm \(T\) (\(1\leq T\leq 100\)) trường hợp kiểm thử độc lập.

Dữ liệu vào

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

Dòng đầu tiên của mỗi trường hợp kiểm thử chứa \(N\).

Dòng thứ hai của mỗi trường hợp kiểm thử chứa \(N\) số nguyên cách nhau bởi dấu cách \(a_1,a_2,\ldots,a_N\).

Đảm bảo tổng \(N\) trên tất cả các trường hợp kiểm thử không vượt quá \(10^6\).

Dữ liệu ra

Với mỗi trường hợp kiểm thử, in hàng \(b\) lớn nhất theo thứ tự từ điển trên một dòng mới.

Ví dụ

3
5
4 3 2 1 3
6
5 1 2 6 3 4
6
4 1 3 2 1 1

4 3 3 2 1
6 5 4
4 3 2 1 1

Phân nhóm

• Dữ liệu 2–4: \(N\leq 100\).
• Dữ liệu 5–8: \(N\leq 750\).
• Dữ liệu 9–18: Không có ràng buộc bổ sung.

Ghi chú

Nhắc lại rằng một dãy \(s\) lớn hơn một dãy \(t\) theo thứ tự từ điển khi và chỉ khi một trong các điều sau đúng:

• Tại vị trí đầu tiên \(i\) mà \(s_i\neq t_i\), ta có \(s_i>t_i\).
• Nếu không tồn tại \(i\) như vậy, \(s\) dài hơn \(t\).

Nguồn

USACO 2025 February Contest, Silver — The Best Lineup. Tác giả: Chongtian Ma, Haokai Ma, Andrew Li.

https://usaco.org/index.php?page=viewproblem2&cpid=1494

Bessie đang giúp Elsie chuẩn bị cho bài kiểm tra từ vựng sắp tới. Các từ được kiểm tra sẽ lấy từ một ngân hàng gồm \(M\) từ phân biệt, trong đó không từ nào trong ngân hàng là tiền tố của một từ khác trong ngân hàng.

Khi ngân hàng còn từ, Bessie sẽ chọn một từ, xóa nó khỏi ngân hàng và đọc cho Elsie từng ký tự từ trái sang phải. Nhiệm vụ của Elsie là báo cho Bessie ngay khi cô có thể xác định duy nhất từ đó; khi ấy Bessie sẽ ngừng đọc.

Bessie đã quyết định đọc các từ trong ngân hàng theo thứ tự \(w_1,w_2,\dots,w_M\). Nếu Elsie trả lời nhanh nhất có thể, Bessie sẽ đọc bao nhiêu ký tự của mỗi từ?

Các từ được cho dưới dạng nén. Trước tiên, ta định nghĩa \(N+1\) (\(1\le N\le 10^6\)) từ phân biệt, rồi ngân hàng từ sẽ gồm tất cả những từ không phải là tiền tố của một từ khác. Các từ được định nghĩa như sau:

• Ban đầu, từ thứ \(0\) là xâu rỗng.
• Sau đó, với mỗi \(1\le i\le N\), từ thứ \(i\) bằng từ thứ \(p_i\) cộng thêm một ký tự ở cuối (\(0\le p_i<i\)). Các ký tự được chọn sao cho cả \(N+1\) từ đều phân biệt.

Dữ liệu vào

Dòng đầu tiên chứa \(N\), trong đó \(N+1\) là số từ được cho dưới dạng nén.

Dòng tiếp theo chứa \(p_1,p_2,\dots,p_N\), trong đó \(p_i\) biểu thị rằng từ thứ \(i\) được tạo bằng cách lấy từ thứ \(p_i\) rồi thêm một ký tự vào cuối.

Gọi \(M\) là số từ không phải tiền tố của bất kỳ từ nào khác. \(M\) dòng tiếp theo chứa lần lượt \(w_1,w_2,\dots,w_M\), nghĩa là từ thứ \(w_i\) sẽ được đọc ở vị trí thứ \(i\). Đảm bảo các từ được đọc tạo thành một hoán vị của các từ trong ngân hàng.

Dữ liệu ra

In ra \(M\) dòng, trong đó dòng thứ \(i\) chứa số ký tự của từ thứ \(i\) trong thứ tự đọc mà Bessie đọc.

Ví dụ

5
0 1 2 3 4
5

0

4
0 0 1 1
4
3
2

2
1
0

4
0 0 1 1
2
3
4

1
2
0

Phân nhóm

• Dữ liệu 4–5: Không từ nào có độ dài lớn hơn \(20\).
• Dữ liệu 6–10: Tổng độ dài của tất cả các từ trong ngân hàng không vượt quá \(10^7\).
• Dữ liệu 11–18: Không có ràng buộc bổ sung.

Nguồn

USACO 2025 February Contest, Silver — Vocabulary Quiz. Tác giả: Benjamin Qi.

https://usaco.org/index.php?page=viewproblem2&cpid=1495

Bessie, cô bò thông thái, vừa khám phá ra một niềm say mê mới — phép thuật toán học! Một ngày nọ, khi đang chạy qua những cánh đồng trong trang trại của Farmer John, cô bắt gặp hai đống cỏ khô bị phù phép. Đống thứ nhất có \(a\) kiện và đống thứ hai có \(b\) kiện (\(1\le a,b\le 10^{18}\)).

Bên cạnh đống cỏ, bị vùi một nửa trong đất, cô tìm thấy một cuộn giấy cổ. Khi cô mở nó ra, những ký tự phát sáng hé lộ một lời tiên tri:

Để thực hiện sắc lệnh của Đại Đồng Cỏ, người được chọn phải biến đổi hai đống cỏ nhỏ bé này thành chính xác \(c\) và \(d\) kiện — không hơn, không kém.

Bessie nhận ra cô chỉ có thể thi triển hai phép thuật sau:

• Cô có thể triệu hồi thêm số kiện cỏ vào đống thứ nhất bằng đúng số kiện hiện có trong đống thứ hai.
• Cô có thể triệu hồi thêm số kiện cỏ vào đống thứ hai bằng đúng số kiện hiện có trong đống thứ nhất.

Cô phải thực hiện các thao tác tuần tự, nhưng có thể thực hiện chúng bao nhiêu lần và theo bất kỳ thứ tự nào. Cô phải đạt chính xác \(c\) kiện ở đống thứ nhất và \(d\) kiện ở đống thứ hai (\(1\le c,d\le 10^{18}\)).

Với mỗi trong số \(T\) (\(1\le T\le 10^4\)) trường hợp kiểm thử độc lập, hãy in ra số thao tác tối thiểu cần thiết để hoàn thành lời tiên tri; nếu không thể, in ra \(-1\).

Dữ liệu vào

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

\(T\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên \(a,b,c,d\).

Dữ liệu ra

In ra \(T\) dòng, là đáp án cho từng trường hợp kiểm thử.

Ví dụ

4
5 3 5 2
5 3 8 19
5 3 19 8
5 3 5 3

-1
3
-1
0

1
1 1 1 1000000000000000000

999999999999999999

Phân nhóm

• Dữ liệu 3–4: \(\max(c,d)\le 20\cdot\min(a,b)\).
• Dữ liệu 5–7: \(T\le 10\) và \(a,b,c,d\le 10^6\).
• Dữ liệu 8–12: Không có ràng buộc bổ sung.

Nguồn

USACO 2025 February Contest, Silver — Transforming Pairs. Tác giả: Benjamin Qi.

https://usaco.org/index.php?page=viewproblem2&cpid=1496