Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

MAKHOA2 - Mã khóa bí mật 2

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/makhoa2


ConanKudo

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 MxN chỉ chứa các số 0 hoặc 1 (0 < M, N ≤ 30). 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: Ki A(i,1) A(i,2) ... A(i,Ki), có ý nghĩa là: Trên hàng i, có Ki đ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,1) A(i,2) ... A(i,Ki). ('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: Kj B(j,1) B(j,2) ... B(j,Kj), có ý nghĩa là: Trên cột j, có Kj đ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,1) B(j,2) ... B(j,Kj).

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.

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

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à Ki A(i,1) A(i,2) ... A(i,Ki) cho biết thông tin ứng với hàng i.
  • N dòng tiếp, dòng thứ j là Kj B(j,1) B(j,2) ... B(j,Kj) 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.

Đ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à 2.5 điểm.

- Nếu D <= max(M,N), bạn được 0 điểm.

- Nếu D = M + N bạn được 2.5 điểm.

- Trường hợp còn lại, bạn được

Example

Input
Output
 

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

1000110001
1000111011
1000110101
0101010001
0010010001
0001001000
0011011000
0001001000
0001001000
0001001000

MAKHOA2.png

 

Với output như trên, bạn sẽ được 2.5 điểm cho test này.
Trong lúc thi, bài của bạn sẽ được chấm với 50% số test của bài. Điểm tối đa bạn có thể đạt được là 50.

Được gửi lên bởi:VOJ Team
Ngày:2011-08-04
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:VM11 - Tác giả: Nguyễn Thành Trung

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.