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

Farmer John có \(N\) món quà được đánh số \(1\ldots N\) dành cho \(N\) con bò cũng được đánh số \(1\ldots N\) (\(1\le N\le 500\)). Mỗi con bò có một danh sách mong muốn là một hoán vị của toàn bộ \(N\) món quà; con bò thích những món xuất hiện sớm hơn trong danh sách hơn những món xuất hiện muộn hơn.

FJ đã lười biếng và chỉ gán quà \(i\) cho bò \(i\) với mọi \(i\). Giờ đây, đàn bò đã tụ họp và quyết định phân phối lại các món quà sao cho sau khi phân phối lại, mỗi con bò nhận được chính món quà ban đầu của mình hoặc một món mà nó thích hơn món ban đầu.

Với mỗi \(i\) từ \(1\) đến \(N\), hãy tìm món quà được yêu thích nhất mà bò \(i\) có thể hy vọng nhận được sau khi phân phối lại.

Dữ liệu vào

Dòng đầu tiên chứa \(N\). Mỗi dòng trong \(N\) dòng tiếp theo chứa danh sách ưu tiên của một con bò. Bảo đảm rằng mỗi dòng là một hoán vị của \(1\dots N\).

Dữ liệu ra

In ra \(N\) dòng; dòng thứ \(i\) chứa món quà được yêu thích nhất mà bò \(i\) có thể hy vọng nhận được sau khi phân phối lại.

Phân nhóm

• Các test 2–3 thỏa mãn \(N\le 8\).
• Các test 4–11 không có ràng buộc bổ sung.

Ví dụ

4
1 2 3 4
1 3 2 4
1 2 3 4
1 2 3 4

1
3
2
4

Nguồn

USACO 2022 February Contest, Silver — Redistributing Gifts: https://usaco.org/index.php?page=viewproblem2&cpid=1206

Tác giả: Benjamin Qi.

Bessie đang học cách điều khiển một rô-bốt mà cô mới được tặng.

Rô-bốt bắt đầu tại điểm \((0,0)\) trên mặt phẳng tọa độ và Bessie muốn nó kết thúc tại điểm \((x_g,y_g)\). Ban đầu Bessie có danh sách gồm \(N\) (\(1\le N\le 40\)) chỉ dẫn dành cho rô-bốt; chỉ dẫn thứ \(i\) sẽ di chuyển rô-bốt sang phải \(x_i\) đơn vị và lên trên \(y_i\) đơn vị (tương ứng là sang trái hoặc xuống dưới khi \(x_i\) hoặc \(y_i\) âm).

Với mỗi \(K\) từ \(1\) đến \(N\), hãy giúp Bessie đếm số cách chọn \(K\) chỉ dẫn trong \(N\) chỉ dẫn ban đầu sao cho sau khi thực hiện \(K\) chỉ dẫn đó, rô-bốt kết thúc tại điểm \((x_g,y_g)\).

Lưu ý: giới hạn thời gian và bộ nhớ của bài này lần lượt là 4 giây và 512 MB, gấp đôi mức mặc định.

Dữ liệu vào

Dòng đầu tiên chứa \(N\). Dòng tiếp theo chứa \(x_g\) và \(y_g\), mỗi số nằm trong khoảng \(-10^9\ldots 10^9\). \(N\) dòng cuối mô tả các chỉ dẫn. Mỗi dòng có hai số nguyên \(x_i\) và \(y_i\), cũng nằm trong khoảng \(-10^9\ldots 10^9\).

Bảo đảm rằng \((x_g,y_g)\ne(0,0)\) và \((x_i,y_i)\ne(0,0)\) với mọi \(i\).

Dữ liệu ra

In \(N\) dòng; với mỗi \(K\) từ \(1\) đến \(N\), dòng thứ \(K\) là số cách Bessie có thể chọn \(K\) chỉ dẫn trong \(N\) chỉ dẫn ban đầu.

Phân nhóm

• Các test 2–4 thỏa mãn \(N\le 20\).
• Các test 5–16 không có ràng buộc bổ sung.

Ví dụ

7
5 10
-2 0
3 0
4 0
5 0
0 10
0 -10
0 10

0
2
0
3
0
1
0

(-2,0) (3,0) (4,0) (0,10) (0,-10) (0,10) (1 2 3 5 6 7)
(-2,0) (3,0) (4,0) (0,10) (1 2 3 5)
(-2,0) (3,0) (4,0) (0,10) (1 2 3 7)
(5,0) (0,10) (0,-10) (0,10) (4 5 6 7)
(5,0) (0,10) (4 5)
(5,0) (0,10) (4 7)

(0,0) -> (-2,0) -> (1,0) -> (5,0) -> (5,10) -> (5,0) -> (5,10)

Nguồn

USACO 2022 February Contest, Silver — Robot Instructions: https://usaco.org/index.php?page=viewproblem2&cpid=1207

Tác giả: Alex Liang.

Farmer John đã chậm trễ trong việc sắp xếp hộp thư đến. Màn hình của ông được bố trí với một danh sách thư mục dọc ở bên trái và một danh sách email dọc ở bên phải. Có tổng cộng \(M\) thư mục, được đánh số \(1\ldots M\) (\(1\le M\le 10^4\)). Hộp thư đến hiện có \(N\) email được đánh số \(1\ldots N\) (\(1\le N\le 10^5\)); email thứ \(i\) cần được lưu vào thư mục \(f_i\) (\(1\le f_i\le M\)).

Màn hình của FJ khá nhỏ nên ông chỉ có thể xem đồng thời \(K\) (\(1\le K\le\min(N,M)\)) thư mục và \(K\) email. Ban đầu, màn hình hiển thị các thư mục \(1\ldots K\) ở bên trái và các email \(1\ldots K\) ở bên phải. Để truy cập những thư mục và email khác, ông phải cuộn qua từng danh sách tương ứng. Ví dụ, nếu cuộn xuống một vị trí trong danh sách thư mục, màn hình sẽ hiển thị các thư mục \(2\ldots K+1\); cuộn tiếp xuống một vị trí sẽ hiển thị các thư mục \(3\ldots K+2\). Khi FJ kéo một email vào một thư mục, email đó biến mất khỏi danh sách và những email đứng sau nó dịch lên một vị trí. Ví dụ, nếu các email \(1,2,3,4,5\) đang được hiển thị và FJ kéo email \(3\) vào đúng thư mục, danh sách email sẽ hiển thị \(1,2,4,5,6\). FJ chỉ có thể kéo một email vào đúng thư mục mà nó cần được lưu.

Đáng tiếc, con lăn chuột của FJ bị hỏng nên ông chỉ có thể cuộn xuống, không thể cuộn lên. Cách duy nhất để ông có thể phần nào cuộn lên là khi đang xem nhóm \(K\) email cuối cùng trong danh sách email và lưu một email trong số đó. Khi ấy, danh sách lại hiển thị \(K\) email cuối cùng chưa được lưu, về thực chất làm email trên cùng dịch lên một vị trí. Nếu còn ít hơn \(K\) email thì tất cả chúng đều được hiển thị.

Hãy giúp FJ xác định liệu ông có thể lưu tất cả email hay không.

Dữ liệu vào

Dòng đầu tiên chứa \(T\) (\(1\le T\le 10\)), số trường hợp con trong tệp vào; tất cả đều phải được giải đúng để giải được tệp test này. Sau đó là \(T\) trường hợp con. Với mỗi trường hợp con, dòng đầu chứa \(M\), \(N\) và \(K\). Dòng tiếp theo chứa \(f_1\ldots f_N\).

Bảo đảm tổng \(M\) trên tất cả các trường hợp con không vượt quá \(10^4\), và tổng \(N\) trên tất cả các trường hợp con không vượt quá \(10^5\).

Dữ liệu ra

In \(T\) dòng, mỗi dòng chứa YES hoặc NO, cho biết FJ có thể lưu thành công tất cả email trong mỗi trường hợp con trong số \(T\) trường hợp hay không.

Phân nhóm

• Trong các tệp test 2–10, tổng \(M\) trên tất cả các trường hợp con không vượt quá \(10^3\).
• Trong các tệp test 11–12, không có ràng buộc bổ sung.

Ví dụ

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

YES
YES
NO
YES
YES
NO

Nguồn

USACO 2022 February Contest, Silver — Email Filing: https://usaco.org/index.php?page=viewproblem2&cpid=1208

Tác giả: Brian Dean.