| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2017 - Lots of Triangles | 100 (p) | 4.0s | 512M |
| 2 | USACO 2017 - Team Building | 100 (p) | 4.0s | 512M |
| 3 | USACO 2017 - Robotic Cow Herd | 100 (p) | 4.0s | 512M |
Farmer John đang nghĩ đến việc bán một phần đất để kiếm thêm thu nhập. Khu đất của ông có \(N\) cây (\(3 \leq N \leq 300\)), mỗi cây được biểu diễn bởi một điểm trên mặt phẳng hai chiều và không có ba cây nào thẳng hàng. Farmer John đang cân nhắc bán những lô đất hình tam giác có ba đỉnh là các cây; dĩ nhiên, dựa trên mọi bộ ba cây có thể chọn trong khu đất, có \(L=\binom{N}{3}\) lô như vậy để ông cân nhắc.
Một lô đất hình tam giác có giá trị \(v\) nếu nó chứa đúng \(v\) cây trong phần bên trong (không tính các cây ở ba đỉnh, và lưu ý rằng không có cây nào nằm trên biên vì không có ba cây nào thẳng hàng). Với mỗi \(v=0 \ldots N-3\), hãy giúp Farmer John xác định có bao nhiêu trong số \(L\) lô đất tiềm năng có giá trị \(v\).
Dòng đầu tiên chứa \(N\).
\(N\) dòng tiếp theo, mỗi dòng chứa tọa độ \(x\), \(y\) của một cây; cả hai tọa độ đều là số nguyên trong khoảng \(0 \ldots 1\,000\,000\).
In \(N-2\) dòng, trong đó dòng thứ \(i\) chứa số lô đất có giá trị \(i-1\).
Ví dụ 1
7
3 6
17 15
13 15
6 12
9 1
2 7
10 1928
6
1
0
0USACO 2016 December Contest, Platinum — Lots of Triangles. Tác giả đề: Lewin Gan.
Mỗi năm, Farmer John đưa \(N\) con bò của mình tới tranh tài cho danh hiệu "xuất sắc nhất cuộc thi" tại hội chợ tiểu bang. Đối thủ truyền kiếp của ông, Farmer Paul, cũng đưa \(M\) con bò của mình tới tranh tài (\(1 \leq N \leq 1000\), \(1 \leq M \leq 1000\)).
Mỗi con trong số \(N+M\) con bò tại sự kiện được chấm một điểm số nguyên. Tuy nhiên, cuộc thi chung kết năm nay sẽ được quyết định dựa trên các đội gồm \(K\) con bò (\(1 \leq K \leq 10\)) như sau: Farmer John và Farmer Paul mỗi người chọn một đội gồm \(K\) con bò của mình để tranh tài. Các con bò của hai đội sau đó được ghép cặp: con bò có điểm cao nhất trong đội của Farmer John được ghép với con có điểm cao nhất trong đội của Farmer Paul, con có điểm cao thứ hai trong đội của Farmer John được ghép với con có điểm cao thứ hai trong đội của Farmer Paul, và cứ tiếp tục như vậy. Farmer John thắng nếu trong mọi cặp, bò của ông có điểm cao hơn.
Hãy giúp Farmer John đếm số cách khác nhau mà ông và Farmer Paul có thể chọn đội sao cho Farmer John thắng cuộc thi. Nói cách khác, mỗi cặp phân biệt (một tập \(K\) con bò của Farmer John, một tập \(K\) con bò của Farmer Paul) mà Farmer John thắng đều phải được tính. In đáp án theo modulo \(1\,000\,000\,009\).
Dòng đầu tiên chứa \(N\), \(M\) và \(K\). Giá trị \(K\) không lớn hơn \(N\) hoặc \(M\).
Dòng tiếp theo chứa điểm số của \(N\) con bò của Farmer John.
Dòng cuối cùng chứa điểm số của \(M\) con bò của Farmer Paul.
In số cách Farmer John và Farmer Paul có thể chọn đội sao cho Farmer John thắng, theo modulo \(1\,000\,000\,009\).
Ví dụ 1
10 10 3
1 2 2 6 6 7 8 9 14 17
1 3 8 10 10 16 16 18 19 19382USACO 2016 December Contest, Platinum — Team Building. Tác giả đề: Brian Dean và William Luo.
Bessie hy vọng đánh lừa Farmer John bằng cách chế tạo một đàn gồm \(K\) con bò robot trông như thật (\(1 \leq K \leq 100\,000\)).
Hóa ra việc chế tạo một con bò robot khá phức tạp. Trên robot có \(N\) vị trí riêng biệt (\(1 \leq N \leq 100\,000\)) cần được kết nối với vi điều khiển (tức là phải kết nối đúng một vi điều khiển tại mỗi vị trí). Với mỗi vị trí này, Bessie có thể chọn một trong nhiều mẫu vi điều khiển khác nhau, mỗi mẫu có chi phí tương ứng.
Để đàn bò robot trông thuyết phục với Farmer John, không có hai robot nào được hành xử giống hệt nhau. Vì vậy, không có hai robot nào được có chính xác cùng một bộ vi điều khiển. Với bất kỳ cặp robot nào, phải có ít nhất một vị trí mà hai robot sử dụng hai mẫu vi điều khiển khác nhau. Đảm bảo rằng luôn có đủ các mẫu vi điều khiển khác nhau để thỏa mãn ràng buộc này.
Bessie muốn chế tạo đàn bò robot với chi phí thấp nhất có thể. Hãy giúp cô xác định chi phí nhỏ nhất để làm được điều đó!
Dòng đầu tiên chứa \(N\) và \(K\), cách nhau bởi một dấu cách.
\(N\) dòng tiếp theo mô tả các mẫu vi điều khiển khác nhau có sẵn cho từng vị trí. Dòng thứ \(i\) trong số này bắt đầu bằng \(M_i\) (\(1 \leq M_i \leq 10\)), là số mẫu có sẵn cho vị trí \(i\). Tiếp theo là \(M_i\) số nguyên cách nhau bởi dấu cách \(P_{i,j}\), biểu thị chi phí của các mẫu này (\(1 \leq P_{i,j} \leq 100\,000\,000\)).
In một dòng chứa chi phí nhỏ nhất để chế tạo \(K\) robot.
Ví dụ 1
3 10
4 1 5 3 10
3 2 3 3
5 1 3 4 6 661USACO 2016 December Contest, Platinum — Robotic Cow Herd. Tác giả đề: Richard Peng và Nathan Pinsker.