LightOJ 1275 - Internet Service Providers

1275 - Internet Service Providers

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 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 ≤ 109).

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

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

解题思路

题目大意给出N,C，满足数学式T*（C-N*T），问当T取什么值（整数值）时能让这个函数式的值最大。（T取满足条件的最小值）。

题解：很明显，就是一个求一元二次方程最高点横坐标的问题。顶点坐标(-b/(2*a)，(4*a*c-b*b)/(4*a))。要注意的地方是求出T后，是向下取整的，最大的整数最高点可能落在T+1上，这里需要比较一下。

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int main()
{
    int cn=0;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        long long n,m;
        scanf("%lld%lld",&n,&m);
        printf("Case %d: ",++cn);
        if(n==0||m==0)
        {
            printf("0\n");
        }
        else
        {
            long long cm1,cm,a1,a2;
            cm=(m/(2*n));
            a1=(-n*cm*cm)+m*cm;
            cm1=cm+1;
            a2=(-n*cm1*cm1)+m*cm1;
            if(a2>a1)
            {
                printf("%lld\n",cm1);
            }
            else
            printf("%lld\n",cm);
        }
    }
    return 0;
}