传送门

Codeforces


Description

One year ago, Mr. Ang joined a great company and he rented a house on the same street as the company. The company is so great that Mr. Ang doesn’t need to punch in and out. He can have a good sleep and gets up at any time.

Every day, he walks along the street, goes through N traffic lights numbered 1, 2, 3, …, N and arrives the company. It takes Mr. Ang S_0 seconds from the house to first traffic light. S_i seconds from traffic light i to traffic light i + 1 and S_N seconds from Nth traffic light to company. The time spent on the way to company depends on the state of traffic lights.

Mr. Ang got interested in the traffic lights and hacked into the system. After reading the code, he found that for traffic light i on his way, it stays A_i seconds green and then stays B_i seconds red and repeats. He also found that for all traffic lights, A_i + B_i are the same. He can modify the code to set different offsets OFF_i for the traffic lights. Formally, Mr. Ang can set the offsets for the traffic lights to OFF_i so that for each traffic light, Mr. Ang can go through it in time range [OFF_i + k \times (A_i + B_i), OFF_i + k \times (A_i + B_i) + A_i) and must wait in time range [OFF_i + k \times (A_i + B_i) + A_i, OFF_i + (k + 1) \times (A_i + B_i)) for all integers k.

Now Mr. Ang would like to make his commuting time from house to company as short as possible in the worst case. Find out the minimal time in second.


Input

The first line of the input gives the number of test cases, T. T test cases follow.

Each test case starts with a line which consists of one number N, indicating the number of traffic lights.

The next line consists of N + 1 numbers S_0, S_1, …, S_N indicating the walking time between house, traffic lights and company in seconds as described in the problem.

Then followed by N lines each consists of 2 numbers A_i, B_i indicating the length of green light and red light of the i^{th} traffic light.

  • 1 \le T \le 50.
  • 1 \le N \le 1000.
  • 1 \le A_i, B_i \le 120. All A_i + B_i are the same.
  • 1 \le S_i \le 10^6.

Output

For each test case, output one line containing “Case #x: y”, where x is the test case number (starting from 1) and y is the minimal time in second from house to company in the worst case.

y will be considered correct if it is within an absolute or relative error of 10^{-8} of the correct answer.


Sample Input

2
1
30 70
15 15
2
30 15 70
10 20
20 10

Sample Output

Case #1: 115.000000
Case #2: 135.000000


题目大意:

一个人从家到公司一共要经过n个红绿灯。从第i-1个红绿灯到第i个红绿灯需要花费S_i秒(假设家在第0个红绿灯,公司在第n+1个红绿灯),第i个红绿灯绿灯时长为A_i,红灯时长为B_i。保证所有的A_i + B_i相等,即红绿灯的周期相等。现在你能够调整所有红绿灯的相位,使得这个人在最坏情况下从家到公司所需时间最少,求最少是多少?

解题思路:

由于你能够调整所有红绿灯的相位,所以在路上花的时间是不会影响到他等红绿灯的时间。现在就只需要考虑如何使得在最坏情况下等红绿灯的时间最短,容易看出,这个时间为max(B_i)

Code:

/*Program from Luvwgyx*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void print(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar(x%10+'0');
}
void write(int x){print(x);puts("");}
int main(){
    int T=read(),cas=0;
    while(T--){
        int n=read(),sum=0,mx=0;
        for(int i=1;i<=n+1;i++)sum+=read();
        for(int i=1;i<=n;i++)read(),mx=max(mx,read());
        printf("Case #%d: %.6lf\n",++cas,(double)sum+mx);
    }
    return 0;
}