USACO 2018 - US Open - Hạng Vàng

Để 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 cài đặt ban đầu của Bessie 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.

Sau khi thử mã trên một số mảng, Bessie nhận ra một điều thú vị: trong khi các phần tử lớn có thể được đẩy về cuối mảng rất nhanh, các phần tử nhỏ có thể mất rất nhiều thời gian để “nổi” lên đầu mảng (cô nghi rằng thuật toán có tên như vậy chính vì lý do này). Để cố gắng giảm bớt vấn đề, Bessie sửa mã để trong mỗi vòng lặp chính, mảng được quét xuôi rồi quét ngược, nhờ đó cả phần tử lớn lẫn phần tử nhỏ đều có cơ hội được đẩy đi một quãng xa trong mỗi vòng lặp chính. Mã của cô giờ đây như sau:

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]
   for i = N-2 downto 0:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
   for i = 0 to N-2:
      if A[i+1] < A[i]:
         sorted = false

Với một mảng đầu vào, hãy dự đoán mã đã sửa đổi 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
8
5
3
2

2

Nguồn

USACO 2018 US Open Contest, Gold — Out of Sorts

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

\(N\) cô bò của bác nông dân John (\(1 \leq N \leq 10^5\)), như thường lệ được đánh số từ \(1 \ldots N\), tình cờ có quá nhiều thời gian rảnh. Vì vậy, chúng đã xây dựng một hệ thống thứ bậc xã hội phức tạp liên quan đến thứ tự bác nông dân John vắt sữa chúng vào mỗi buổi sáng.

Sau nhiều tuần nghiên cứu, bác nông dân John đã ghi nhận \(M\) quan sát về cấu trúc xã hội của đàn bò (\(1 \leq M \leq 50\,000\)). Mỗi quan sát là một danh sách có thứ tự gồm một số cô bò, cho biết những cô bò này phải được vắt sữa theo đúng thứ tự xuất hiện trong danh sách. Ví dụ, nếu một trong các quan sát của bác nông dân John là danh sách 2, 5, 1, thì ông phải vắt sữa bò 2 trước bò 5 vào một thời điểm nào đó, rồi vắt sữa bò 5 trước bò 1 vào một thời điểm nào đó.

Các quan sát của bác nông dân John được xếp theo mức độ ưu tiên, nên mục tiêu của ông là tối đa hóa giá trị \(X\) sao cho thứ tự vắt sữa thỏa mãn các điều kiện trong \(X\) quan sát đầu tiên. Nếu có nhiều thứ tự vắt sữa thỏa mãn \(X\) điều kiện đầu tiên này, bác nông dân John tin rằng theo một truyền thống lâu đời, những cô bò có số nhỏ hơn có thứ bậc cao hơn những cô bò có số lớn hơn, nên ông muốn vắt sữa những cô bò mang số nhỏ hơn trước. Nói chính xác hơn, nếu có nhiều thứ tự vắt sữa thỏa mãn các điều kiện, ông muốn dùng thứ tự nhỏ nhất theo thứ tự từ điển. Một thứ tự \(x\) nhỏ hơn theo thứ tự từ điển so với một thứ tự \(y\) nếu tồn tại một vị trí \(j\) sao cho \(x_i = y_i\) với mọi \(i < j\) và \(x_j < y_j\); nói cách khác, hai thứ tự giống hệt nhau cho tới một vị trí nhất định, và tại đó \(x\) nhỏ hơn \(y\).

Hãy giúp bác nông dân John xác định thứ tự tốt nhất để vắt sữa đàn bò.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(M\). Mỗi dòng trong \(M\) dòng tiếp theo mô tả một quan sát. Dòng \(i+1\) mô tả quan sát \(i\), bắt đầu bằng số lượng bò \(m_i\) được liệt kê trong quan sát, sau đó là danh sách \(m_i\) số nguyên cho biết thứ tự của các cô bò trong quan sát. Tổng tất cả các giá trị \(m_i\) không vượt quá \(200\,000\).

Dữ liệu ra

In ra \(N\) số nguyên cách nhau bởi dấu cách, tạo thành một hoán vị của \(1 \ldots N\), cho biết thứ tự bác nông dân John nên vắt sữa đàn bò.

Ví dụ

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

1 4 2 3

Nguồn

USACO 2018 US Open Contest, Gold — Milking Order

Tác giả bài toán: Jay Leeds.

Bác nông dân John đưa \(N\) cô bò, được đánh số thuận tiện từ \(1 \ldots N\), đến hội chợ của hạt để tham gia cuộc thi tài năng bò thường niên! Cô bò thứ \(i\) có cân nặng \(w_i\) và mức tài năng \(t_i\), đều là các số nguyên.

Khi đến nơi, bác nông dân John khá bất ngờ trước các quy tắc mới của cuộc thi tài năng năm nay:

(i) Phải đưa vào cuộc thi một nhóm bò có tổng cân nặng ít nhất \(W\) (để bảo đảm rằng các đội bò mạnh tham gia tranh tài, chứ không chỉ những cá thể mạnh).

(ii) Nhóm có tỷ lệ tổng tài năng trên tổng cân nặng lớn nhất sẽ chiến thắng.

Bác nông dân John nhận thấy tổng cân nặng của tất cả các cô bò ít nhất là \(W\), nên ông có thể đưa vào thi một đội thỏa mãn điều kiện thứ nhất. Hãy giúp ông xác định tỷ lệ tài năng trên cân nặng tối ưu có thể đạt được với một đội như vậy.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) (\(1 \leq N \leq 250\)) và \(W\) (\(1 \leq W \leq 1000\)). Mỗi dòng trong \(N\) dòng tiếp theo mô tả một cô bò bằng hai số nguyên \(w_i\) (\(1 \leq w_i \leq 10^6\)) và \(t_i\) (\(1 \leq t_i \leq 10^3\)).

Dữ liệu ra

Hãy xác định tỷ lệ lớn nhất có thể giữa tổng tài năng và tổng cân nặng mà bác nông dân John có thể đạt được bằng cách chọn một nhóm bò có tổng cân nặng ít nhất \(W\). Nếu đáp án là \(A\), hãy in \(\lfloor 1000A \rfloor\) để kết quả là một số nguyên. Phép lấy phần nguyên loại bỏ phần thập phân bằng cách làm tròn xuống tới một số nguyên nếu số đang xét chưa phải là số nguyên.

Ví dụ

3 15
20 21
10 11
30 31

1066

Nguồn

USACO 2018 US Open Contest, Gold — Talent Show

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