| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2019 - Balance Beam | 100 (p) | 4.0s | 512M |
| 2 | USACO 2019 - Sort It Out | 100 (p) | 4.0s | 512M |
| 3 | USACO 2019 - The Cow Gathering | 100 (p) | 4.0s | 512M |
Để dành tiền xây một ô chuồng mới trong chuồng bò của mình, cô bò Bessie đã bắt đầu biểu diễn tại rạp xiếc địa phương, phô diễn khả năng giữ thăng bằng đáng kinh ngạc khi cẩn thận đi qua đi lại trên một thanh thăng bằng trên cao!
Số tiền Bessie kiếm được từ màn biểu diễn phụ thuộc vào vị trí mà cuối cùng cô có thể nhảy khỏi thanh. Các vị trí trên thanh được đánh số \(0, 1, \ldots, N+1\) từ trái sang phải. Nếu Bessie đi đến vị trí \(0\) hoặc \(N+1\), cô sẽ rơi khỏi một đầu thanh và đáng tiếc không nhận được khoản tiền nào.
Nếu Bessie đang ở vị trí \(k\), cô có thể thực hiện một trong hai hành động sau:
Tung đồng xu. Nếu ra mặt sấp, cô đi đến vị trí \(k-1\); nếu ra mặt ngửa, cô đi đến vị trí \(k+1\) (tức mỗi khả năng xảy ra với xác suất \(\frac{1}{2}\)).
Nhảy khỏi thanh và nhận khoản tiền \(f(k)\) \((0 \leq f(k) \leq 10^9)\).
Bessie nhận ra rằng cô có thể không đảm bảo được một khoản tiền cụ thể nào vì chuyển động của cô bị chi phối bởi những lần tung đồng xu ngẫu nhiên. Tuy nhiên, dựa trên vị trí xuất phát, cô muốn xác định kỳ vọng số tiền mình sẽ nhận được nếu đưa ra một chuỗi quyết định tối ưu ("tối ưu" nghĩa là các quyết định dẫn đến kỳ vọng số tiền cao nhất có thể). Ví dụ, nếu chiến lược của cô mang lại khoản tiền \(10\) với xác suất \(1/2\), khoản tiền \(8\) với xác suất \(1/4\), hoặc \(0\) với xác suất \(1/4\), thì kỳ vọng số tiền của cô là trung bình có trọng số \(10(1/2) + 8(1/4) + 0(1/4) = 7\).
Dòng đầu tiên chứa \(N\) (\(2 \leq N \leq 10^5\)). \(N\) dòng còn lại lần lượt chứa \(f(1) \ldots f(N)\), mỗi dòng một giá trị.
In ra \(N\) dòng. Trên dòng \(i\), in ra \(10^5\) lần kỳ vọng số tiền Bessie nhận được nếu cô xuất phát tại vị trí \(i\) và chơi tối ưu, được làm tròn xuống số nguyên gần nhất.
Ví dụ 1
2
1
3150000
300000Đề bài gốc: USACO 2018 December Contest, Platinum — Balance Beam
Tác giả: Franklyn Wang and Spencer Compton
FJ có \(N\) cô bò (\(1 \leq N \leq 10^5\)), được định danh riêng biệt từ \(1 \ldots N\) và xếp thành một hàng. FJ thích các cô bò được sắp xếp theo thứ tự tăng dần, nhưng đáng tiếc là hiện tại chúng đang lộn xộn. Trước đây FJ từng dùng những thuật toán đột phá như "bubble sort" để sắp xếp các cô bò, nhưng hôm nay ông cảm thấy khá lười. Thay vào đó, mỗi lần ông sẽ quát một cô bò cụ thể rằng hãy "tự sắp xếp đi". Khi bị quát, một cô bò sẽ đảm bảo rằng mình không đứng sai thứ tự (theo góc nhìn của cô). Chừng nào cô bò ngay bên phải có ID nhỏ hơn, hai cô sẽ đổi chỗ cho nhau. Sau đó, chừng nào cô bò ngay bên trái có ID lớn hơn, hai cô sẽ đổi chỗ cho nhau. Cuối cùng, cô bò hoàn tất việc "tự sắp xếp"; lúc này cô bò bên trái cô có ID nhỏ hơn và cô bò bên phải cô có ID lớn hơn.
FJ muốn chọn một tập con các cô bò, rồi duyệt qua tập con này và lần lượt quát từng cô (theo thứ tự ID tăng dần), lặp đi lặp lại cho đến khi tất cả \(N\) cô bò được sắp xếp. Chẳng hạn, nếu chọn tập con gồm các cô bò có ID \(\{2, 4, 5\}\), ông sẽ quát cô bò \(2\), rồi cô bò \(4\), rồi cô bò \(5\). Nếu \(N\) cô bò vẫn chưa được sắp xếp, ông sẽ tiếp tục quát lại chính những cô bò này nhiều lần nữa nếu cần.
Vì FJ không chắc những cô bò nào đang chú ý, ông muốn tối thiểu hóa kích thước của tập con này. Ngoài ra, FJ cho rằng số \(K\) rất may mắn. Hãy giúp ông tìm tập con có kích thước nhỏ nhất đứng thứ \(K\) theo thứ tự từ điển sao cho việc quát các cô bò trong đó nhiều lần cuối cùng sẽ khiến tất cả các cô bò được sắp xếp.
Một tập con \(S\) của \(\{1,\dots,N\}\) được gọi là nhỏ hơn tập con \(T\) theo thứ tự từ điển nếu danh sách các phần tử của \(S\) (theo thứ tự tăng dần) nhỏ hơn danh sách các phần tử của \(T\) (theo thứ tự tăng dần) theo thứ tự từ điển. Chẳng hạn, \(\{1, 3, 6\}\) nhỏ hơn \(\{1, 4, 5\}\) theo thứ tự từ điển.
Dòng đầu tiên chứa một số nguyên duy nhất \(N\). Dòng thứ hai chứa một số nguyên duy nhất \(K\) (\(1 \leq K \leq 10^{18}\)). Dòng thứ ba chứa \(N\) số nguyên cách nhau bởi dấu cách, biểu diễn số hiệu của các cô bò từ trái sang phải.
Đảm bảo rằng có ít nhất \(K\) tập con hợp lệ.
Dòng đầu tiên chứa kích thước của tập con nhỏ nhất. Các dòng còn lại chứa ID của các cô bò trong tập con có kích thước nhỏ nhất đứng thứ \(K\) theo thứ tự từ điển, mỗi dòng một ID và được liệt kê theo thứ tự tăng dần.
Ví dụ 1
4 1
4 2 1 32
1
4Ban đầu ta có mảng \(\mathtt{\:4\:\; 2\:\; 1\:\; 3\:}\). Sau khi FJ quát cô bò có ID 1, mảng trở thành \(\mathtt{\:1\:\; 4\:\; 2\:\; 3\:}\). Khi FJ quát cô bò có ID 4, mảng trở thành \(\mathtt{\:1\:\; 2\:\; 3\:\; 4\:}\). Lúc này, mảng đã được sắp xếp.
Đề bài gốc: USACO 2018 December Contest, Platinum — Sort It Out
Tác giả: Spencer Compton
Những cô bò từ khắp nơi trên thế giới đã tập hợp về dự một cuộc tụ họp quy mô lớn. Có \(N\) cô bò và \(N-1\) cặp bò là bạn của nhau. Mỗi cô bò đều biết mọi cô bò khác thông qua một chuỗi quan hệ bạn bè nào đó.
Chúng đã có một khoảng thời gian tuyệt vời, nhưng giờ đã đến lúc lần lượt rời đi từng cô một. Chúng muốn rời đi theo một thứ tự sao cho chừng nào vẫn còn ít nhất hai cô bò, mỗi cô bò còn lại đều có ít nhất một người bạn vẫn còn ở đó. Ngoài ra, do những vấn đề về chỗ cất hành lý, có \(M\) cặp bò \((a_i, b_i)\) sao cho cô bò \(a_i\) phải rời đi trước cô bò \(b_i\). Lưu ý rằng cô bò \(a_i\) và cô bò \(b_i\) có thể là bạn hoặc không.
Hãy giúp các cô bò xác định, với mỗi cô bò, liệu cô có thể là cô bò cuối cùng rời đi hay không. Có thể không tồn tại cách nào để các cô bò rời đi mà thỏa mãn những ràng buộc trên.
Dòng \(1\) chứa hai số nguyên \(N\) và \(M\) cách nhau bởi dấu cách.
Mỗi dòng \(2 \leq i \leq N\) chứa hai số nguyên \(x_i\) và \(y_i\) với \(1 \leq x_i, y_i \leq N\) và \(x_i \neq y_i\), cho biết cô bò \(x_i\) và cô bò \(y_i\) là bạn.
Mỗi dòng \(N+1 \leq i \leq N+M\) chứa hai số nguyên \(a_i\) và \(b_i\) với \(1 \leq a_i, b_i \leq N\) và \(a_i \neq b_i\), cho biết cô bò \(a_i\) phải rời cuộc tụ họp trước cô bò \(b_i\).
Đảm bảo rằng \(1 \leq N, M \leq 10^5\).
Trong các trường hợp kiểm thử chiếm \(20\%\) số điểm, còn đảm bảo thêm rằng \(N, M \leq 3000\).
Dữ liệu ra gồm \(N\) dòng, mỗi dòng chứa một số nguyên \(d_i\) sao cho \(d_i = 1\) nếu cô bò \(i\) có thể là cô bò cuối cùng rời đi, và \(d_i = 0\) nếu không thể.
Ví dụ 1
5 1
1 2
2 3
3 4
4 5
2 40
0
1
1
1Đề bài gốc: USACO 2018 December Contest, Platinum — The Cow Gathering
Tác giả: Dhruv Rohatgi