USACO 2018 - US Open - Hạng Bạc

Để chuẩn bị cho những cơ hội nghề nghiệp lâu dài bên ngoài trang trại, cô bò Bessie đã bắt đầu học các thuật toán từ nhiều trang web lập trình trực tuyến.

Cho đến nay, thuật toán yêu thích của cô là “sắp xếp nổi bọt”. Dưới đây là cách Bessie cài đặt thuật toán này bằng mã dành cho bò để sắp xếp một mảng \(A\) có độ dài \(N\).

sorted = false
while (not sorted):
   sorted = true
   moo
   for i = 0 to N-2:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
         sorted = false

Hóa ra lệnh moo trong mã dành cho bò không làm gì ngoài việc in ra moo. Thật kỳ lạ, Bessie dường như nhất quyết chèn lệnh này vào nhiều vị trí trong mã của mình.

Với một mảng đầu vào, hãy dự đoán mã của Bessie sẽ in moo bao nhiêu lần.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) (\(1 \leq N \leq 100\,000\)). \(N\) dòng tiếp theo mô tả lần lượt \(A[0] \ldots A[N-1]\); mỗi phần tử là một số nguyên thuộc khoảng \(0 \ldots 10^9\). Các phần tử đầu vào không nhất thiết đôi một khác nhau.

Dữ liệu ra

In ra số lần moo được in.

Ví dụ

5
1
5
3
8
2

4

Nguồn

USACO 2018 US Open Contest, Silver — Out of Sorts

Tác giả bài toán: Brian Dean.

Đó là một ngày hè nóng nực ở trang trại, và bác nông dân John đang phục vụ nước chanh cho \(N\) cô bò! Cả \(N\) cô bò (được đánh số thuận tiện từ \(1 \dots N\)) đều thích nước chanh, nhưng có cô thích hơn những cô khác. Cụ thể, bò \(i\) sẵn lòng đứng trong hàng với nhiều nhất \(w_i\) cô bò đứng trước mình để nhận nước chanh. Hiện tại, cả \(N\) cô bò đều đang ở ngoài đồng, nhưng ngay khi bác nông dân John rung chuông gọi bò, chúng sẽ lập tức kéo đến quầy nước chanh của ông. Tất cả sẽ đến trước khi ông bắt đầu phục vụ, nhưng không có hai cô bò nào đến cùng một lúc. Hơn nữa, khi bò \(i\) đến, cô ấy sẽ vào hàng khi và chỉ khi trong hàng hiện có không quá \(w_i\) cô bò.

Bác nông dân John muốn chuẩn bị trước một lượng nước chanh nhưng không muốn lãng phí. Số cô bò vào hàng có thể phụ thuộc vào thứ tự chúng đến. Hãy giúp ông tìm số cô bò ít nhất có thể vào hàng.

Dữ liệu vào

Dòng đầu tiên chứa \(N\), và dòng thứ hai chứa \(N\) số nguyên cách nhau bởi dấu cách \(w_1, w_2, \dots, w_N\). Bảo đảm rằng \(1 \leq N \leq 10^5\) và \(0 \leq w_i \leq 10^9\) với mỗi bò \(i\).

Dữ liệu ra

Trong tất cả các thứ tự mà đàn bò có thể đến, in ra số cô bò ít nhất có thể vào hàng.

Ví dụ

5
7 1 400 2 2

3

Nguồn

USACO 2018 US Open Contest, Silver — Lemonade Line

Tác giả bài toán: Dhruv Rohatgi.

Đàn bò đã nghĩ ra một trò chơi mới đầy sáng tạo, nhưng thật bất ngờ lại đặt cho nó cái tên kém sáng tạo nhất có thể: “Moo”.

Trò Moo diễn ra trên một lưới gồm \(N \times N\) ô vuông. Một cô bò chiếm một ô bằng cách kêu “moo!” và viết số ID của mình vào ô đó.

Khi trò chơi kết thúc, mỗi ô đều chứa một số. Lúc này, một cô bò thắng nếu cô ấy đã tạo ra một vùng ô liên thông có kích thước ít nhất bằng mọi vùng khác. Một “vùng” được định nghĩa là một nhóm ô đều mang cùng một số ID, trong đó mỗi ô trong vùng kề trực tiếp với một ô khác trong cùng vùng ở phía trên, phía dưới, bên trái hoặc bên phải; các ô kề chéo không được tính.

Vì chơi riêng lẻ hơi nhàm chán, đàn bò cũng muốn ghép cặp để thi đấu theo đội. Một đội gồm hai cô bò có thể tạo ra một vùng như trên, nhưng giờ đây các ô trong vùng có thể thuộc về một trong hai cô bò của đội.

Với trạng thái cuối cùng của bàn chơi, hãy giúp đàn bò tính số ô trong vùng lớn nhất do một cô bò sở hữu, và số ô trong vùng lớn nhất mà một đội hai cô bò có thể tuyên bố sở hữu. Một vùng do đội hai cô bò tuyên bố sở hữu chỉ được tính nếu nó chứa số ID của cả hai cô bò trong đội, chứ không chỉ của một cô.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) (\(1 \leq N \leq 250\)). Mỗi dòng trong \(N\) dòng tiếp theo chứa \(N\) số nguyên, mỗi số thuộc khoảng \(0 \ldots 10^6\), mô tả trạng thái cuối cùng của bàn chơi. Trên bàn bảo đảm có ít nhất hai số ID khác nhau.

Dữ liệu ra

Dòng đầu tiên in kích thước vùng lớn nhất do một cô bò sở hữu. Dòng thứ hai in kích thước vùng lớn nhất mà một đội hai cô bò có thể tuyên bố sở hữu.

Ví dụ

4
2 3 9 3
4 9 9 1
9 9 1 7
2 1 1 9

5
10

Nguồn

USACO 2018 US Open Contest, Silver — Multiplayer Moo

Tác giả bài toán: Brian Dean.