| # | 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 |
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 (\(3 \leq N \leq 100\)), với \(N-1\) con đường theo hướng bắc-nam và \(N-1\) con đường theo hướng đông-tây chạy xuyên qua bên trong trang trại, đóng vai trò phân chia các cánh đồng. Một hàng rào cao chạy quanh chu vi bên ngoài, ngăn bò rời khỏi trang trại. Bò Bessie 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), miễn là nó cẩn thận nhìn cả hai phía trước khi băng qua con đường ngăn cách hai cánh đồng. Nó mất \(T\) đơn vị thời gian để băng qua một con đường (\(0 \leq T \leq 1,000,000\)).
Một ngày nọ, FJ mời Bessie đến nhà chơi một ván cờ thân mật. Bessie bắt đầu ở cánh đồng góc tây bắc, còn nhà của FJ nằm ở cánh đồng góc đông nam, nên nó phải đi bộ một quãng khá dài. Vì bị đói dọc đường, cứ đến cánh đồng thứ ba mà mình ghé qua, nó lại dừng lại để ăn cỏ (không tính cánh đồng xuất phát, nhưng có thể tính cánh đồng cuối cùng nơi nhà FJ tọa lạc). Một số cánh đồng có nhiều cỏ hơn những cánh đồng khác, vì vậy thời gian dừng lại ăn phụ thuộc vào cánh đồng nơi nó dừng chân.
Hãy giúp Bessie xác định thời gian ít nhất để đến nhà FJ.
Dòng đầu tiên chứa \(N\) và \(T\). Mỗi dòng trong \(N\) dòng tiếp theo chứa \(N\) số nguyên dương (mỗi số không quá 100.000), mô tả thời gian cần để ăn cỏ tại từng cánh đồng. Số đầu tiên của dòng đầu tiên ứng với góc tây bắc.
In ra thời gian ít nhất để Bessie đến nhà FJ.
Ví dụ 1
4 2
30 92 36 10
38 85 60 16
41 13 5 68
20 97 13 8031Lộ trình tối ưu trong ví dụ này đi 3 ô về phía đông (ăn cỏ tại ô có giá trị "10"), sau đó đi hai ô về phía nam và một ô về phía tây (ăn cỏ tại ô có giá trị "5"), cuối cùng đi về phía nam rồi về phía đông để tới đích.
USACO 2017 February Contest, Gold — Why Did the Cow Cross the Road. Tác giả đề: Brian Dean.
Farmer John nuôi \(N\) giống bò (\(1 \leq N \leq 1000\)), được đánh số thuận tiện từ \(1 \ldots N\). Một số cặp giống thân thiện với nhau hơn những cặp khác, và tính chất này có thể được mô tả dễ dàng theo mã số giống: hai giống \(a\) và \(b\) thân thiện nếu \(|a-b| \leq 4\), ngược lại thì không thân thiện.
Một con đường dài chạy qua trang trại của FJ. Có một dãy \(N\) cánh đồng ở một phía của con đường (mỗi giống được dành riêng một cánh đồng), và một dãy \(N\) cánh đồng ở phía bên kia (cũng mỗi giống một cánh đồng). Để giúp đàn bò băng qua đường an toàn, FJ muốn kẻ các vạch qua đường. Mỗi vạch qua đường phải nối một cánh đồng ở phía này với một cánh đồng ở phía kia sao cho mã số giống của hai cánh đồng là thân thiện (bò có thể đi vào cánh đồng dành cho giống khác, miễn là hai giống thân thiện). Mỗi cánh đồng chỉ có thể tiếp cận được qua nhiều nhất một vạch qua đường (do đó các vạch qua đường không gặp nhau tại đầu mút).
Cho trước thứ tự của \(N\) cánh đồng ở hai phía con đường chạy qua trang trại của FJ, hãy giúp FJ xác định số vạch qua đường lớn nhất có thể kẻ sao cho không có hai vạch nào giao nhau.
Dòng đầu tiên chứa \(N\). \(N\) dòng tiếp theo mô tả thứ tự các cánh đồng ở một phía của con đường theo mã số giống; mỗi mã số giống là một số nguyên trong khoảng \(1 \ldots N\). \(N\) dòng cuối cùng mô tả thứ tự các cánh đồng ở phía bên kia của con đường theo mã số giống. Mỗi mã số giống xuất hiện đúng một lần trong mỗi thứ tự.
In ra số "vạch qua đường thân thiện" đôi một không giao nhau lớn nhất mà Farmer John có thể kẻ qua con đường.
Ví dụ 1
6
1
2
3
4
5
6
6
5
4
3
2
15USACO 2017 February Contest, Gold — Why Did the Cow Cross the Road II. Tác giả đề: Brian Dean.
Bố cục trang trại của Farmer John khá kỳ lạ: một con đường lớn hình tròn chạy quanh rìa cánh đồng chính, nơi đàn bò của ông gặm cỏ vào ban ngày. Mỗi sáng, đàn bò băng qua con đường này để vào cánh đồng; mỗi tối, tất cả lại băng qua đường khi rời cánh đồng và trở về chuồng.
Như chúng ta đã biết, bò là loài sống theo thói quen và mỗi con đều băng qua đường theo cùng một cách mỗi ngày. Mỗi con bò đi vào cánh đồng tại một điểm khác với điểm nó đi ra, và tất cả các điểm băng qua đường đều phân biệt. Farmer John có \(N\) con bò, được đánh dấu thuận tiện bằng các mã số nguyên từ \(1 \ldots N\), nên có chính xác \(2N\) điểm băng qua đường quanh con đường. Farmer John ghi lại các điểm này một cách ngắn gọn bằng cách đi một vòng theo chiều kim đồng hồ, viết mã số của con bò tại mỗi điểm băng qua đường, cuối cùng tạo thành một dãy \(2N\) số trong đó mỗi số xuất hiện đúng hai lần. Ông không ghi lại đâu là điểm đi vào và đâu là điểm đi ra.
Nhìn vào sơ đồ các điểm băng qua đường, Farmer John tò mò muốn biết đường đi của các cặp bò khác nhau có thể cắt nhau bao nhiêu lần trong ngày. Ông gọi một cặp bò \((a,b)\) là một cặp "giao nhau" nếu đường đi từ điểm vào đến điểm ra của bò \(a\) bắt buộc phải cắt đường đi từ điểm vào đến điểm ra của bò \(b\). Hãy giúp Farmer John đếm tổng số cặp giao nhau.
Dòng đầu tiên chứa \(N\) (\(1 \leq N \leq 50,000\)), và \(2N\) dòng tiếp theo mô tả mã số bò trong dãy các điểm đi vào và đi ra quanh cánh đồng.
In ra tổng số cặp giao nhau.
Ví dụ 1
4
3
2
4
4
1
3
2
13USACO 2017 February Contest, Gold — Why Did the Cow Cross the Road III. Tác giả đề: Brian Dean.