USACO 2025 - Cow Checkups

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Dạng bài
Ngôn ngữ cho phép
Assembly, Awk, C, C#, C++, Clang, Cobol, D, Groovy, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, Swift
Điểm: 1500 (p) Thời gian: 4.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Lưu ý: Chúng tôi đề xuất sử dụng một ngôn ngữ khác Python để đạt trọn điểm bài này.

\(N\) (\(1 \leq N \leq 7500\)) con bò của Farmer John đang đứng thành một hàng, với bò \(1\) ở đầu hàng và bò \(N\) ở cuối hàng. Các con bò của FJ cũng thuộc nhiều loài khác nhau. Ông ký hiệu mỗi loài bằng một số nguyên từ \(1\) đến \(N\). Con bò thứ \(i\) tính từ đầu hàng thuộc loài \(a_i\) (\(1 \leq a_i \leq N\)).

FJ đang đưa đàn bò đến khám tại một bệnh viện bò địa phương. Tuy nhiên, bác sĩ thú y cho bò rất kén chọn và chỉ muốn khám con bò thứ \(i\) trong hàng nếu nó thuộc loài \(b_i\) (\(1 \leq b_i \leq N\)).

FJ lười biếng và không muốn sắp xếp lại hoàn toàn đàn bò. Ông sẽ thực hiện thao tác sau đúng một lần.

  • Chọn hai số nguyên \(l\) và \(r\) sao cho \(1 \leq l \le r \leq N\). Đảo ngược thứ tự các con bò nằm giữa con bò thứ \(l\) và con bò thứ \(r\) trong hàng, tính cả hai đầu.

FJ muốn đo lường mức độ hiệu quả của cách làm này. Với mỗi \(c=0 \ldots N\), hãy giúp FJ tìm số thao tác phân biệt \((l,r)\) khiến đúng \(c\) con bò được khám. Hai thao tác \((l_1,r_1)\) và \((l_2,r_2)\) là khác nhau nếu \(l_1 \neq l_2\) hoặc \(r_1 \neq r_2\).

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(N\).

Dòng thứ hai chứa \(a_1, a_2, \ldots, a_N\).

Dòng thứ ba chứa \(b_1, b_2, \ldots, b_N\).

Dữ liệu ra

In \(N+1\) dòng, trong đó dòng thứ \(i\) chứa số thao tác phân biệt \((l,r)\) khiến \(i-1\) con bò được khám.

Ví dụ

Ví dụ 1

Input 
3
1 3 2
3 2 1
Output 
3
3
0
0
Giải thích

Nếu FJ chọn \((l=1,r=1)\), \((l=2,r=2)\) hoặc \((l=3,r=3)\) thì không có con bò nào được khám. Lưu ý rằng các thao tác này không thay đổi vị trí của bất kỳ con bò nào.

Các thao tác sau khiến một con bò được khám:

  • \(l=1,r=2\): FJ đảo thứ tự con bò thứ nhất và thứ hai, nên loài của các con bò trong hàng mới là \([3,1,2]\). Con bò thứ nhất sẽ được khám.
  • \(l=2,r=3\): FJ đảo thứ tự con bò thứ hai và thứ ba, nên loài của các con bò trong hàng mới là \([1,2,3]\). Con bò thứ hai sẽ được khám.
  • \(l=1,r=3\): FJ đảo thứ tự con bò thứ nhất, thứ hai và thứ ba, nên loài của các con bò trong hàng mới là \([2,3,1]\). Con bò thứ ba sẽ được khám.

Ví dụ 2

Input 
3
1 2 3
1 2 3
Output 
0
3
0
3
Giải thích

Ba thao tác có thể khiến \(3\) con bò được khám là \((l=1,r=1)\), \((l=2,r=2)\) và \((l=3,r=3)\).

Ví dụ 3

Input 
7
1 3 2 2 1 3 2
3 2 2 1 2 3 1
Output 
0
6
14
6
2
0
0
0
Giải thích

Hai thao tác có thể khiến \(4\) con bò được khám là \((l=4,r=5)\) và \((l=5,r=7)\).

Phân nhóm

  • Inputs 4-6: \(N\le 100\).
  • Inputs 7-13: Không có ràng buộc bổ sung.

Nguồn

USACO 2025 January Contest, Bronze — Cow Checkups

Đề bài: https://usaco.org/index.php?page=viewproblem2&cpid=1469

Tác giả đề: Chongtian Ma và Haokai Ma

Bình luận

Mới nhất
Tải bình luận...

Không có bình luận nào.

Kỳ thi: