LightOJ

Internet Service Providers

Time Limit: 2000MS

Memory Limit: 32768KB

64bit IO Format: %lld & %llu

Submit Status

Description

A group of N Internet Service Provider companies (ISPs) use a private communication channel that has a maximum capacity of C traffic units per second. Each company transfers T traffic units per second through the channel and gets a profit that is directly proportional to the factor T(C - T*N). The problem is to compute the smallest value of T that maximizes the total profit the N ISPs can get from using the channel. Notice that N, C, T, and the optimal T are integer numbers.

Input

Input starts with an integer T (≤ 20), denoting the number of test cases.

Each case starts with a line containing two integers N and C (0 ≤ N, C ≤ 10⁹).

Output

For each case, print the case number and the minimum possible value of T that maximizes the total profit. The result should be an integer.

Sample Input

6

1 0

0 1

4 3

2 8

3 27

25 1000000000

Sample Output

Case 1: 0

Case 2: 0

Case 3: 0

Case 4: 2

Case 5: 4

Case 6: 20000000

Source

Submit Status

 

求满足T(C-T*N) 值最大时的T值, x=对称轴时y最大 ; /*利润最大时取整 ;*/  关键是读题;

#include <cstdio>
typedef long long LL;
int main()
{
    int t, Q=1;
    scanf("%d", &t);
    while(t--)
    {
        LL N, C;
        scanf("%lld%lld", &N, &C);
        if(N==0||C==0)   // 0 和 开口向下的一元二次(顶点在原点)方程 ; 
        {
            printf("Case %d: %lld
", Q++, 0);
            continue;
        }
        LL T=C/2/N;
        LL rec1=T*(C-T*N);
        LL rec2=(T+1)*(C-(T+1)*N);
        LL rec=T;
        if(rec1<rec2)
            rec=T+1;
        printf("Case %d: %lld
", Q++, rec);
    }
    return 0;
}