| # | 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? Có lẽ chúng ta sẽ không bao giờ biết được đầy đủ nguyên nhân, nhưng chắc chắn đàn bò của Farmer John băng qua đường khá thường xuyên. Thực tế, chúng sang đường nhiều đến mức thường va vào nhau khi đường đi giao nhau, và Farmer John muốn khắc phục tình trạng này.
Farmer John nuôi \(N\) giống bò (\(1 \leq N \leq 100,000\)), và mỗi cánh đồng của ông được dành riêng cho một giống cụ thể; chẳng hạn, một cánh đồng dành cho giống 12 chỉ có thể được bò giống 12 sử dụng, không phải bất kỳ giống nào khác. Một con đường dài chạy qua trang trại của ông. Có một dãy \(N\) cánh đồng ở một phía của con đường (mỗi giố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). Vì vậy, khi một con bò băng qua đường, nó đi giữa hai cánh đồng dành riêng cho giống của mình.
Nếu Farmer John lên kế hoạch cẩn thận hơn, ông đã sắp xếp các cánh đồng theo cùng một thứ tự giống ở hai phía con đường, để hai cánh đồng của mỗi giống nằm đối diện trực tiếp với nhau. Khi đó, bò có thể băng qua đường mà không va vào bò thuộc giống khác. Đáng tiếc là thứ tự ở hai phía có thể khác nhau, nên Farmer John nhận thấy có thể tồn tại những cặp giống giao nhau. Một cặp hai giống khác nhau \((a,b)\) được gọi là "giao nhau" nếu mọi đường đi băng qua đường dành cho giống \(a\) đều bắt buộc phải cắt mọi đường đi băng qua đường dành cho giống \(b\).
Farmer John muốn giảm thiểu số cặp giống giao nhau. Vì lý do hậu cần, ông có thể di chuyển bò ở một phía con đường để các cánh đồng ở phía đó trải qua một phép "dịch vòng". Cụ thể, với một giá trị \(0 \leq k < N\) nào đó, mỗi con bò chuyển đến cánh đồng cách vị trí của nó \(k\) cánh đồng về phía trước, còn những con bò ở \(k\) cánh đồng cuối chuyển đến chiếm \(k\) cánh đồng đầu tiên. Chẳng hạn, nếu ban đầu các cánh đồng ở một phía con đường có thứ tự giống là 3, 7, 1, 2, 5, 4, 6 và được dịch vòng với \(k=2\), thứ tự mới sẽ là 4, 6, 3, 7, 1, 2, 5. Hãy xác định số cặp giống giao nhau nhỏ nhất có thể sau khi thực hiện một phép dịch vòng thích hợp đối với các cánh đồng ở một phía con đường.
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.
In ra số cặp giống giao nhau nhỏ nhất sau khi dịch vòng các cánh đồng ở một phía con đường (có thể dịch một trong hai phía).
Ví dụ 1
5
5
4
1
3
2
1
3
2
5
40USACO 2017 February Contest, Platinum — Why Did the Cow Cross the Road. Tác giả đề: Brian Dean.
Farmer John tiếp tục suy ngẫm về vấn đề bò băng qua con đường chạy qua trang trại của mình, đã được giới thiệu trong bài trước. Ông nhận ra rằng sự tương tác giữa một số cặp giống thực ra có thể chấp nhận được nếu chúng thân thiện với nhau, 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. 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.
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 (mỗi phía vẫn có đúng một cánh đồng cho mỗi giống), 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 và mỗi vạch nối một cặp cánh đồng dành cho 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).
Dòng đầu tiên chứa \(N\) (\(1 \leq N \leq 100,000\)). \(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, Platinum — Why Did the Cow Cross the Road II. Tác giả đề: Brian Dean.
Farmer John tiếp tục suy ngẫm về vấn đề bò băng qua con đường chạy qua trang trại của mình, đã được giới thiệu trong hai bài trước. Giờ đây ông nhận ra rằng ngưỡng xác định sự thân thiện tinh tế hơn đôi chút so với suy nghĩ trước đây: hai giống \(a\) và \(b\) thân thiện nếu \(|a-b| \leq K\), ngược lại thì không thân thiện.
Cho trước thứ tự các cánh đồng ở hai phía con đường chạy qua trang trại của FJ, hãy đếm số cặp giống không thân thiện và giao nhau, trong đó một cặp giống giao nhau được định nghĩa như trong các bài trước.
Dòng đầu tiên chứa \(N\) (\(1 \leq N \leq 100,000\)) và \(K\) (\(0 \leq K < 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ố cặp giống không thân thiện và giao nhau.
Ví dụ 1
4 1
4
3
2
1
1
4
2
32Trong ví dụ này, giống 1 và giống 4 không thân thiện và giao nhau; giống 1 và giống 3 cũng vậy.
USACO 2017 February Contest, Platinum — Why Did the Cow Cross the Road III. Tác giả đề: Brian Dean.