MAKHOA3 - Mã khóa bí mật 3
Giới hạn- Thời gian: 0.2s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Đọc đề đẹp hơn ở:
https://codeforces.com/group/FLVn1Sc504/contest/272672/problem/F
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 x N 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: K i A(i,1) A(i,2) ... 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,1) A(i,2) ... 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) ... 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,1) B(j,2) ... 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.
Chỉ 10 phút sau khi ConanKudo đưa thông tin về mã khóa, ll931110, với tốc độ code như gió, đã đưa ra được output. Tuy nhiên ll931110 đưa ra không phải chỉ 1 đáp án, mà những T ( T ≤ 5) đáp án khác nhau. Nhiệm vụ của bạn là kiểm tra xem đáp án nào là đáp án đúng (thỏa mãn tất cả M + N thông tin).
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.
- Dòng tiếp theo chứa số T - số đáp án khác nhau mà ll931110 đưa ra.
- Tiếp theo là T nhóm dòng, mỗi nhóm gồm M dòng, mỗi dòng gồm N ký tự mô tả kết quả mà ll931110 đưa ra.
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 T dòng, dòng thứ i là YES nếu kết quả thứ i của ll931110 đưa ra thỏa mãn tất cả M + N thông tin, ngược lại in ra NO.
Example
Input
3 3
1 1
1 1
1 1
1 1
1 1
1 1
2
100
010
001
100
010
000
Output
YES
NO
- Người up: voj
- Nguồn bài: VM11 - Tác giả: Nguyễn Thành Trung