C |
Hats
Off Input: Standard Input Output: Standard Output |
It’s the Wild West. But things are
not quite well here, now. Last few months, many trains have been robbed by the mysterious
and vicious bandit called ‘El Diablo’. The railroad company has offered a
reward of about $150000 for the one
who can stop him. That’s why John Cooper is trying to catch him.
But the task is not that easy as it looks. That’s why John
made a team and planned to chase after the ‘El Diablo’. After a lot of hard
work and with mild plans, they finally managed to surround him in a room. But
the problem is that the only door of the room is locked and it can’t be
unlocked other than finding a combination.
There are n
stones scattered outside the room. Each of them is equal in size but labeled by
an integer number. The door has n
holes numbered from 1 to n. Any hole can contain at most one
stone. In the upper side of the door, m
pairs of integers are written. Each of them denotes a range of some consecutive
holes.
John is trying to arrange the stones in the holes such that, the maximum difference of the maximum labeled stone and the minimum labeled stone in any range is minimized. If John can place them in the best possible way, then the door will be unlocked.
El Diablo will escape if it takes more than 5 hours. Cause he is digging a hole
which leads to a cave. If he reaches the cave, all the plans and hark works
will be in vain, because he can escape through the cave. That’s why John is
seeking your help. Since John is not a programmer, he asks you to write a
program which will solve this problem and unlock the door. So, Hats off to you
for helping John. May be you will get a share of the reward if you can unlock
the door.
First line of the input will contain the number of cases T (<=300). Then T cases follow.
Each case will start with an integer n ( 1 <= n <= 30 ). The next line will contain n integers denoting the labels of the
stones. The next line will contain an integer m ( 1 <= m <= 5 ). Each of the next m lines will contain two integers a b ( 1 <= a <= b <= n ) denoting all the holes from a to b (inclusive). Each of the integers will be fit into a 32 bit signed integer.
For each case, print the case number and the desired result as shown below.
2 3 1 2 4 2 1 2 2 3 4 1 2 3 4 1 1 4 |
Case 1: 2 Case 2: 3 |
Problemsetter: Jane Alam Jan
Special Thanks: Manzurur
Rahman Khan