| Author: | A. Baranov | Time limit: | 1 sec | |
| Input file: | Standard input | Memory limit: | 256 Mb | |
| Output file: | Standard output |
Let we have set of the N strings of the same length are consisted by 0 and 1. Next some previously unknown string from this set will be selected, whose index need to guess.
It is required to define optimal in the worst case sequence of compares that allows to recognize index of the input string. Result need presented as decision tree.
Each non leaf node of this tree contains i — position number in which comparison need to perform. It has exactly 2 childs (for each character of the alphabet).
If in the i-th position of the string there is a character with the number k, transition to the appropriate subtree where the search will be continued is performed.
Leafs of this tree correspond to terminal states of search and contain indices of recognized strings.
Input data contains N, followed by exactly N strings of the original set.
Output data must contain decision tree written in the next format.
Leaf node starts from symbol '=', followed by string number
(indices of strings starting by zero).
Non-leaf node starts from '>',
followed by position number in which comparison will be performed.
(position starting by zero).
Next the according subtree is written in same way.
It is guaranteed that all strings of the original set are distinct.
Their length does not exceed 32.
2 ≤ N ≤ 16
| No. | Standard input | Standard output |
|---|---|---|
| 1 | |
|
| 2 | |
|