ZOJ Problem Set - 2698
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.
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 the result of the transformation.
There should be an empty line after each case.
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.
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