시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
4 초 | 512 MB | 127 | 57 | 48 | 57.831% |
Tira would like to join a multiplayer game with n other players. Each player has a character with some features. There are a total of k features, and each character has some subset of them.
The similarity between two characters A and B is calculated as follows: for each feature f, if both A and B have feature f or if none of them have feature f, the similarity increases by one.
Tira does not have a character yet. She would like to create a new, very original character so that the maximum similarity between Tira’s character and any other character is as low as possible.
Given the characters of the other players, your task is to create a character for Tira that fulfils the above requirement. If there are many possible characters, you can choose any of them.
The first line of input contains two integers n and k, where 1 ≤ n ≤ 105 is the number of players (excluding Tira) and 1 ≤ k ≤ 20 is the number of features.
Then follow n lines describing the existing characters. Each of these n lines contains a string of k digits which are either 0 or 1. A 1 in position j means the character has the j’th feature, and a 0 means that it does not have the j’th feature.
Output a single line describing the features of Tira’s character in the same format as in the input. If there are multiple possible characters with the same smallest maximum similarity, any one of them will be accepted.
3 5 01001 11100 10111
00010
1 4 0000
1111
ICPC > Regionals > Europe > Northwestern European Regional Contest > Nordic Collegiate Programming Contest > NCPC 2017 D번