| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 1024 MB | 9 | 2 | 2 | 40.000% |
You have a collection of strings of the same length $L$ and are wondering how similar they are. We can say that the distance $d(S,T)$ between two strings $S$ and $T$ of the same length is the number of indices $i$ where $S_ i \neq T_ i$. For example, $d($berry, bears$) = 2$ since only the third and fifth characters differ.
You wonder if your strings are very close to each other. That is, for a given distance $D$ you have in mind, is there a string $S$ of length $L$ such that $d(S,A) \leq D$ for each string $A$ in your collection? Call such a string $S$ a central string. Note that a central string does not necessarily have to be one of your strings.
The first line of input contains three integers $N$ ($1 \leq N \leq 50$), $L$ ($1 \leq L \leq 1\, 000\, 000$), and $D$ ($0 \leq D \leq 6$). Here, $N$ indicates the number of strings in your collection, $L$ is the common length of these strings, and $D$ is the distance bound you are curious about. Then $N$ lines follow, the $i$’th such line contains a single string $A_ i$ of length $L$ consisting of only lowercase letters.
You are further guaranteed that $N \cdot L \leq 1\, 000\, 000$.
Output consists of a single line. If there is a string $S$ consisting of only lowercase letters such that $d(S,A_ i) \leq D$ for each $1 \leq i \leq N$, output any such string. Otherwise, simply output the single digit 0 to indicate there is no central string.
2 4 1 abba bbca
abca
3 4 3 abcd efgh ijkl
abgl
3 4 2 abcd efgh ijkl
0
University > University of Alberta Programming Contest > UAPC 2023 > Division 1 E번