USACO 2021 - Open - Bronze - Acowdemia II

View as PDF

Submit solution

Points: 0.07 (partial)
Time limit: 0.5s
Memory limit: 256M
Input: stdin
Output: stdout

Suggester:
Problem source:
http://www.usaco.org/index.php?page=viewproblem2&cpid=1132
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Bessie đang nộp đơn vào ngành Khoa học máy tính tại Cao học, đồng thời, cô đã nhận được lời mời phỏng vấn tại một phòng thí nghiệm Khoa học máy tính danh tiếng. Để tránh xúc phạm bất kì ai, Bessie muốn so sánh kinh nghiệm của ~N~ ~(1 \le N \le 100)~ thành viên trong phòng thí nghiệm với nhau. Không có bất kì hai thành viên nào có cùng lượng kinh nghiệm, nhưng để xác định kinh nghiệm của họ thì khá khó. Để làm vậy, Bessie sẽ xem các bài xuất bản của phòng thí nghiệm.

Mỗi bài xuất bản gồm một danh sách các tác giả, danh sách này là một hoán vị tên của ~N~ thành viên phòng thí nghiệm. Danh sách được sắp xếp giảm dần dựa trên sự đóng góp của từng thành viên vào bài viết. Nếu có nhiều thành viên đóng góp như nhau thì họ sẽ được sắp xếp theo thứ tự bảng chữ cái. Vì thành viên có nhiều kinh nghiệm hơn thì có nhiều công việc hành chính hơn, nên một thành viên nhiều kinh nghiệm hơn sẽ không bao giờ đóng góp nhiều hơn một thành viên ít kinh nghiệm hơn.

Ví dụ, trong phòng thí nghiệm có ba thành viên, thành viên ít kinh nghiệm là Elsie, thành viên có nhiều kinh nghiệm hơn là Giáo sư Mildred và thành viên nhiều kinh nghiệm nhất là Giáo sư Dean. Sẽ có bài xuất bản (Elsie-Mildred-Dean) nếu cả ba thành viên đóng góp khác nhau và bài xuất bản (Elsie-Dean-Mildred) nếu Dean và Mildred đóng góp như nhau và Elsie đóng góp nhiều hơn.

Từ ~K~ ~(1 \le K \le 100)~ bài xuất bản của phòng thí nghiệm này, hãy giúp Bessie xác định với mỗi cặp thành viên trong phòng thí nghiệm này, ai có nhiều kinh nghiệm hơn.

Input

Dòng đầu tiên chứa hai số nguyên ~K~ và ~N~.

Dòng thứ hai chứa ~N~ xâu cách nhau bởi một dấu cách, mỗi xâu là tên của một thành viên. Mỗi xâu chỉ gồm các kí tự in thường và có độ dài tối đa là ~10~.

~K~ dòng tiếp theo, mỗi dòng gồm ~N~ xâu cách nhau bởi một dấu cách, thể hiện danh sách các tác giả cho một bài xuất bản.

Output

In ra ~N~ dòng, mỗi dòng chứa ~N~ kí tự. Ở dòng ~i~, với mỗi ~j \neq i~, kí tự thứ ~j~ là ~1~ nếu như thành viên thứ ~i~ có nhiều kinh nghiệm hơn thành viên thứ ~j~, là ~0~ nếu như thành viên thứ ~j~ có nhiều kinh nghiệm hơn thành viên thứ ~i~ và là ~?~ nếu như không thể xác định được điều đó từ các bài xuất bản đã cho.

Kí tự thứ ~i~ ở dòng ~i~ là ~B~ bởi vì Bessie thích kí tự đó.

Sample Input 1

1 3
dean elsie mildred
elsie mildred dean

Sample Output 1

B11
0B?
0?B

Giải thích: Trong ví dụ này, duy nhất một bài xuất bản (elsie-mildred-dean) không cho ta đủ thông tin để biết rằng Elsie có nhiều kinh nghiệm hơn Mildred hay không. Tuy nhiên, dễ dàng có thể thấy rằng, Dean có nhiều kinh nghiệm hơn hai người còn lại. Vậy nên, có hai cách sắp xếp kinh nghiệm có thể xảy ra là Elsie < Mildred < Dean và Mildred < Elsie < Dean.

Sample Input 2

2 3
elsie mildred dean
elsie mildred dean
elsie dean mildred

Sample Output 2

B00
1B0
11B

Giải thích: Trong ví dụ này, từ hai bài xuất bản, cách sắp xếp kinh nghiệm từ bé đến lớn của ba thành viên là Elsie < Mildred < Dean.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.