Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 2698
Numbers to Numbers

Time Limit: 10 Seconds      Memory Limit: 32768 KB

Numbers in English are written down in the following way (only numbers less then 109 are considered). Number abc,def,ghi is written as “[abc] million [def] thousand [ghi]”. Here “[xyz] ” means the written down number xyz .

In the written down number the part “[abc] million” is omitted if abc = 0 , “[def] thousand” is omitted if def = 0 , and “[ghi] ” is omitted if ghi = 0 . If the whole number is equal to 0 it is written down as “zero”. Note that words “million” and “thousand” are singular even if the number of millions or thousands respectively is greater than one.

Numbers under one thousand are written down in the following way. The number xyz is written as “[x] hundred and [yz] . Here “[x] hundred and” is omitted if x = 0 . Note that “hundred” is also always singular.

Numbers under 20 are written down as “zero”, “one”, “two”, “three”, “four”, “five”, “six”, “seven”, “eight”, “nine”, “ten”, “eleven”, “twelve”, “thirteen”, “fourteen”, “fifteen”, “sixteen”, “seventeen”, “eighteen”, and “nineteen” respectively. Numbers from 20 to 99 are written down in the following way. Number xy is written as “[x0] [y] ”, and numbers divisible by ten are written as “twenty”, “thirty”, “forty”, “fifty”, “sixty”, “seventy”, “eighty”, and “ninety” respectively.

For example, number 987,654,312 is written down as “nine hundred and eighty seven million six hundred and fifty four thousand three hundred and twelve”, number 100,000,037 as “one hundred million thirty seven”, number 1,000 as “one thousand”. Note that “one” is never omitted for millions, thousands and hundreds.

Given English text with all numbers written as words, transform it to the text where all numbers are written as numbers. For example, the text “he had one hundred and ninety five dogs” must be tranformed to “he had 195 dogs”. You must perform a transformation in such a way that as many words as possible are transformed to numbers, so, for example, “three thousand” must be transformed to “3000”, not to “3 thousand”.

If there are several way to perform the transformation in such a way, you must do it so that the first number is as great as possible, for example “two thousand thirty two” must be transformed to “2032”, not “2030 2”. If there are still several ways, maximize the second number, and so on.

Input

There are mutilple cases in the input file.

Each case contains an English text that only contains English letters, punctuation marks (‘,’, ‘.’, ‘!’, ‘?’, ’:’, ’;’, ’(’, ’)’), and blanks (spaces and line feeds).

You must perform the transformation in the way described. Words in numbers to be transformed are separated with blanks only (so, for example, “thirty, three” may only be transformed as “30, 3”, not as “33”).

When performing transformation you must replace characters starting from the first letter of the first word in the number to the last one in the last word with digits.

Input file is not empty and its size does not exceed 20000 bytes.

There is an empty line after each case.

Output

Output the result of the transformation.

There should be an empty line after each case.

Sample Input

From three thousand one hundred and fifty teams selected 
from one thousand four hundred and eleven universities 
in seventy five countries competing at one hundred and
twenty seven sites and hundreds more competing at 
preliminary contests worldwide, seventy three teams 
of students competed for bragging rights and prizes 
at The Twenty Eighth Annual ACM International Collegiate 
Programming Contest World Finals sponsored by IBM on 
March Thirty One, Two Thousand Four, and hosted at the 
Obecni Dum, Prague by Czech Technical University in Prague. 

Sample Output

From 3150 teams selected 
from 1411 universities 
in 75 countries competing at 127 sites and hundreds more competing at 
preliminary contests worldwide, 73 teams 
of students competed for bragging rights and prizes 
at The 20 Eighth Annual ACM International Collegiate 
Programming Contest World Finals sponsored by IBM on 
March 31, 2004, and hosted at the 
Obecni Dum, Prague by Czech Technical University in Prague. 


Source: Andrew Stankevich's Contest #9
Submit    Status