Codeforces Round

http://codeforces.com/contest/492

A 水题

A. Vanya and Cubes

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Vanya got _n_ cubes. He decided to build a pyramid from them. Vanya wants to
build the pyramid as follows: the top level of the pyramid must consist of 1
cube, the second level must consist of 1 + 2 = 3 cubes, the third level must
have 1 + 2 + 3 = 6 cubes, and so on. Thus, the _i_ -th level of the pyramid
must have 1 + 2 + … + ( _i_ - 1) + _i_ cubes.

Vanya wants to know what is the maximum height of the pyramid that he can make
using the given cubes.

Input

The first line contains integer _n_ ( 1 ≤ _n_ ≤ 10 4 ) — the number of
cubes given to Vanya.

Output

Print the maximum possible height of the pyramid in the single line.

Sample test(s)

input

output

input

output

Note

Illustration to the second sample:

#include <iostream>
#include <algorithm>
#include <iterator>
#include <deque>
#include <vector>
#include <unordered_set>
#include <unordered_map>
#include <set>
#include <valarray>
#include <list>
#include <stack>
#include <array>
#include <iomanip>
#include <map>
#include <string.h>
#include <queue>
#include <sstream>
#include <iomanip>
#include <fstream>
#include <stdio.h>

using namespace std;

int n,m;

int a[1000];

int main ()
{
    a[1] = 1;
    for(int i=1;i<=999;i++)
        a[i] = a[i-1]+i;
    while (cin>>n)
    {
        int i =1;
        int ans = 0;
        while (n-a[i] >=0)
        {
            n-=a[i];
            i++;
            ans++;
        }
        cout<<ans<<endl;
    }
    return 0;
}

B 简单贪心

B. Vanya and Lanterns

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Vanya walks late at night along a straight street of length _l_ , lit by _n_
lanterns. Consider the coordinate system with the beginning of the street
corresponding to the point 0 , and its end corresponding to the point _l_ .
Then the _i_ -th lantern is at the point _a_ _i_ . The lantern lights all
points of the street that are at the distance of at most _d_ from it, where
_d_ is some positive number, common for all lanterns.

Vanya wonders: what is the minimum light radius _d_ should the lanterns have
to light the whole street?

Input

The first line contains two integers _n_ , _l_ ( 1 ≤ _n_ ≤ 1000 , 1 ≤ _l_
≤ 10 9 ) — the number of lanterns and the length of the street respectively.

The next line contains _n_ integers _a_ _i_ ( 0 ≤ _a_ _i_ ≤ _l_ ). Multiple
lanterns can be located at the same point. The lanterns may be located at the
ends of the street.

Output

Print the minimum light radius _d_ , needed to light the whole street. The
answer will be considered correct if its absolute or relative error doesn’t
exceed 10 - 9 .

Sample test(s)

input

7 15
15 5 3 7 9 14 0

output

2.5000000000

input

2 5
2 5

output

2.0000000000

Note

Consider the second sample. At _d_ = 2 the first lantern will light the
segment [0, 4] of the street, and the second lantern will light segment [3,
5] . Thus, the whole street will be lit.

#include <iostream>
#include <algorithm>
#include <iterator>
#include <deque>
#include <vector>
#include <unordered_set>
#include <unordered_map>
#include <set>
#include <valarray>
#include <list>
#include <stack>
#include <array>
#include <iomanip>
#include <map>
#include <string.h>
#include <queue>
#include <sstream>
#include <iomanip>
#include <fstream>
#include <stdio.h>

using namespace std;

int n,l;
double a[1010];

int main ()
{
    while (cin>>n>>l)
    {
          for(int i=1;i<=n;i++)
                cin>>a[i];
          sort(a+1,a+1+n);

          double ans = a[1] ;

          for(int i=1;i<=n-1;i++)
          {
              ans = max (ans,(a[i+1]-a[i])*1.0/2);
          }

          ans = max(ans,l-a[n]);

          printf("%.10lf\n",ans);
    }
    return 0;
}

C 按照bi升序排列注意不要超时即可

C. Vanya and Exams

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Vanya wants to pass _n_ exams and get the academic scholarship. He will get
the scholarship if the average grade mark for all the exams is at least avg
. The exam grade cannot exceed _r_ . Vanya has passed the exams and got grade
_a_ _i_ for the _i_ -th exam. To increase the grade for the _i_ -th exam by
1 point, Vanya must write _b_ _i_ essays. He can raise the exam grade
multiple times.

What is the minimum number of essays that Vanya needs to write to get
scholarship?

Input

The first line contains three integers _n_ , _r_ , avg ( 1 ≤ _n_ ≤ 10 5
, 1 ≤ _r_ ≤ 10 9 , 1 ≤ avg ≤ min ( _r_ , 10 6 ) ) — the number of
exams, the maximum grade and the required grade point average, respectively.

Each of the following _n_ lines contains space-separated integers _a_ _i_
and _b_ _i_ ( 1 ≤ _a_ _i_ ≤ _r_ , 1 ≤ _b_ _i_ ≤ 10 6 ).

Output

In the first line print the minimum number of essays.

Sample test(s)

input

output

input

2 5 4
5 2
5 2

output

Note

In the first sample Vanya can write 2 essays for the 3rd exam to raise his
grade by 2 points and 2 essays for the 4th exam to raise his grade by 1 point.

In the second sample, Vanya doesn’t need to write any essays as his general
point average already is above average.

#include <iostream>
#include <algorithm>
#include <iterator>
#include <deque>
#include <vector>
#include <unordered_set>
#include <unordered_map>
#include <set>
#include <valarray>
#include <list>
#include <stack>
#include <array>
#include <iomanip>
#include <map>
#include <string.h>
#include <queue>
#include <sstream>
#include <iomanip>
#include <fstream>
#include <stdio.h>

using namespace std;

int n;
long long r;
long long avg,AVE;

struct q
{
    int a;
    int b;
}p[100010];

bool cmp(q aa,q bb)
{
    return aa.b < bb.b;
}

int main ()
{
    while (cin>>n>>r>>avg)
    {
        AVE= 0;
        for(int i=1;i<=n;i++)
        {
            cin>>p[i].a>>p[i].b;
            AVE+=p[i].a;
        }

        if (AVE >= avg*n)
        {
            cout<<0<<endl;
            return 0;
        }

        sort(p+1,p+1+n,cmp);

        long long  ans = 0;

        int i = 1;
        while ( AVE < avg*n )
        {
            ans += p[i].b * min ( r -p[i].a,n*avg - AVE );

            AVE += min(r -p[i].a,n*avg - AVE);

            i++;
        }

        cout<<ans<<endl;

    }

    return 0;
}