trang chủ / đề bài / icpcwf12_i

Đặt cược an toàn

Đề bài

Mô tả

Công ty Safe Ltd. sản xuất két sắt chất lượng cao. Phát minh mới nhất của công ty là một cơ chế khóa quang học: một tia laser đi qua một lưới hình chữ nhật có đặt một số tấm gương.

Hình trái: tia được phát hiện, két mở. Hình phải: tia không được phát hiện, chuông báo động kêu.

Khi bật laser, tia sáng đi vào hàng trên cùng của lưới theo phương ngang từ bên trái. Tia bị phản xạ bởi mọi tấm gương mà nó gặp. Mỗi tấm gương đặt chéo 45 độ, theo một trong hai hướng / hoặc \. Nếu tia ra khỏi hàng dưới cùng của lưới theo phương ngang về bên phải thì tia được phát hiện và két mở (xem hình bên trái). Ngược lại két vẫn đóng và chuông báo động kêu.

Mỗi két sắt bị thiếu một tấm gương, khiến tia laser không đi qua lưới thành công được (xem hình bên phải). Két có một cơ chế cho phép người dùng thả đúng một tấm gương vào một ô trống bất kỳ của lưới. Người dùng hợp lệ biết vị trí và hướng đúng của tấm gương còn thiếu (ở hình trên là gương / tại hàng 4, cột 3) nên mở được két. Không biết điều này thì người dùng phải đoán đúng, việc này có thể rất khó với các két có lưới lớn.

Nhiệm vụ của bạn là xác định một số két sắt có thực sự an toàn hay không. Một két an toàn là két không tự mở khi chưa thả gương, và có ít nhất một vị trí cùng hướng hợp lệ cho tấm gương còn thiếu. Thực tế có thể có nhiều vị trí và hướng như vậy.

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ test, đọc tới hết file. Mỗi bộ test mô tả một két sắt, bắt đầu bằng một dòng gồm bốn số nguyên r, c, m và n (1≤r,c≤1000000 và 0≤m,n≤200000). Lưới của cơ chế khóa có r hàng và c cột. Hàng được đánh số từ 1 tới r từ trên xuống, cột được đánh số từ 1 tới c từ trái sang.

Mỗi dòng trong m dòng tiếp theo gồm hai số nguyên ri và ci (1≤ri≤r và 1≤ci≤c), cho biết có một gương / ở hàng ri, cột ci. n dòng tiếp theo cho vị trí các gương \ theo cùng cách. m+n vị trí gương đôi một khác nhau.

Dữ liệu ra

Với mỗi bộ test, in ra số thứ tự của bộ test theo định dạng trong ví dụ, tiếp theo là:

  • 0 nếu két mở mà không cần thả gương.
  • k r c nếu két không mở khi chưa thả gương, có đúng k vị trí mà thả một gương vào đó thì két mở, và (r,c) là vị trí (hàng, cột) nhỏ nhất theo thứ tự từ điển trong các vị trí đó. Một vị trí mà cả gương / lẫn gương \ đều mở được két chỉ được tính một lần.
  • impossible nếu không thể mở két, dù có thả gương hay không.

Ràng buộc

  • 1≤r,c≤1000000.
  • 0≤m,n≤200000.
  • 1≤ri≤r, 1≤ci≤c; các vị trí gương đôi một khác nhau.

Ví dụ

Input Output Giải thích
5 6 1 4
2 3
1 2
2 5
4 2
5 5
100 100 0 2
1 77
100 77
100 100 0 0
Case 1: 2 4 3
Case 2: 0
Case 3: impossible
Bộ 1 là két ở hình phải: tia đi xuống ở cột 2 rồi ra khỏi lưới ở bên phải hàng 4. Thả gương / vào ô (4,3) (hình trái) hoặc gương \ vào ô (4,5) (tia rẽ xuống, gặp gương ở ô (5,5) rồi ra bên phải hàng 5) đều mở được két, nhỏ nhất là (4,3). Bộ 2: tia gặp gương \ ở ô (1,77), đi xuống tới gương \ ở ô (100,77) rồi ra bên phải hàng 100, két tự mở. Bộ 3: không có gương, tia đi thẳng ra bên phải hàng 1; thả một gương thì tia rẽ đúng một lần (lên hoặc xuống) rồi ra khỏi lưới ở mép trên hoặc mép dưới, không thể ra bên phải hàng 100.
3 5 0 3
1 3
3 2
2 4
Case 1: 2 1 2 Ba gương đều là \. Chưa thả gương thì tia gặp gương ở ô (1,3), đi xuống cột 3 rồi ra khỏi đáy lưới. Thả gương \ vào ô (1,2) thì tia đi xuống cột 2, gặp gương ở ô (3,2) và ra bên phải hàng 3. Thả gương \ vào ô (3,3) cũng làm tia rẽ sang phải ở hàng 3. Có 2 vị trí, nhỏ nhất là (1,2).

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0