1275 - Internet Service Providers    PDF (English)StatisticsForum Time Limit: 2 second(s)Memory Limit: 32 MB

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 thatN, 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

Output for Sample Input

6

1 0

0 1

4 3

2 8

3 27

25 1000000000

Case 1: 0

Case 2: 0

Case 3: 0

Case 4: 2

Case 5: 4

Case 6: 20000000

 

二元一次方程求最大值时x坐标， 题目x取整数，最后再比较比较x和x+1时方程的最大值 #include<cstdio> int main() { int t,n,c,k=1; int m; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&c); if(n==0||c==0) { printf("Case %d: 0\n",k++); continue; } m=c/(2*n); if((c*m-n*m*m)>=(c*(m+1)-n*(m+1)*(m+1))) printf("Case %d: %d\n",k++,m); else printf("Case %d: %d\n",k++,m+1); } return 0; }