<PREV Problem:
Solved by 104 users: ...

Grammar of a Great Machine (Correct words 1)

Time limit = 1 second(s)

The Association of Great Machines (AGM) has recently made a breakthrough in their archaeological excavations. They have found an ancient artifact with some codes definitely produced by some Great Machine built many centuries ago by a highly intelligent civilization now extinct. Researchers think that these codes incorporate the great wisdom of that civilization. However, the progress in deciphering the code has halted because some words were badly damaged and some letters were not readable.

Researchers have found out that the Great Machine was using only words of particular structure and composition. Each such word can only consist of digits from 0 to 7 (inclusive) and was definitely built from the word S by one or more of the following rules:

 S ::= 0
 S ::= 1 S
 S ::= 2 S S
 S ::= 3 S S S
 S ::= 7 S S S S S S S

Each of these rules can be applied several times if needed, and they can be used in any order. Single use of a rule replaces one chosen S character in a word by a string at the right side of that particular rule specification. For example, the word 2S0 can be transformed to 22SS0 by the third rule.

Please help researchers to reconstruct these words and decipher the whole message from an ancient civilization. You will be given the remains of a correct word consisting of digits from 0 to 7 only. Researchers are quite sure that only a small fraction of letters was lost, so they want you to determine the correct word of minimal length that will contain a given word as a subsequence.

Correct words: 0, 10, 200, 111111110, 200, 3000, 21010, 70000000, 400400000, ...

Not correct words: 1, 2, 4, 22, 12, 01, 30, 2070, 11111, 21111110, ...

Input. The input contains a single line with a non-empty string consisting of digits from 0 to 7 (inclusive). The total number of digits will be less than or equal to 30000.

Output. Print out a single line with a correct word of minimal length that contains a given word as a subsequence. In case several such words of the same minial length exist you may output any of them.




ACM ICPC 2006, Moscow Subregion, Artem Voroztsov & Eugene Barsky
4 November 2006

<PREV | Problem set | Search related messages | NEXT>

© acm.mipt DevGroup
The page was generated in 180ms

SW soft NIX
ID =