VM 11 Bài 05 - Mã khóa bí mật 2

View as PDF

Submit solution

Points: 2.00 (partial)
Time limit: 2.0s
Memory limit: 512M

Problem source:
VM11 - Tác giả: Nguyễn Thành Trung
Problem type
Allowed languages
C, C++, Java, Pascal, Python, TEXT

Hè đã về!! ConanKudo đã tự hứa sẽ làm một việc gì đó có ích trong hè này, và bây giờ là lúc anh bắt đầu.

ConanKudo đi thuyền tới một hòn đảo giấu vàng. Sau nhiều ngày tìm kiếm, anh phát hiện ra một chiếc hòm đã bị khóa. Hiển nhiên ConanKudo không thể phá khóa vì hệ thống kích nổ sẽ hoạt động, và cái mà anh nhận được sẽ chỉ là một đống tro. Do đó, việc tìm ra chìa khóa để mở chiếc hòm là rất cần thiết.

Chìa khóa này là một bảng kích thước ~M \times N~ chỉ chứa các số ~0~ hoặc ~1~ ~\left(0 < M,\text{ } N \leq 30\right)~. Các hàng được đánh số từ ~1~ đến ~M~, và các cột được đánh số từ ~1~ đến ~N~. Từ những người đến trước (và thất bại trong việc mở khóa), ConanKudo đã thu thập được ~M + N~ thông tin. Mỗi thông tin tương ứng với một hàng hoặc một cột của bảng, và có ~1~ trong ~2~ dạng:

Dạng 1: ~K_i~ ~A_{i,1}~ ~A_{i,2}~ ~\ldots~ ~A_{i,K_i}~, có ý nghĩa là: Trên hàng ~i~, có ~K_i~ đoạn được tạo bởi "dãy dài nhất các số ~1~ liên tiếp", và độ dài các đoạn lần lượt (từ trái sang phải) là ~A_{i,2}~ ~\ldots~ ~A_{i,K_i}~. ("Dãy dài nhất các số ~1~ liên tiếp" là dãy gồm các số ~1~ liên tiếp và không là một dãy con của dãy các số ~1~ liên tiếp khác).

Dạng 2: ~K_j~ ~B_{j,1}~ ~B_{j,2}~ ~\ldots~ ~B_{j,K_j}~, có ý nghĩa là: Trên cột ~j~, có ~K_j~ đoạn được tạo bởi "dãy dài nhất các số ~1~ liên tiếp", và độ dài các đoạn lần lượt (từ trên xuống dưới) là ~B_{j,2}~ ~\ldots~ ~B_{j,K_j}~.

Có ~M~ thông tin dạng ~1~ tương ứng với ~M~ hàng, và ~N~ thông tin dạng ~2~ tương ứng với ~N~ cột.

Cho kích thước bảng mã khóa, và các thông tin, hãy giúp ConanKudo xác định mã khóa.

Input

  • Dòng ~1~: ~2~ số nguyên ~M, N~ cách nhau bởi dấu cách.
  • ~M~ dòng tiếp, dòng thứ ~i~ là ~K_i~ ~A_{i,1}~ ~A_{i,2}~ ... ~A_{i,K_i}~ cho biết thông tin ứng với hàng ~i~.
  • ~N~ dòng tiếp, dòng thứ ~j~ là ~K_j~ ~B_{j,1}~ ~B_{j,2}~ ... ~B_{j,K_j}~ cho biết thông tin ứng với cột ~j~.

Chú ý:

- Các dòng trắng thừa có thể xuất hiện ở bất kỳ vị trí nào trong file.

- Nếu một hàng không có số ~1~ nào, thì ràng buộc tương ứng sẽ gồm duy nhất ~1~ số ~0~.

Output

  • Gồm ~M~ dòng, mỗi dòng ~N~ ký tự ~0~ hoặc ~1~, thể hiện mã khóa.

Giới hạn

Trong ít nhất ~50\%~ test, bài toán chỉ có 1 nghiệm duy nhất.

Điểm của bạn được cho như sau: Gọi ~D~ là số hàng và cột thỏa mãn điều kiện. Điểm lớn nhất có thể đạt được của một test là ~3~ điểm.

  • Nếu ~D \leq max(M, N)~, bạn được ~0~ điểm.
  • Nếu ~D = M + N~ bạn được ~3~ điểm.
  • Trường hợp còn lại, bạn được $$\frac{D - max(M, N)}{M + N - max(M, N)} \times 2.5 + 0.5$$

Sample Input

10 10
3 1 2 1
3 1 3 2
4 1 2 1 1
4 1 1 1 1
3 1 1 1

2 1 1
2 2 2
2 1 1
2 1 1
2 1 1

1 3
1 1
2 1 1
2 1 5
1 3

2 5 1
2 1 5
1 1
1 1
1 5

Sample Output

1000110001
1000111011
1000110101
0101010001
0010010001
0001001000
0011011000
0001001000
0001001000
0001001000

Note

Với output như trên, bạn sẽ được ~3~ điểm cho test này.

image


Comments

Please read the guidelines before commenting.


There are no comments at the moment.