cho.shCompress
No attempts yetTime limit1sMemory limit128 MBProblem
Reduce the number of digits.
An experimental physicist generates a huge amount of data. The data has a special property, and he wants to exploit it to shrink the space needed to store the results.
The data comes as pairs of numbers where the first number is always smaller than the second. He wants to store each pair much the way people abbreviate a range of pages in a book: instead of writing "pages 11 through 18" they sometimes write "11-8".
Notation
| Symbol | Meaning | Example |
|---|---|---|
| $F$ | the first number of a pair | in "18482-02", $F = 18482$ |
| $C$ | the second number in compressed form | in "18482-02", $C = 02$ |
| $R$ | the second number in decoded (original) form | in "18482-02", $R = 18502$ |
| $\text{MSD}(x, y)$ | the $x$ most significant digits of $y$ in base ten; the empty string when $x \le 0$ | $\text{MSD}(3, 19283) = 192$, $\text{MSD}(0, 12)$ is empty |
| $\text{LSD}(x, y)$ | the $x$ least significant digits of $y$ in base ten, left-padded with zeros when needed | $\text{LSD}(2, 48290) = 90$, $\text{LSD}(2, 3) = 03$ |
Decoding a compressed second number
| Rule | Example |
|---|---|
| $C$ is always written with the fewest possible digits. | |
| If $C > F$, then $R = C$. | for "123-283": $F = 123$, $C = 283$, so $R = 283$ |
| If $C \le F$, apply the rules below. | |
| $\text{LSD}(\text{len}(C), R)$ always equals $C$. | |
| If $\text{LSD}(\text{len}(C), F) < C$, then $R$ is $\text{MSD}(\text{len}(F) - \text{len}(C), F)$ followed by the digits of $C$. | for "4137-223": $F = 4137$, $C = 223$; $\text{MSD}(1, 4137) = 4$, so $R = 4223$ |
| If $\text{LSD}(\text{len}(C), F) \ge C$, then $R$ is $10^{\text{len}(C)}$ plus $\text{MSD}(\text{len}(F) - \text{len}(C), F)$ followed by the digits of $C$. | for "8543-13": $F = 8543$, $C = 13$; $\text{MSD}(2, 8543) = 85$, so $R = 8513 + 100 = 8613$ |
Leading zeros in $C$ are significant: "7", "07" and "007" are all different. For example:
- for "2839-06": $F = 2839$, $C = 06$, so $R = 2906$
- for "2839-006": $F = 2839$, $C = 006$, so $R = 3006$
Your task is the reverse of decoding: given each uncompressed pair $F$ and $R$, output the compressed second number $C$ using the fewest possible digits.
Input
Each line contains a pair of non-negative integers separated by a hyphen. The second number is always larger than the first, and the second number is always less than $2^{31} - 1$. Read lines until end of file.
Output
For each input line, print one line containing the first number, a hyphen, and the compressed form of the second number.