USACO 2025 - Astral Superposition
Xem PDFLưu ý: Giới hạn thời gian của bài này là 4 giây, gấp đôi giới hạn mặc định.
Bessie đang dùng chiếc kính thiên văn tiện lợi của mình để chụp ảnh tất cả các ngôi sao trên bầu trời đêm. Kính thiên văn của cô có thể chụp một bức ảnh kích thước \(N \times N\) (\(1 \leq N \leq 1000\)), trong đó mỗi điểm ảnh hoặc là một ngôi sao, hoặc là bầu trời trống. Mỗi ngôi sao được biểu diễn bởi đúng một điểm ảnh, và không có hai ngôi sao khác nhau nào nằm trên cùng một điểm ảnh.
Qua một đêm, có chuyện kỳ lạ xảy ra với những ngôi sao trên trời. Mỗi ngôi sao hoặc biến mất, hoặc dịch sang phải \(A\) điểm ảnh và xuống dưới \(B\) điểm ảnh (\(0 \leq A,B \leq N\)). Nếu một ngôi sao biến mất hoặc dịch ra ngoài biên ảnh, nó sẽ không còn xuất hiện trong bức ảnh thứ hai.
Bessie đã chụp ảnh trước và sau khi các vị trí bị dịch chuyển, nhưng sau khi thử nghiệm trong Mootoshop, cô vô tình chồng một bức ảnh lên bức còn lại. Giờ đây, cô thấy các điểm ảnh màu trắng tại những nơi cả hai bức ảnh đều trống, các điểm ảnh màu xám tại những nơi có sao trong đúng một bức ảnh, và các điểm ảnh màu đen tại những nơi có sao trong cả hai bức ảnh. Bessie cũng nhớ rằng không có ngôi sao mới nào di chuyển vào khung của bức ảnh thứ hai, nên bức ảnh đầu tiên của cô chứa tất cả các ngôi sao trên bầu trời đêm.
Cho bức ảnh cuối cùng, hãy xác định số ngôi sao ít nhất có thể có trên bầu trời trước sự cố dịch chuyển đối với \(T\) (\(1 \leq T \leq 1000\)) bộ test độc lập. Nếu không có cách sắp xếp các ngôi sao nào có thể tạo ra bức ảnh cuối cùng đã cho, hãy in \(-1\).
Dữ liệu vào
Dòng đầu tiên chứa \(T\), sau đó là \(T\) bộ test.
Dòng đầu tiên của mỗi bộ test chứa \(N\) \(A\) \(B\).
Tiếp theo là \(N\) dòng, mỗi dòng biểu diễn một hàng của bức ảnh chồng. Hàng thứ \(i\) tính từ trên xuống được biểu diễn bởi chuỗi \(c_{i,1}c_{i,2}\dots c_{i,N}\), trong đó mỗi \(c_{i,j} \in \{W,G,B\}\) lần lượt biểu diễn các màu trắng, xám và đen.
Đảm bảo tổng \(N^2\) trên tất cả các bộ test không vượt quá \(10^7\).
Dữ liệu ra
Với mỗi bộ test, in số ngôi sao ít nhất đã tồn tại trước khi dịch chuyển, hoặc \(-1\) nếu không thể.
Ví dụ
Ví dụ 1
Input
1
3 0 0
WWB
BBB
GGGOutput
7Giải thích
Trong ví dụ này, không có sự dịch chuyển. Bức ảnh đầu tiên như sau (. là bầu trời, * là ngôi sao):
..*
***
***
Bức ảnh thứ hai, trong đó các ngôi sao ở hàng dưới cùng đã biến mất, như sau:
..*
***
...
Đây là cách duy nhất để tạo ra bức ảnh chồng, nên số ngôi sao ban đầu ít nhất có thể là \(7\).
Ví dụ 2
Input
3
5 1 2
GWGWW
WGWWW
WBWGW
WWWWW
WWGWW
3 1 1
WWW
WBW
WWW
3 1 0
GGB
GGW
WWWOutput
4
-1
4Giải thích
Trong trường hợp thứ nhất, ban đầu có ít nhất \(4\) ngôi sao. Nếu gọi \((r,c)\) là giao điểm của hàng thứ \(r\) tính từ trên xuống và cột thứ \(c\) tính từ trái sang, một khả năng là ban đầu chúng ở \((1,1), (3,2), (2,2)\) và \((1,3)\). Tất cả các ngôi sao đều dịch chuyển, ngoại trừ ngôi sao tại \((2,2)\) đã biến mất.
Trong trường hợp thứ hai, không có cách sắp xếp các ngôi sao trong bức ảnh ban đầu nào có thể tạo ra điểm ảnh màu đen ở giữa với độ dịch chuyển đã cho.
Trong trường hợp thứ ba, ban đầu có ít nhất \(4\) ngôi sao. Một khả năng là ban đầu chúng ở \((1,1), (1,2), (1,3)\) và \((2,1)\). Trong bức ảnh thứ hai, ngôi sao ban đầu ở \((1,1)\) đã biến mất và ngôi sao ban đầu ở \((1,3)\) đã dịch ra ngoài khung. Hai ngôi sao còn lại dịch sang phải \(1\) điểm ảnh.
Phân nhóm
- Input 3: \(A=B=0\).
- Inputs 4-7: \(A=1, B=0, N\le 10\).
- Inputs 8-9: \(A=1, B=0\).
- Inputs 10-12: Không có ràng buộc bổ sung.
Nguồn
USACO 2025 January Contest, Bronze — Astral Superposition
Đề bài: https://usaco.org/index.php?page=viewproblem2&cpid=1467
Tác giả đề: Suhas Nagar
Kỳ thi:
- USACO 2025 - Tháng 1 - Hạng Đồng (1 Tháng 1., 2025)
Bình luận