Problem B. Boustrophedon ≡
| Author: | A. Klenin | Time limit: | 1 sec | |
| Input file: | input.txt | Memory limit: | 256 Mb | |
| Output file: | output.txt |
Statement
Boustrophedon is a type of bi-directional text, mostly seen in ancient manuscripts and other inscriptions.
Every other line of writing is reversed. Rather than going left-to-right as in modern English, alternate lines in boustrophedon must be read in opposite directions. The individual character images on reversed lines are mirrored too.
Notice that some Latin letters are symmetrical, and so do not need mirroring on the reversed lines. This way, some English texts may be written as boustrophedons with the standard font. The symmetrical letters are: A, H, I, M, O, T, U, V, W, X, Y.
The boustrophedon must consist of at least 3 lines. All lines of the boustrophedon must have the same number of characters (let us call it the width of the boustrophedon), except the last line, which may be shorter. The text contains only capital English letters (no spacing or punctuation).
You program must find the width of the widest boustrophedon that can be constructed from the given text and does not need letter mirroring.
Input file format
Input file contains a single string composed of capital Latin letters.Output file format
Output file must contain a single integer — maximum boustrophedon width. If there is no solution, output zero.Constraints
String length is between 1 and 100000 characters.
Sample tests
| No. | Input file (input.txt) |
Output file (output.txt) |
|---|---|---|
| 1 | |
|
| 2 | |
|