ANARC07J - Johny Hates Math

Johnny is on probation! He has failed so many math courses and the Department has forced him to register in a remedial math course. He must pass the course or he'd be expelled from the University. In an attempt to impress his professor, Johnny is typing all his assignments on the computer. The latest assignment is rather simple, Johnny was given a set of problems to solve. Each problem had a list of one or more numbers that Johnny was supposed to add. Johnny has worked all night on the assignment, neatly typing his solution to each problem using a word processor as seen here:

4+12+3=19

As usual, Johnny woke up late, he hardly had the time to print the assignment and rush to class. Only in the classroom did he discover that, due to a printer driver problem, non of the plus signs were printed. The above line was printed as:

4123=19

Write a program to figure out where the pluses are supposed to be. All that Johnny remembers is that all the numbers were positive; None of the numbers, other than possibly the sum, had more than 5 digits; And none of the numbers had a zero as the left-most digit.

Input

The input consists of N (N <= 100) test cases. The number of them (N) is given on the first line of the input file. N lines follows each have an expression. No line will be longer than 256 characters.

Output

For each expression in the input, your program must print a line of result. Result is the expression with the necessary plus signs in place. There are no spaces in result. If there are more than one possible solution, print a solution that requires the least number of plus signs. Knowing how bad Johnny is in arithmetic, it is possible that there is no solution, in which case your program should print "IMPOSSIBLE" as the result.

Example

Input:
3
4123=19
15442147612367219875=472
111=8

Output:
4+12+3=19
15+44+21+47+61+23+67+21+98+75=472
IMPOSSIBLE

Added by:Amr Mesbah
Date:2011-09-02
Time limit:0.807s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:ANARC 2007

hide comments
2013-08-30 23:25:35 (Tjandra Satria Gunawan)(曾毅昆)
"If there are more than one possible solution, print a solution that requires the least number of plus signs" how about this case:
232222222322=4589?
there still exists more than one possible solution:
some of them:
2322+2222+23+22 and 23+2222+22+2322
which one should I print? for this kind of problem better using custom judge..
2012-05-11 06:24:22 :D
I still disagree. Reducing the time limit along with harder test cases will make the problem very hard. That would be ok, but is not required from the problem in classical set. And again we have more balant similarities between other problems in the main set. The problem still offers an interesting challenge in it's own.

Moving back to classical.

But I do agree that the time limit itself could be lower. I will try to contact the author on this matter.
2011-09-09 05:42:54 [Trichromatic] XilinX
@:D If the problem setter reduce the time limit to <10 secs and provide more (powerful) test cases, I'll move it back. (BTW, I think your pretty approach is worth 2 points.) At PKU Online Judge, large number of users passed this problem with DP+constant optimization.

Last edit: 2011-09-09 05:44:39
2011-09-08 21:02:00 :D
Why tutorial? Problems are considerably similar, but my algos for them were pretty different. There are much more similar pairs of problems in the classic set.

Last edit: 2011-09-08 21:02:21
2011-09-08 17:45:37 Buda IM (retired)
Maybe it could stay. Constraints are higher. Approach must be modified a little.
2011-09-08 13:24:49 [Trichromatic] XilinX
So it is. Moved to tutorial.
2011-09-04 10:21:50 Buda IM (retired)
This is almost same problem as original JEDNAKOS. Problem setter on spoj removed printing part.

Last edit: 2011-09-04 11:59:26
2011-09-03 13:11:05 Problem Solver
Read problem statement carefully... All what Johnny remembers is that all the numbers were positive; None of the numbers, other than possibly the sum, had more than 5 digits;
2011-09-03 05:31:58 Santiago Palacio
This can be done with 64-bit integer? or there are larger numbers? (I mean, obviusly the first number is very likely to be large, but the result...)

Last edit: 2011-09-03 05:32:08
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.