Problem J
Two Knights' Poem
Two chess knights have decided to collaborate on writing short, one-line poems. They have obtained the use of a laptop to type their poetry. The laptop keyboard is composed of 4 rows of 10 keys. 30 of these are symbol keys, 4 are Shift keys, and 6 are Space keys.
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ | Q | W | E | R | T | Y | U | I | O | P | | | | | | | | | | | | | q | w | e | r | t | y | u | i | o | p | +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ | A | S | D | F | G | H | J | K | L | : | | | | | | | | | | | | | a | s | d | f | g | h | j | k | l | ; | +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ | Z | X | C | V | B | N | M | < | > | ? | | | | | | | | | | | | | z | x | c | v | b | n | m | , | . | / | +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ | | | | | | | | | | | |Shift|Shift|Space|Space|Space|Space|Space|Space|Shift|Shift| | | | | | | | | | | | +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
Note that the Shift and Space keys, which are usually extra-wide keys on a keyboard, are treated here as multiple individual keys that each have the same effect.
The knights will type the poem by making moves, one at a time, that are valid for a chess knight. A chess knight can move two positions vertically and then one horizontally, or one position vertically and then two horizontally. For example, from the D key, a knight can move to any of these keys: Q, Z, T, B, the second Shift key from the left, and the second Space key from the left.
One knight always begins each poem on the left-most Shift key. The other knight always begins on the right-most Shift key. Either knight may move first, and either may make multiple consecutive moves. The knights cannot occupy the same key.
Each move of a knight will type at most one character, adding to the poem. Landing on a symbol key or Space key will type one character. A knight landing on a symbol key types the upper value of that key when the other knight is on a Shift key; otherwise, the lower value is typed. Landing on a Space key always types a single space character, regardless of whether the other knight is on a Shift key. Landing on a Shift key does not add anything to the poem.
Input
There will be up to 10 test cases in the input. Each test case will consist of a string on a single line, representing a poem. Each poem will consist of 1 to 100 characters inclusive, using only characters from the symbol keys on the keyboard and spaces. No poem will begin or end with a space. The input will end with a line with a single asterisk (’*’).
Output
For each poem, output 1 if the knights can type the poem, or 0 if they cannot.
Sample Input 1 | Sample Output 1 |
---|---|
S,veA,eVE,aU S,veA,eVE,aUc CAlmimg eventa CAL * |
1 0 1 1 |