What a Horrible and Dreadful Formula
Time limit1sMemory limit256 MB
Given a string where digits were replaced by English number words, recover the original arithmetic expression or report that none exists, then evaluate it left to right.
- Level
Hard8 of 10
- Topics
- String, Implementation, Brute force, Simulation
- Solved
- No attempts yet
Problem
A person who stared at numbers all day long lost his mind and did something dreadful. Thinking that if he did not want to see numbers, he could simply erase them, he wrote the following dreadful string.
ONETWOTHREEFOUR+TWOTHREEFOURFIVE=
That is right. As long as numbers are not visible, it is fine. So, looking at the table below, he replaced every digit with an English word.
But alas, while looking at the string, the person who wrote it lost consciousness. Let us look at the string, compute the original expression, and tell him the answer. If the expression before conversion can be determined exactly and the answer can be computed, output that answer. If no expression before conversion is possible, output "Madness!".
The expression before conversion starts with a positive integer, then positive integers and operators alternate, the last operator is =, and = appears only at the end of the expression. The operators that appear are +, -, x, /, and =, five in total. Unlike the usual order of operations, calculation proceeds from left to right, and when the / operation produces a non-integer, it is rounded toward zero. For example, 1.8 rounds to 1, and -1.8 rounds to -1.
Input
A string consisting of uppercase English letters and +,-,x,/,= is given. The string ends with =, and does not start with an operator. = always appears only at the end of the string. "ZERO" never appears at the start of the string or immediately after an operator.
The given string has length , and every number contained in the string is between and inclusive.
Output
If no expression before conversion is possible, output Madness!
If a possible expression exists, output that expression on the first line, and on the second line output the value of the expression with every digit converted back to an English word.
Constraints
The absolute value of every number appearing in the answer and in the calculation process is less than .