| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2019 - Convention | 100 (p) | 4.0s | 512M |
| 2 | USACO 2019 - Convention II | 100 (p) | 4.0s | 512M |
| 3 | USACO 2019 - Mooyo Mooyo | 100 (p) | 4.0s | 512M |
Nông dân John đang tổ chức một hội nghị ăn cỏ mới dành cho bò tại trang trại của mình!
Những cô bò từ khắp nơi trên thế giới đang đến sân bay địa phương để tham dự hội nghị và ăn cỏ. Cụ thể, có \(N\) cô bò đến sân bay (\(1 \leq N \leq 10^5\)), trong đó cô bò \(i\) đến vào thời điểm \(t_i\) (\(0 \leq t_i \leq 10^9\)). Nông dân John đã bố trí \(M\) chiếc xe buýt (\(1 \leq M \leq 10^5\)) để đưa các cô bò rời sân bay. Mỗi xe buýt có thể chở tối đa \(C\) cô bò (\(1 \leq C \leq N\)). Nông dân John đang chờ cùng các xe buýt tại sân bay và muốn phân các cô bò đến sân bay lên các xe. Một xe buýt có thể khởi hành vào thời điểm cô bò cuối cùng trên xe đến. Nông dân John muốn làm một người chủ nhà chu đáo nên không muốn để những cô bò mới đến phải chờ quá lâu tại sân bay. Nếu Nông dân John điều phối các xe buýt một cách tối ưu, giá trị nhỏ nhất có thể của thời gian chờ lớn nhất trong số mọi cô bò là bao nhiêu? Thời gian chờ của một cô bò là độ chênh lệch giữa thời điểm cô đến và thời điểm chiếc xe được phân cho cô khởi hành.
Đảm bảo rằng \(MC \geq N\).
Dòng đầu tiên chứa ba số nguyên \(N\), \(M\) và \(C\) cách nhau bởi dấu cách. Dòng tiếp theo chứa \(N\) số nguyên cách nhau bởi dấu cách, biểu diễn thời điểm đến của mỗi cô bò.
In ra một dòng chứa giá trị nhỏ nhất có thể của thời gian chờ lớn nhất đối với bất kỳ cô bò nào.
Ví dụ 1
6 3 2
1 1 10 14 4 34Nếu hai cô bò đến vào thời điểm 1 đi trên một xe, các cô bò đến vào thời điểm 3 và 4 đi trên xe thứ hai, còn các cô bò đến vào thời điểm 10 và 14 đi trên xe thứ ba, thì thời gian chờ lâu nhất của một cô bò là 4 đơn vị thời gian (cô bò đến vào thời điểm 10 chờ từ thời điểm 10 đến thời điểm 14).
Đề bài gốc: USACO 2018 December Contest, Silver — Convention
Tác giả: Grace Cai
Bất chấp sự chậm trễ kéo dài trong việc đón bò tại sân bay, hội nghị dành cho những cô bò thích ăn cỏ của Nông dân John cho đến nay vẫn diễn ra tốt đẹp. Hội nghị đã thu hút bò từ khắp nơi trên thế giới.
Tuy nhiên, sự kiện chính của hội nghị có vẻ sẽ khiến Nông dân John gặp thêm khó khăn trong việc xếp lịch. Một đồng cỏ rất nhỏ trong trang trại của ông có một loại cỏ quý hiếm được những cô bò sành ăn cho là ngon nhất thế giới. Vì vậy, tất cả \(N\) cô bò tại hội nghị (\(1 \leq N \leq 10^5\)) đều muốn nếm thử loại cỏ này. Điều đó có thể tạo ra hàng chờ dài vì đồng cỏ nhỏ đến mức mỗi lúc chỉ có thể phục vụ một cô bò.
Nông dân John biết thời điểm \(a_i\) mà mỗi cô bò \(i\) dự định đến đồng cỏ đặc biệt, cũng như khoảng thời gian \(t_i\) cô dự định dùng để nếm loại cỏ đặc biệt khi đến lượt. Một khi cô bò \(i\) bắt đầu ăn cỏ, cô sẽ ăn trọn vẹn trong \(t_i\) đơn vị thời gian rồi mới rời đi; trong khoảng đó, những cô bò khác đến nơi phải chờ. Nếu có nhiều cô bò đang chờ khi đồng cỏ lại trống, cô bò có thâm niên cao nhất sẽ là cô tiếp theo được phép nếm cỏ. Theo quy tắc này, một cô bò đến đúng lúc một cô bò khác ăn xong được xem là đang "chờ". Tương tự, nếu nhiều cô bò cùng đến vào chính xác một thời điểm khi không có cô bò nào đang ăn, cô có thâm niên cao nhất sẽ được ăn tiếp theo.
Hãy giúp FJ tính thời gian dài nhất mà một cô bò có thể phải chờ trong hàng (từ thời điểm \(a_i\) đến thời điểm cô bắt đầu ăn).
Dòng đầu tiên chứa \(N\). Mỗi dòng trong \(N\) dòng tiếp theo cung cấp thông tin của \(N\) cô bò theo thứ tự thâm niên (cô bò có thâm niên cao nhất đứng đầu). Mỗi dòng chứa \(a_i\) và \(t_i\) của một cô bò. Các giá trị \(t_i\) là số nguyên dương không vượt quá \(10^4\), còn các giá trị \(a_i\) là số nguyên dương không vượt quá \(10^9\).
In ra thời gian chờ dài nhất trong số tất cả các cô bò.
Ví dụ 1
5
25 3
105 30
20 50
10 17
100 1010Trong ví dụ này, có 5 cô bò (được đánh số 1..5 theo thứ tự trong dữ liệu vào). Cô bò 4 đến đầu tiên (vào thời điểm 10), và trước khi cô ăn xong (vào thời điểm 27), cả cô bò 1 và cô bò 3 đều đến. Vì cô bò 1 có thâm niên cao hơn nên cô được ăn tiếp theo, sau khi đã chờ 2 đơn vị thời gian kể từ lúc đến. Cô ăn xong vào thời điểm 30, rồi cô bò 3 bắt đầu ăn sau khi đã chờ 10 đơn vị thời gian kể từ thời điểm đến. Sau một khoảng thời gian không có cô bò nào ăn, cô bò 5 đến; trong lúc cô đang ăn thì cô bò 2 đến và được ăn sau đó 5 đơn vị thời gian. Cô bò bị trì hoãn lâu nhất so với thời điểm đến là cô bò 3.
Đề bài gốc: USACO 2018 December Contest, Silver — Convention II
Tác giả: Brian Dean
Với rất nhiều thời gian rảnh trong tay (hay đúng hơn là trong móng), những cô bò ở trang trại của Nông dân John thường giết thời gian bằng cách chơi trò chơi điện tử. Một trong những trò yêu thích của chúng dựa trên trò chơi nổi tiếng của con người có tên Puyo Puyo; phiên bản dành cho bò tất nhiên được gọi là Mooyo Mooyo.
Mooyo Mooyo được chơi trên một lưới cao và hẹp gồm \(N\) ô theo chiều cao (\(1 \leq N \leq 100\)) và 10 ô theo chiều rộng. Dưới đây là một ví dụ với \(N = 6\):
0000000000
0000000300
0054000300
1054502230
2211122220
1111111223
Mỗi ô hoặc trống (được biểu diễn bằng 0), hoặc chứa một kiện cỏ khô thuộc một trong chín màu khác nhau (được biểu diễn bằng các ký tự 1..9). Trọng lực khiến các kiện cỏ khô rơi xuống, vì vậy không bao giờ có một ô 0 nằm bên dưới một kiện cỏ khô.
Hai ô thuộc cùng một vùng liên thông nếu chúng kề cạnh trực tiếp theo chiều ngang hoặc chiều dọc và có cùng một màu khác 0. Bất cứ khi nào tồn tại một vùng liên thông có ít nhất \(K\) ô, tất cả các kiện cỏ khô trong vùng đó biến mất và các ô của chúng trở thành 0. Nếu cùng lúc có nhiều vùng liên thông như vậy, tất cả chúng biến mất đồng thời. Sau đó, trọng lực có thể khiến các kiện cỏ khô rơi xuống để lấp một số ô vừa trở thành 0. Trong cấu hình mới, có thể lại xuất hiện các vùng liên thông có kích thước ít nhất \(K\). Nếu có, chúng cũng biến mất (đồng thời nếu có nhiều vùng như vậy), rồi trọng lực kéo các ô còn lại xuống, và quá trình lặp lại cho đến khi không còn vùng liên thông nào có kích thước ít nhất \(K\).
Cho trạng thái của một bàn Mooyo Mooyo, hãy in ra hình ảnh cuối cùng của bàn sau khi các thao tác trên hoàn tất.
Dòng đầu tiên chứa \(N\) và \(K\) (\(1 \leq K \leq 10N\)). \(N\) dòng còn lại mô tả trạng thái ban đầu của bàn.
In ra \(N\) dòng mô tả trạng thái cuối cùng của bàn.
Ví dụ 1
6 3
0000000000
0000000300
0054000300
1054502230
2211122220
11111112230000000000
0000000000
0000000000
0000000000
1054000000
2254500000Trong ví dụ trên, với \(K = 3\), có một vùng liên thông màu 1 có kích thước ít nhất \(K\) và cũng có một vùng như vậy màu 2. Sau khi hai vùng này bị xóa đồng thời, bàn tạm thời trông như sau:
0000000000
0000000300
0054000300
1054500030
2200000000
0000000003
Sau đó, trọng lực có hiệu lực và các kiện cỏ khô rơi xuống thành cấu hình sau:
0000000000
0000000000
0000000000
0000000000
1054000300
2254500333
Một lần nữa, có một vùng màu 3 có kích thước ít nhất \(K\). Xóa vùng này ta thu được cấu hình cuối cùng của bàn:
0000000000
0000000000
0000000000
0000000000
1054000000
2254500000
Đề bài gốc: USACO 2018 December Contest, Silver — Mooyo Mooyo
Tác giả: Brian Dean