Bet
Time limit2sMemory limit1024 MB
Given two strings of letters and digits, decide whether both could come from one original string by replacing some Roman numeral substrings with Arabic numbers.
- Level
Medium7 of 10
- Topics
- Dynamic programming, String matching, String
- Solved
- No attempts yet
Problem
To free Anakin Skywalker and acquire a hyperdrive, Qui-Gon Jinn made a bet with Watto about who would win the Boonta Eve race. Few people know that Watto did what is often done on Tatooine: he cheated when the bet was made.
To officially register a dispute on Tatooine, the parties must go to the appropriate official, who issues two identical receipts. Both receipts carry the same string of characters, which in a faraway galaxy, many years later, will be called Latin letters.
Watto's trick was this. His acquaintance, the official, drew up nonstandard receipts. To stay within the law, he first wrote two correct receipts and then altered them. He picked an arbitrary substring that is a valid representation of a natural number in Roman numerals. Then he replaced that substring with the same number written in Arabic numerals, with no leading zeros. The official repeated this until no suitable substrings remained.
Qui-Gon Jinn never got cheated by Watto, so nobody ever mentioned this trick. Can you, a resident of a faraway galaxy, check whether the texts on the two nonstandard receipts could have come from one string?
Input
The first and second lines of the input each contain a string of lowercase Latin letters and digits. The length of each string does not exceed . It is guaranteed that no substring of these strings is a valid Roman numeral representation. It is guaranteed that every substring that is a natural number does not exceed in value. It is guaranteed that no all-digit substring starts with zero.
Output
Print YES if the two strings could have been obtained from one string, and NO otherwise.
Hint
In Roman numerals, I is 1, V is 5, X is 10, L is 50, C is 100, D is 500, and M is 1000. To write a number correctly, write the thousands first, then the hundreds, then the tens, and finally the units. Digits may repeat, but no more than three times. A smaller digit may be written to the left of a larger one, in which case it is subtracted from the larger one. In that case the smaller digit cannot be repeated. There are six subtractive forms: IV is , IX is , XL is , XC is , CD is , and CM is . No other subtractive forms are allowed.