USACO 2025 - US Open - Hạng Bạch Kim

Farmer John đang luyện tập để được cấp chứng chỉ lái xe nâng! Trong quá trình huấn luyện, ông cần dọn \(N\) (\(1\le N\le 10^5\)) thùng hàng, được đánh số thuận tiện từ \(1\) đến \(N\), ra khỏi một nhà kho cũ.

Các thùng hàng có thể được mô hình hóa thành những hình chữ nhật song song với các trục trong mặt phẳng hai chiều, trong đó hướng \(+x\) là hướng đông và hướng \(+y\) là hướng bắc. Thùng \(i\) có góc tây nam tại \((x_{i1},y_{i1})\) và góc đông bắc tại \((x_{i2},y_{i2})\). Mọi tọa độ đều là số nguyên trong đoạn \([1,2N]\), và không có hai góc thuộc hai hình chữ nhật khác nhau có cùng tọa độ \(x\) hoặc cùng tọa độ \(y\). Mọi thùng đều có diện tích khác không và không có hai thùng nào giao nhau.

Farmer John dự định lần lượt đưa từng thùng ra ngoài qua lối vào phía tây nam của nhà kho. Tuy nhiên, do giới hạn vật lý của xe nâng, ông chỉ có thể đưa một thùng ra nếu không có phần nào của bất kỳ thùng nào khác vừa nằm về phía nam vừa nằm về phía tây so với góc đông bắc của thùng đó.

Ví dụ với \(N=4\) được minh họa dưới đây. Để đưa thùng \(4\) ra, vùng tô đậm không được chứa bất kỳ thùng nào khác. Thùng \(2\) và \(3\) cản thùng \(4\), còn thùng \(1\) thì không.

Hãy giúp Farmer John quyết định cách đưa tất cả các thùng ra ngoài! Chương trình của bạn phải hoạt động ở hai chế độ riêng biệt, được xác định bởi cờ nguyên \(M\):

• Chế độ 1 (\(M=1\)): Sinh một hoán vị của \(1,\dots,N\) mô tả một thứ tự dỡ thùng hợp lệ. Nếu có nhiều thứ tự hợp lệ, hãy tìm bất kỳ thứ tự nào. Có thể chứng minh rằng luôn tồn tại một thứ tự như vậy.
• Chế độ 2 (\(M=2\)): Với mỗi \(k=1,\dots,N\), in \(\texttt{1}\) nếu Farmer John có thể đưa thùng \(k\) ra sau khi các thùng \(1,\dots,k-1\) đã được đưa ra, và in \(\texttt{0}\) nếu không thể.

Dữ liệu vào

Mỗi dữ liệu vào gồm \(T\) (\(1\le T\le 10\)) bộ dữ liệu độc lập. Đảm bảo tổng tất cả các giá trị \(N\) trong một dữ liệu vào không vượt quá \(5\cdot 10^5\).

Dòng đầu tiên chứa \(T\) và \(M\). (Lưu ý rằng \(M\) giống nhau cho mọi bộ dữ liệu.) Sau đó mỗi bộ dữ liệu có định dạng như sau:

• Dòng đầu tiên chứa một số nguyên \(N\).
• Mỗi dòng trong \(N\) dòng tiếp theo chứa bốn số nguyên cách nhau bởi dấu cách \(x_{i1},y_{i1},x_{i2},y_{i2}\), là vị trí góc tây nam và góc đông bắc của thùng \(i\).

Dữ liệu ra

Với mỗi bộ dữ liệu:

• Nếu \(M=1\), in một dòng gồm \(N\) số nguyên cách nhau bởi dấu cách, trong đó số nguyên thứ \(j\) là nhãn của thùng thứ \(j\) cần đưa ra.
• Nếu \(M=2\), in một dòng gồm một xâu nhị phân dài \(N\) ký tự, mô tả đáp án cho mỗi \(k=1,\dots,N\).

Ví dụ

2 1
4
1 6 2 8
6 2 7 3
3 1 4 7
5 4 8 5
3
1 5 3 6
4 1 5 2
2 3 6 4

1 3 2 4
2 3 1

2 2
4
1 6 2 8
6 2 7 3
3 1 4 7
5 4 8 5
3
1 5 3 6
4 1 5 2
2 3 6 4

1011
011

Phân nhóm

• Dữ liệu 3–5: \(M=1\), \(N\le 1000\).
• Dữ liệu 6: \(M=2\), \(N\le 1000\).
• Dữ liệu 7–13: \(M=1\), không có ràng buộc bổ sung.
• Dữ liệu 14–16: \(M=2\), không có ràng buộc bổ sung.

Đề bài: Austin Geng.

Nguồn

USACO 2025 US Open Contest, Platinum — Forklift Certified: https://usaco.org/index.php?page=viewproblem2&cpid=1524

Farmer John có \(N\) con bò (\(2\leq N\leq 5\cdot 10^6\)) và đang cố nhờ vào tính lười biếng của chúng để sắp xếp một mảng số nguyên không âm \(A\) độ dài \(N\). Ông có rất nhiều thùng nặng nên xếp các con bò thành một hàng, con bò \(i+1\) đứng sau con bò \(i\), rồi giao \(a_i\) thùng cho con bò \(i\) (\(0\le a_i\)).

Bò vốn lười biếng nên luôn tìm cách đẩy việc cho người khác. Theo thứ tự từ bò \(1\) đến bò \(N-1\), mỗi con bò nhìn con bò đứng sau mình. Nếu bò \(i\) có nhiều thùng hơn hẳn bò \(i+1\), bò \(i\) cho rằng điều này “không công bằng” và đưa một thùng của mình cho bò \(i+1\). Quá trình này lặp lại cho tới khi mọi con bò đều hài lòng.

Sau đó, Farmer John ghi lại số thùng \(b_i\) mà mỗi bò \(i\) đang giữ và tạo mảng \(B\) từ các giá trị này. Nếu \(B=sorted(A)\) thì Farmer John sẽ vui. Không may, Farmer John đã quên tất cả trừ \(Q\) giá trị (\(2\leq Q\leq\min(N,100)\)) trong \(A\). May mắn thay, trong đó có số thùng ông định giao cho con bò đầu tiên và con bò cuối cùng. Mỗi giá trị FJ nhớ được có dạng \(c_i\;v_i\), biểu thị \(a_{c_i}=v_i\) (\(1\leq c_i\leq N\), \(1\le v_i\leq 10^9\)). Hãy xác định số cách khác nhau để điền các giá trị còn thiếu sao cho ông sẽ vui, lấy modulo \(10^9+7\).

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên cách nhau bởi dấu cách \(N\) và \(Q\), lần lượt là số bò và số giá trị được nhớ.

\(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên cách nhau bởi dấu cách \(c_i\;v_i\), biểu thị ban đầu bò \(c_i\) giữ \(v_i\) thùng. Đảm bảo \(c_1=1\), \(c_Q=N\) và \(c_i<c_{i+1}\) (thứ tự các con bò tăng nghiêm ngặt).

Dữ liệu ra

In ra số cách khác nhau modulo \(10^9+7\) để gán các giá trị \(a_i\) sao cho Farmer John sẽ vui sau khi các con bò thực hiện phép sắp xếp lười biếng. Đảm bảo có ít nhất một cách gán hợp lệ.

Ví dụ

3 2
1 3
3 2

2

6 3
1 1
3 3
6 5

89

Phân nhóm

• Dữ liệu 3–4: \(N,v_i\le 100\).
• Dữ liệu 5–6: \(N\le 100\) và \(v_i\leq 10^6\).
• Dữ liệu 7–9: \(N\leq 2\cdot 10^5\) và \(v_i\le 10^6\).
• Dữ liệu 10–12: \(N\leq 2\cdot 10^5\).
• Dữ liệu 13–15: Không có ràng buộc bổ sung.

Đề bài: Suhas Nagar.

Nguồn

USACO 2025 US Open Contest, Platinum — Lazy Sort: https://usaco.org/index.php?page=viewproblem2&cpid=1525

Lưu ý: Giới hạn thời gian của bài này là 4 giây, bằng 2 lần giới hạn mặc định.

Farmer John đã phân bố bò và kiện hàng theo một quy luật kỳ lạ trên trục số bằng quy trình sau:

• Farmer John chọn một số \(M\) (\(1\le M\le 10^{18}\)).
• Farmer John chọn \(N\) (\(1\le N\le 2\cdot 10^4\)) đoạn \([L_i,R_i]\) để phân bố bò (\(1\le L_i\le R_i\le 10^{18}\)). Sau đó, ông đặt bò tại các vị trí \(L_i,L_i+M,L_i+2M,\ldots,R_i\). Đảm bảo \(R_i-L_i\) là bội của \(M\).
• Farmer John chọn \(P\) (\(1\le P\le 2\cdot 10^4\)) đoạn \([A_i,B_i]\) để phân bố kiện hàng (\(1\le A_i\le B_i\le 10^{18}\)). Sau đó, ông đặt các kiện hàng tại các vị trí \(A_i,A_i+M,A_i+2M,\ldots,B_i\). Đảm bảo \(B_i-A_i\) là bội của \(M\).

Sau khi bò và kiện hàng được phân bố, Farmer John muốn biết các con bò mất bao lâu để nhặt các kiện hàng. Mỗi giây, bằng chiếc bộ đàm tiện dụng của mình, Farmer John có thể ra lệnh cho một con bò duy nhất di chuyển một đơn vị sang trái hoặc sang phải so với vị trí hiện tại. Nếu một con bò đi đến vị trí có một kiện hàng, nó có thể nhặt kiện hàng đó. Farmer John muốn biết số giây ít nhất cần thiết để các con bò nhặt hết mọi kiện hàng.

Dữ liệu vào

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

\(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(L_i\) và \(R_i\).

\(P\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(A_i\) và \(B_i\).

Dữ liệu ra

In ra một số nguyên, biểu thị thời gian nhỏ nhất để các con bò có thể nhặt hết mọi kiện hàng, với điều kiện mỗi giây ông chỉ có thể ra một lệnh sang trái/phải cho một con bò duy nhất.

Ví dụ

100 3 7
10 10
20 20
30 30
7 7
11 11
13 13
17 17
24 24
26 26
33 33

22

2 1 1
1 5
2 6

3

Phân nhóm

• Dữ liệu 3–4: Đảm bảo tổng số bò và kiện hàng không vượt quá \(2\cdot 10^5\).
• Dữ liệu 5–10: Đảm bảo \(N,P\le 500\).
• Dữ liệu 11–13: Đảm bảo không có hai đoạn phân bố kiện hàng hoặc bò nào giao nhau.
• Dữ liệu 14–20: Không có ràng buộc bổ sung.

Đề bài: Suhas Nagar và Benjamin Qi.

Nguồn

USACO 2025 US Open Contest, Platinum — Package Pickup: https://usaco.org/index.php?page=viewproblem2&cpid=1526