trang chủ / đề bài / icpcwf21_a

Gió ngang tinh thể

Đề bài

Mô tả

Bạn là thành viên của một nhóm khoa học đang phát triển một kỹ thuật mới để chụp ảnh cấu trúc tinh thể ở cấp độ phân tử. Kỹ thuật này thổi một luồng gió rất nhẹ qua bề mặt tinh thể theo nhiều góc khác nhau để phát hiện các biên (thể hiện qua những phân tử bị gió thổi trúng). Việc này được lặp lại với nhiều hướng gió khác nhau, và các biên quan sát được với mỗi hướng được ghi lại. Nhóm của bạn đã thu thập xong dữ liệu, nhưng như thường thấy trong khoa học ứng dụng, giờ mới đến phần việc thực sự: phân tích.

Với một tinh thể cho trước, bạn nhận được các hướng gió đã thổi qua bề mặt và vị trí của mọi biên mà mỗi luồng gió gặp. Với luồng gió thổi theo hướng (wx,wy), một biên là một vị trí (x,y) sao cho có phân tử tại (x,y) và không có phân tử nào tại (x−wx,y−wy). Lưu ý rằng vì lý do kỹ thuật, wx và wy không nhất thiết nguyên tố cùng nhau.

Dữ liệu có thể không xác định duy nhất cấu trúc của tinh thể. Hãy tìm hai cấu trúc (luôn duy nhất) có số phân tử ít nhất và nhiều nhất phù hợp với các quan sát.

Chẳng hạn, trong ví dụ thứ nhất, có chín phân tử được các luồng gió gặp trực tiếp. Phải có một phân tử tại (3,3), vì nếu không thì (4,2) sẽ là một biên của luồng gió thứ ba. Vì lý do tương tự, phải có phân tử tại (4,4) và (5,5). Không thể có thêm phân tử nào khác, vì khi đó sẽ có thêm quan sát với một luồng gió nào đó.

Dữ liệu vào

Dòng đầu tiên gồm ba số nguyên dx, dy và k, trong đó dx và dy (1≤dx,dy≤103) là kích thước tối đa của cấu trúc tinh thể, còn k (1≤k≤10) là số lần thổi gió qua tinh thể.

Mỗi dòng trong k dòng tiếp theo mô tả dữ liệu của một luồng gió. Dòng bắt đầu bằng hai số nguyên wx và wy (−dx≤wx≤dx và −dy≤wy≤dy, không đồng thời bằng 0) là hướng của gió. Tiếp theo là số nguyên b (0≤b≤105) là số biên mà luồng gió này gặp. Cuối dòng là b cặp số nguyên x,y đôi một phân biệt (1≤x≤dx và 1≤y≤dy), liệt kê các biên quan sát được.

Dữ liệu vào đảm bảo phù hợp với ít nhất một tinh thể, và không có phân tử nào nằm ngoài kích thước đã cho.

Dữ liệu ra

In ra hai biểu diễn dạng văn bản của cấu trúc tinh thể, cách nhau bởi một dòng trống. Mỗi cấu trúc gồm dy dòng, mỗi dòng dx ký tự, góc trên bên trái ứng với vị trí (1,1) (ký tự thứ x của dòng thứ y ứng với vị trí (x,y)). Cấu trúc thứ nhất là cấu trúc có số phân tử ít nhất phù hợp với các quan sát, cấu trúc thứ hai là cấu trúc có số phân tử nhiều nhất. Dùng # cho vị trí có phân tử và . cho vị trí không có phân tử.

Ràng buộc

  • 1≤dx,dy≤103, 1≤k≤10.
  • −dx≤wx≤dx, −dy≤wy≤dy, (wx,wy)≠(0,0).
  • 0≤b≤105 với mỗi luồng gió; các biên của cùng một luồng gió đôi một phân biệt.
  • Dữ liệu phù hợp với ít nhất một tinh thể.

Ví dụ

Input Output Giải thích
6 6 3
1 1 3 3 1 1 3 2 2
0 2 6 3 1 1 3 2 2 6 4 5 3 4 2
1 -1 4 1 3 2 4 3 5 4 6
..#...
.#.#..
#.#.#.
.#.#.#
..#.#.
...#..

..#...
.#.#..
#.#.#.
.#.#.#
..#.#.
...#..
Chín phân tử được quan sát trực tiếp; ba phân tử (3,3), (4,4), (5,5) là bắt buộc như giải thích ở trên. Cấu trúc ít nhất và nhiều nhất trùng nhau.
5 4 2
1 0 6 1 1 4 1 2 2 5 2 2 3 3 4
0 -1 7 1 1 4 1 5 2 2 3 3 4 4 4 5 4
#..#.
.#..#
.#...
..###

##.##
.##.#
.###.
..###
Gió (1,0) thổi từ trái sang, gió (0,−1) thổi từ dưới lên. Chẳng hạn (2,1) có thể có hoặc không có phân tử: nếu có thì nó không phải biên của cả hai luồng gió vì (1,1) và (2,2) đều có phân tử.

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