USACO 2026 - Farmer John Loves Rotations
Xem PDFFarmer John có một mảng \(A\) gồm \(N\) số nguyên (\(1\le N\le 5\cdot 10^5\), \(1\le A_i\le N\)). Ông chọn chỉ số yêu thích \(j\) của mình và lấy ra một tờ giấy chỉ ghi \(A_j\). Sau đó, ông có thể thực hiện thao tác sau một số lần tùy ý:
- Dịch vòng tất cả các phần tử trong \(A\) sang trái một vị trí hoặc sang phải một vị trí. Sau đó, ghi \(A_j\) lên tờ giấy.
Gọi \(S\) là tập hợp các số nguyên phân biệt xuất hiện trong \(A\). Farmer John muốn biết số thao tác ít nhất phải thực hiện để tờ giấy chứa tất cả các số nguyên xuất hiện trong \(S\).
Vì không rõ chỉ số yêu thích của FJ là gì, hãy in đáp án cho mọi chỉ số yêu thích có thể có \(1\le j\le N\). Lưu ý rằng đối với mỗi chỉ số, \(A\) được khôi phục về trạng thái ban đầu trước khi thực hiện bất kỳ thao tác nào.
Dữ liệu vào
Dòng đầu tiên chứa \(N\).
Dòng tiếp theo chứa \(A_1,A_2,\ldots,A_N\).
Dữ liệu ra
In ra \(N\) số nguyên cách nhau bởi dấu cách, trong đó số nguyên thứ \(i\) là đáp án khi chỉ số yêu thích của Farmer John là \(j=i\).
Ví dụ
Ví dụ 1
Input
6
1 2 3 1 3 4Output
4 3 3 4 3 3Note
Các số phân biệt là \(S=\{1,2,3,4\}\). Giả sử chỉ số yêu thích của Farmer John là \(j=1\). Ban đầu, ông ghi \(A_1=1\) lên một tờ giấy. Ta có thể theo dõi mảng \(A\) sau mỗi lần Farmer John dịch vòng:
-
Dịch vòng sang phải: FJ ghi \(A_1=4\).
4 1 2 3 1 3 -
Dịch vòng sang trái: FJ lại ghi \(A_1=1\).
1 2 3 1 3 4 -
Dịch vòng sang trái: FJ ghi \(A_1=2\).
2 3 1 3 4 1 -
Dịch vòng sang trái: FJ ghi \(A_1=3\).
3 1 3 4 1 2
Đến lúc này, Farmer John đã ghi mọi số trong \(S\) bằng \(4\) thao tác.
Ví dụ 2
Input
12
1 1 2 1 1 3 1 1 4 1 1 1Output
8 7 6 7 8 9 8 7 6 7 8 9Phân nhóm
- Inputs 3–5: \(N\le 500\).
- Inputs 6–8: \(N\le 10^4\).
- Inputs 9–17: Không có ràng buộc bổ sung.
Nguồn
USACO 2026 Contest 2, Silver — Farmer John Loves Rotations. Tác giả: Chongtian Ma.
Kỳ thi:
- USACO 2026 - Kỳ thi 2 - Hạng Bạc (30 Tháng 1., 2026)
Bình luận