| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2019 - Left Out | 100 (p) | 4.0s | 512M |
| 2 | USACO 2019 - Cow Steeplechase II | 100 (p) | 4.0s | 512M |
| 3 | USACO 2019 - Fence Planning | 100 (p) | 4.0s | 512M |
Farmer John đang cố chụp ảnh đàn bò của mình. Từ những kinh nghiệm trước đây, ông biết rằng công việc cụ thể này thường chẳng bao giờ kết thúc tốt đẹp.
Lần này, Farmer John đã mua một chiếc máy bay không người lái đắt tiền để chụp ảnh từ trên không. Để bức ảnh đẹp nhất có thể, ông muốn tất cả bò cùng quay về một hướng khi chụp. Hiện tại, các con bò được xếp thành một lưới \(N \times N\) (\(2 \leq N \leq 1000\)) bên trong một đồng cỏ vuông có hàng rào bao quanh, ví dụ:
RLR
RRL
LLR
Ở đây, R nghĩa là một con bò quay sang phải, còn L nghĩa là một con bò quay sang trái. Vì các con bò đứng sát nhau, Farmer John không thể đi tới từng con để bắt nó quay lại. Tất cả những gì ông có thể làm là hét vào một hàng hoặc một cột bò bất kỳ để chúng quay lại, khiến các ký tự L đổi thành R và R đổi thành L trong hàng hoặc cột đó. Farmer John có thể hét vào bao nhiêu hàng hoặc cột tùy ý, kể cả cùng một hàng hoặc cột nhiều lần.
Đúng như dự đoán, Farmer John nhận thấy ông không thể khiến tất cả bò cùng quay về một hướng. Điều tốt nhất ông có thể làm là khiến tất cả trừ một con bò cùng quay về một hướng. Hãy xác định con bò như vậy.
Dòng đầu tiên chứa \(N\). \(N\) dòng tiếp theo mô tả các hàng \(1 \ldots N\) trong lưới bò, mỗi dòng chứa một xâu có độ dài \(N\).
In ra chỉ số hàng và cột của một con bò sao cho nếu con bò đó được lật hướng, Farmer John có thể khiến tất cả bò cùng quay về một hướng. Nếu không tồn tại con bò nào như vậy, in ra -1. Nếu có nhiều con bò như vậy, in ra con có chỉ số hàng nhỏ nhất; nếu nhiều con có cùng chỉ số hàng nhỏ nhất, in ra con có chỉ số cột nhỏ nhất.
Ví dụ 1
3
RLR
RRL
LLR1 1Trong ví dụ trên, con bò ở hàng 1, cột 1 (góc trên bên trái) là con bò gây ra vấn đề, vì Farmer John có thể hét vào hàng 2 và cột 3 để khiến tất cả những con bò khác quay sang trái, chỉ riêng con bò này quay sang phải.
USACO 2019 US Open Contest, Silver — Left Out
Tác giả: Brian Dean.
Trước đây, Farmer John từng cân nhắc một số ý tưởng sáng tạo cho những môn thể thao mới dành cho bò, trong đó có môn vượt chướng ngại vật dành cho bò, nơi các đàn bò đua quanh một đường chạy và nhảy qua các rào cản. Những nỗ lực trước đây của ông nhằm thu hút sự quan tâm tới môn thể thao này đã cho kết quả không đồng nhất, nên ông hy vọng xây dựng một đường đua vượt chướng ngại vật dành cho bò còn lớn hơn trên trang trại để quảng bá thêm cho môn thể thao này.
Đường đua mới của Farmer John được lên kế hoạch cẩn thận quanh \(N\) rào cản, được đánh số thuận tiện từ \(1 \ldots N\) (\(2 \leq N \leq 10^5\)), mỗi rào cản được mô tả là một đoạn thẳng trên bản đồ 2D của đường đua. Các đoạn thẳng này không được giao nhau dưới bất kỳ hình thức nào, kể cả tại các đầu mút.
Thật không may, Farmer John đã không chú ý khi vẽ bản đồ đường đua và nhận ra rằng có các đoạn thẳng giao nhau. Tuy nhiên, ông cũng nhận thấy rằng chỉ cần bỏ đi đúng một đoạn thẳng, bản đồ sẽ trở lại trạng thái dự định là không có đoạn thẳng nào giao nhau (kể cả tại đầu mút).
Hãy xác định một đoạn thẳng mà Farmer John có thể xóa khỏi kế hoạch để khôi phục tính chất không có đoạn thẳng nào giao nhau. Nếu có thể xóa nhiều đoạn thẳng theo cách này, hãy in ra chỉ số của đoạn xuất hiện sớm nhất trong dữ liệu vào.
Dòng đầu tiên chứa \(N\). Mỗi dòng trong \(N\) dòng còn lại mô tả một đoạn thẳng bằng bốn số nguyên \(x_1\) \(y_1\) \(x_2\) \(y_2\), tất cả đều là số nguyên không âm không vượt quá \(10^9\). Đoạn thẳng có hai đầu mút là \((x_1, y_1)\) và \((x_2, y_2)\). Tất cả các đầu mút đều phân biệt với nhau.
In ra chỉ số nhỏ nhất trong dữ liệu vào của một đoạn thẳng sao cho việc xóa đoạn đó khiến các đoạn thẳng còn lại không giao nhau.
Ví dụ 1
4
2 1 6 1
4 0 1 5
5 6 5 5
2 7 1 32Lưu ý: Bạn nên cẩn thận với tràn số nguyên trong bài này do độ lớn của các số được dùng làm tọa độ đầu mút đoạn thẳng.
USACO 2019 US Open Contest, Silver — Cow Steeplechase II
Tác giả: Brian Dean.
\(N\) con bò của Farmer John, được đánh số thuận tiện từ \(1 \ldots N\) (\(2 \leq N \leq 10^5\)), có một cấu trúc xã hội phức tạp xoay quanh các "mạng lưới tiếng rống" — những nhóm bò nhỏ hơn giao tiếp trong nội bộ nhóm nhưng không giao tiếp với các nhóm khác.
Mỗi con bò ở một vị trí \((x,y)\) riêng biệt trên bản đồ 2D của trang trại, và ta biết có \(M\) cặp bò (\(1 \leq M < 10^5\)) rống với nhau. Hai con bò rống với nhau thuộc cùng một mạng lưới tiếng rống.
Trong nỗ lực nâng cấp trang trại, Farmer John muốn dựng một hàng rào hình chữ nhật có các cạnh song song với trục \(x\) và \(y\). Farmer John muốn đảm bảo rằng ít nhất một mạng lưới tiếng rống được hàng rào bao kín hoàn toàn (những con bò nằm trên biên hình chữ nhật cũng được tính là ở bên trong). Hãy giúp Farmer John xác định chu vi nhỏ nhất có thể của một hàng rào thỏa mãn yêu cầu này. Hàng rào có thể có chiều rộng bằng không hoặc chiều cao bằng không.
Dòng đầu tiên chứa \(N\) và \(M\). Mỗi dòng trong \(N\) dòng tiếp theo chứa tọa độ \(x\) và \(y\) của một con bò (các số nguyên không âm không vượt quá \(10^8\)). Mỗi dòng trong \(M\) dòng tiếp theo chứa hai số nguyên \(a\) và \(b\), mô tả một liên kết rống giữa bò \(a\) và bò \(b\). Mỗi con bò có ít nhất một liên kết rống, và không có liên kết nào được lặp lại trong dữ liệu vào.
In ra chu vi nhỏ nhất của một hàng rào thỏa mãn các yêu cầu của Farmer John.
Ví dụ 1
7 5
0 5
10 5
5 0
5 10
6 7
8 6
8 4
1 2
2 3
3 4
5 6
7 610USACO 2019 US Open Contest, Silver — Fence Planning
Tác giả: Brian Dean.