<PREV Problem:
NEXT>
Solved by 104 users: ...
UserDateAttemptTimeCMSC
daniel.ugra08 jan 2007Ruby1100.0880 
ravehanker19 feb 2007Python1000.44102 
Philip_PV13 jul 2008C++200.11106 
Philip_PV13 jul 2008C++100.11109 
RAVEman11 jan 2009C++500.02111 
RAVEman11 jan 2009C++400.02116 
david_it2119 apr 2008Ruby1000.19116 
WsemirZ18 may 2008Ruby2300.20116 
ethanhunt14 aug 2007C++900.03119 
tomek19 nov 2006C++100.03121 
Philip_PV13 jul 2008C300.01128 
Stranger23 sep 2007C++400.04128 
Shurik16 nov 2006Kylix100.56130 
Languages
C++
75
FPC
11
Kylix
8
C
8
Ruby
4
Java
3
Python
1
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 

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.

Input#1
00
Output#1
200

Input#2
22
Output#2
20200

Input#3
3002010
Output#3
3002010


Author:
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 200ms

SW soft NIX
ID = 18.232.51.247