ULM2H - Hall of Fountains
The Museum of Modern Art has a really exciting exhibition: a kind of a longish hall composed of a sequence of quadratic-shaped rooms. Each room is equipped with a water fountain. Each fountain is characterized by a number p and acts independent of the others. It will be turned on for exactly p seconds, then it will be turned off for exactly p seconds, then on again, then off again, and so on for good. However, different fountains may have different values of p. And even if they share the same value, they still may perform not identically, for they might have been started at different times.
You stand in front of the first room, and want to cross the hall to the other end. Each of your steps takes exactly 1 second. You are able to move one room forward (unless you already reached the other end), one room backward (unless you are at the beginning), or just stay at your current position. Calculate the shortest time to reach the other end, if it is possible at all.
Since you do not want to get wet, you can only move into a room where the water fountain will be off during the second after your step. For example, suppose that the fountain in the next room behaves so, that it is on at times 0, 1, 2, then off at times 3, 4, 5, 6, then on at times 7, 8, 9, 10, then off again (which indicates p=4 with an offset of 7). Then, you can move at time 2 into the room, arriving there at time 3, when the fountain is off. But you cannot move at time 6 into the room, because at time 7 it will be on.
Input Specification
The input contains several test cases. Each test case starts with the number of fountains n. Input is terminated by n=0. Otherwise, 1≤n≤100. Then follow n numbers p_{i} denoting the time each fountain is on and off, where 0≤p_{i}≤10. A value of 0 for p_{i} indicates that fountain i is out of order (i.e. constantly off). Then follow n numbers q_{i} denoting the offset of each fountain, where 0≤q_{i}<2*p_{i}, unless the fountain is out of order, in which case q_{i} is meaningless. Otherwise it means that fountain i will be on at time q_{i}, but off just one second before.
Output Specification
For each test case output on a line a single number t denoting the shortest time needed to reach the end of the hall (i.e. to enter the place after the last room). Assume, that you are in front of the first room at time 0 (i.e. you can enter the first room at time 1, if the fountain is off at time 1). If it is impossible to go through the hall of fountains, print 0 instead.
Sample Input
3 0 0 0 0 0 0 4 6 3 3 4 2 3 0 4 2 1 1 0 0 0 |
Sample Output
4 11 0 |
Added by: | abdelkarim |
Date: | 2013-08-28 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | University of Ulm Local Contest 2002 |