
ZOJ Problem Set  2698
Numbers in English are written down in the following way (only numbers less then 10^{9} 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 