printРабочее место участника

printЗадачи

1153. Javanese Cryptoanalysis

Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Javanese is the language of the people in the Central and Eastern parts of the island of Java, Indonesia.
In 1926, a standard orthography using the English Alphabet was created for the Javanese language. This writing system uses all letters from A to Z. The five letters A, E, I, O, and U are vowels, while all other letters are consonants. In Javanese words vowels and consonants always alternate. This property is quite useful when deciphering encrypted Javanese texts.
A text `s` consists of words, each word contains only capital letters. Let's call text `s` legitimate if in each word of `s` vowels and consonants alternate (no two vowels and no two consonants are located next to each other).
A simple substitution cipher is applied to a text `s`. That is, a bijection `f\ :\ A\ →\ A` is chosen, where A is the set of capital letters. The encoded text `t` is obtained from `s` by substituting each letter `c` with `f(c)`.
You're given the encoded text `t`. Find any legitimate text `s` that can be encoded as `t`, or detect that there is no such legitimate `s`.
Input
The input file contains the encoded text `t`, a list of words separated by spaces and/or line breaks. Each word consists only of capital letters (A to Z).
The input file contains no more than 100 000 characters.
Output
If the text `t` cannot be an encoded legitimate text, output only one word "impossible".
Otherwise, output any legitimate text `s` that can be encoded into `t`. Separate words of `s` with spaces and/or line breaks. All letters in `s` should be capital.

Sample Input 1

O RISK LIP FOCUS LUCKY

Sample Output 1

A CODE FOR VALID FILES

Sample Input 2

NEERC

Sample Output 2

impossible
Source: ACM ICPC NEERC, 2008
loading