| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2014 - The Lazy Cow | 100 (p) | 4.0s | 512M |
| 2 | USACO 2014 - Sabotage | 100 (p) | 4.0s | 512M |
| 3 | USACO 2014 - Counting Friends | 100 (p) | 4.0s | 512M |
Đó là một ngày hè nóng nực và cô bò Bessie cảm thấy khá lười biếng. Cô muốn chọn một vị trí trong cánh đồng để có thể tiếp cận nhiều cỏ ngon nhất có thể mà chỉ phải đi một quãng ngắn.
Cánh đồng của Bessie có \(N\) cụm cỏ (\(1 \le N \le 100\,000\)). Cụm cỏ thứ \(i\) chứa \(g_i\) đơn vị cỏ (\(1 \le g_i \le 10\,000\)) và nằm tại một điểm \((x_i,y_i)\) riêng biệt trên cánh đồng (\(0 \le x_i,y_i \le 1\,000\,000\)). Bessie muốn chọn một điểm trên cánh đồng làm vị trí ban đầu (điểm này có thể trùng với một cụm cỏ, thậm chí có thể có tọa độ không nguyên) sao cho lượng cỏ nằm cách vị trí đó không quá \(K\) bước là lớn nhất (\(1 \le K \le 2\,000\,000\)).
Khi Bessie đi một bước, cô di chuyển \(1\) đơn vị về phía bắc, nam, đông hoặc tây so với vị trí hiện tại. Ví dụ, để đi từ \((0,0)\) đến \((3,2)\) cần tổng cộng \(5\) bước. Bessie không nhất thiết phải đi những bước có độ dài nguyên; chẳng hạn, tổng cộng \(1\) bước có thể được chia thành nửa đơn vị về phía bắc và nửa đơn vị về phía đông.
Hãy giúp Bessie xác định lượng cỏ lớn nhất mà cô có thể tiếp cận nếu chọn vị trí ban đầu tối ưu.
In ra lượng cỏ lớn nhất Bessie có thể tiếp cận trong phạm vi \(K\) bước nếu chọn vị trí ban đầu tối ưu.
Ví dụ 1
4 3
7 8 6
3 0 0
4 6 0
1 4 28Bessie sẵn lòng đi nhiều nhất \(3\) bước từ vị trí ban đầu. Có \(4\) cụm cỏ. Cụm đầu tiên chứa \(7\) đơn vị cỏ và nằm tại vị trí \((8,6)\), và các cụm còn lại được mô tả tương tự.
Nếu đứng tại \((3,0)\), Bessie có thể tiếp cận toàn bộ cỏ ở các vị trí \((0,0)\), \((6,0)\) và \((4,2)\) trong phạm vi \(K\) đơn vị khoảng cách.
USACO 2014 March Contest, Gold — The Lazy Cow
Tác giả: Brian Dean, 2014.
Kẻ thù không đội trời chung của Farmer John, Farmer Paul, đã quyết định phá hoại thiết bị vắt sữa của Farmer John!
Thiết bị vắt sữa gồm một hàng \(N\) máy vắt sữa (\(3 \le N \le 100\,000\)), trong đó máy thứ \(i\) sản xuất \(M_i\) đơn vị sữa (\(1 \le M_i \le 10\,000\)). Farmer Paul dự định ngắt kết nối một đoạn máy liên tiếp, từ máy thứ \(i\) đến máy thứ \(j\) (\(2 \le i \le j \le N-1\)). Lưu ý rằng Farmer Paul không muốn ngắt kết nối máy đầu tiên hoặc máy cuối cùng vì như vậy âm mưu của ông sẽ quá dễ bị phát hiện. Mục tiêu của Farmer Paul là giảm thiểu sản lượng sữa trung bình của những máy còn lại. Farmer Paul dự định loại bỏ ít nhất \(1\) con bò, ngay cả khi không phá hoại gì cả sẽ có lợi hơn cho ông.
May mắn thay, Farmer John đã biết được âm mưu xấu xa của Farmer Paul và đang tự hỏi sản lượng sữa sẽ bị ảnh hưởng nghiêm trọng đến mức nào nếu âm mưu thành công. Hãy giúp Farmer John tìm sản lượng sữa trung bình nhỏ nhất của những máy còn lại nếu Farmer Paul thành công.
In ra giá trị trung bình nhỏ nhất Farmer Paul có thể đạt được, được làm tròn đến \(3\) chữ số sau dấu thập phân và phải luôn hiển thị đủ \(3\) chữ số sau dấu thập phân.
Ví dụ 1
5
5
1
7
8
22.667Phương án tối ưu là loại bỏ \(7\) và \(8\), để lại \(5\), \(1\) và \(2\), có giá trị trung bình bằng \(8/3\).
USACO 2014 March Contest, Gold — Sabotage
Tác giả: Brian Dean, 2014.
\(N\) cô bò của Farmer John (\(2 \le N \le 500\)) đã tham gia mạng xã hội "MooBook".
Mỗi cô bò có một hoặc nhiều người bạn để tương tác trên MooBook. Để giải trí, Farmer John lập danh sách số lượng bạn bè của từng cô bò. Tuy nhiên, trong lúc ghi danh sách ông bị xao nhãng và vô tình ghi thừa một số, vì vậy danh sách có \(N+1\) số thay vì \(N\) số như dự định.
Hãy giúp Farmer John xác định những số nào trong danh sách có thể là số thừa bị ghi nhầm.
Ví dụ 1
4
1
2
2
1
33
1
4
5Farmer John có \(4\) cô bò. Hai cô chỉ có \(1\) người bạn mỗi cô, hai cô có \(2\) người bạn mỗi cô và một cô có \(3\) người bạn; tất nhiên, một trong các số này là số thừa không thuộc danh sách.
Xóa số đầu tiên trong danh sách của FJ (số \(1\)) sẽ để lại danh sách \(2,2,1,3\), và danh sách này thật sự cho phép một cách kết bạn khả thi. Chẳng hạn, nếu đặt tên các cô bò là \(A\) đến \(D\), các cặp \((A,B)\), \((A,C)\), \((A,D)\) và \((B,C)\) là đủ: \(A\) có \(3\) người bạn, \(B\) và \(C\) có \(2\) người bạn, còn \(D\) có \(1\) người bạn. Tương tự, xóa số \(1\) còn lại trong danh sách của FJ cũng được, và xóa số \(3\) cũng được. Xóa một trong hai số \(2\) đều không được; có thể thấy điều này vì tổng các số còn lại là số lẻ, rõ ràng khiến việc tìm một cách kết bạn khả thi trở nên bất khả thi.
USACO 2014 March Contest, Gold — Counting Friends
Tác giả: Brian Dean, 2014.