Time Limit: 2 Seconds
Memory Limit: 65536 KB
Staying fit is important for every superhero, and Spiderman is no exception.
Every day he undertakes a climbing exercise in which he climbs a certain height
of a tall building, rests for a minute, then climbs again, rests again, and
so on. The exercise is described by a sequence of heights d1, d2, d3, �� , dm
telling how many meters he is to climb before the first break, before the second
break, and so on. From an exercise perspective it does not really matter if
he climbs up or down at the ith climbing stage, but it is practical that sometimes
climbs up and sometimes climbs down, so that he both starts and finishes at
street level. Obviously, he can never be below street level! Also, he would
like to climb as short a building as possible (he does not like to admit it,
but he is actually afraid of heights). The building must be at least 2 meters
higher than the highest point his feet reach during the workout.
He wants your help in determining when he should go up and when he should go
down. The answer must be legal: it must start and end at street level (0 meters
above ground) and it may never go below street level. Among the legal solutions
he wants one that minimizes the required building height. When looking for a
solution, you may not reorder distances.
If the distances are 20 20 20 20, he can either climb up, up, down, down or
up, down, up, down. Both are legal, but the second one is better (in fact optimal)
because it only requires a building of height 22, whereas the first one requires
a building of height 42. If the distances are 3 2 5 3 1 2, an optimal legal
solution is to go up, up, down, up, down, down. Note that for some distance
sequences there is no legal solution at all (e.g., for 3 4 2 1 6 4 5).
The first line of the input contains an integer N giving the number of test
cases. The following 2N lines specify the test cases, two lines per test case:
the first line gives a positive integer M, which is the number of heights, and
the following line contains the M positive integer heights. For any test case,
the total distance climbed (the sum of the heights in that test case) is at
For each test case a single line should be output. This line should either be
the string "IMPOSSIBLE" if no legal solution exists, or it should
be a string of length M, containing only the characters "U" and "D",
where the ith character indicates if Spiderman should climb up or down at the
ith stage. If there are several different legal and optimal solutions, output
one of them (it does not matter which one as long as it is optimal).
20 20 20 20
3 2 5 3 1 2
3 4 2 1 6 4 5
Source: Asia 2003, Tehran (Iran), Preliminary