| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2017 - Why Did the Cow Cross the Road | 100 (p) | 4.0s | 512M |
| 2 | USACO 2017 - Why Did the Cow Cross the Road II | 100 (p) | 4.0s | 512M |
| 3 | USACO 2017 - Why Did the Cow Cross the Road III | 100 (p) | 4.0s | 512M |
Đàn bò của Farmer John đang cố học cách băng qua đường hiệu quả. Nhớ đến câu đùa cũ "tại sao con gà băng qua đường?", chúng cho rằng gà hẳn là chuyên gia băng qua đường nên lên đường tìm gà giúp đỡ.
Hóa ra gà là những sinh vật rất bận rộn và chỉ có ít thời gian để giúp đàn bò. Có \(C\) con gà trong trang trại (\(1 \leq C \leq 20,000\)), được đánh số thuận tiện từ \(1 \ldots C\), và mỗi con gà \(i\) chỉ sẵn lòng giúp một con bò vào đúng thời điểm \(T_i\). Đàn bò không bao giờ vội nên có lịch trình linh hoạt hơn. Có \(N\) con bò trong trang trại (\(1 \leq N \leq 20,000\)), được đánh số thuận tiện từ \(1 \ldots N\), trong đó bò \(j\) có thể băng qua đường trong khoảng thời gian từ \(A_j\) đến \(B_j\). Cho rằng đi theo cặp là cách tốt nhất, mỗi bò \(j\) muốn tìm một gà \(i\) giúp mình băng qua đường; để lịch trình của chúng tương thích, \(i\) và \(j\) phải thỏa mãn \(A_j \leq T_i \leq B_j\).
Nếu mỗi con bò chỉ có thể được ghép với nhiều nhất một con gà và mỗi con gà chỉ có thể được ghép với nhiều nhất một con bò, hãy tính số cặp bò-gà lớn nhất có thể tạo thành.
Dòng đầu tiên chứa \(C\) và \(N\). \(C\) dòng tiếp theo chứa lần lượt \(T_1 \ldots T_C\), và \(N\) dòng tiếp theo chứa \(A_j\) và \(B_j\) (\(A_j \leq B_j\)) với \(j = 1 \ldots N\). Các giá trị \(A\), \(B\) và \(T\) đều là số nguyên không âm (không nhất thiết phân biệt) không quá 1.000.000.000.
In ra số cặp bò-gà lớn nhất có thể tạo thành.
Ví dụ 1
5 4
7
8
6
2
9
2 5
4 9
0 3
8 133USACO 2017 February Contest, Silver — Why Did the Cow Cross the Road. Tác giả đề: Brian Dean.
Con đường dài chạy qua trang trại của Farmer John có \(N\) vạch qua đường, được đánh số thuận tiện từ \(1 \ldots N\) (\(1 \leq N \leq 100,000\)). Để đàn bò có thể sang đường tại các vạch này, FJ lắp đặt đèn tín hiệu chạy bằng điện: đèn hiển thị biểu tượng con bò màu xanh khi bò được phép sang đường và màu đỏ trong trường hợp ngược lại. Không may, một cơn giông lớn đã làm hỏng một số đèn tín hiệu. Cho trước danh sách các đèn bị hỏng, hãy tính số đèn ít nhất FJ cần sửa để tồn tại một đoạn liên tiếp gồm ít nhất \(K\) đèn hoạt động.
Dòng đầu tiên chứa \(N\), \(K\) và \(B\) (\(1 \leq B, K \leq N\)). Mỗi dòng trong \(B\) dòng tiếp theo chứa mã số của một đèn tín hiệu bị hỏng.
In ra số đèn tín hiệu ít nhất cần sửa để có một đoạn gồm \(K\) đèn hoạt động liên tiếp ở đâu đó dọc theo con đường.
Ví dụ 1
10 6 5
2
10
1
5
91USACO 2017 February Contest, Silver — Why Did the Cow Cross the Road II. Tác giả đề: Brian Dean.
Tại sao con bò băng qua đường? Một lý do là trang trại của Farmer John có quá nhiều đường, khiến đàn bò của ông không thể đi lại mà không phải băng qua nhiều con đường.
Trang trại của FJ được bố trí thành một lưới ô vuông \(N \times N\) gồm các cánh đồng (\(2 \leq N \leq 100\)). Một số cặp cánh đồng kề nhau (theo hướng bắc-nam hoặc đông-tây) bị ngăn cách bởi đường, và một hàng rào cao chạy quanh toàn bộ chu vi bên ngoài của lưới, ngăn bò rời khỏi trang trại. Bò có thể tự do di chuyển từ bất kỳ cánh đồng nào sang một cánh đồng kề nó (về phía bắc, đông, nam hoặc tây), mặc dù chúng không muốn băng qua đường trừ khi thực sự cần thiết.
Có \(K\) con bò (\(1 \leq K \leq 100, K \leq N^2\)) trong trang trại của FJ, mỗi con ở một cánh đồng khác nhau. Một cặp bò được gọi là "xa cách" nếu một con bắt buộc phải băng qua ít nhất một con đường để đến thăm con còn lại. Hãy giúp FJ đếm số cặp bò xa cách.
Dòng đầu tiên chứa \(N\), \(K\) và \(R\). \(R\) dòng tiếp theo mô tả \(R\) con đường nằm giữa các cặp cánh đồng kề nhau. Mỗi dòng có dạng \(r\) \(c\) \(r'\) \(c'\) (các số nguyên trong khoảng \(1 \ldots N\)), biểu thị một con đường nằm giữa cánh đồng ở (hàng \(r\), cột \(c\)) và cánh đồng kề nó ở (hàng \(r'\), cột \(c'\)). \(K\) dòng cuối cùng cho biết vị trí của \(K\) con bò, mỗi vị trí được xác định bằng một hàng và một cột.
In ra số cặp bò xa cách.
Ví dụ 1
3 3 3
2 2 2 3
3 3 3 2
3 3 2 3
3 3
2 2
2 32USACO 2017 February Contest, Silver — Why Did the Cow Cross the Road III. Tác giả đề: Brian Dean.