HPU Summer Training Day 6（河南理工大学暑期第六天）

Pie

Description:
My birthday is coming up and traditionally I'm serving pie. Not just one pie, no, I have a number N of them, of various tastes and of various sizes. F of my friends are coming to my party and each of them gets a piece of pie. This should be one piece of one pie, not several small pieces since that looks messy. This piece can be one whole pie though.

My friends are very annoying and if one of them gets a bigger piece than the others, they start complaining. Therefore all of them should get equally sized (but not necessarily equally shaped) pieces, even if this leads to some pie getting spoiled (which is better than spoiling the party). Of course, I want a piece of pie for myself too, and that piece should also be of the same size.

What is the largest possible piece size all of us can get? All the pies are cylindrical in shape and they all have the same height 1, but the radii of the pies can be different.
Input
One line with a positive integer: the number of test cases. Then for each test case:
---One line with two integers N and F with 1 <= N, F <= 10 000: the number of pies and the number of friends.
---One line with N integers ri with 1 <= ri <= 10 000: the radii of the pies.
Output
For each test case, output one line with the largest possible volume V such that me and my friends can all get a pie piece of size V. The answer should be given as a floating point number with an absolute error of at most 10^(-3).
Sample Input

3
3 3
4 3 3
1 24
5
10 5
1 4 2 3 4 5 6 5 4 2

Sample Output

25.1327
3.1416
50.2655

Problem solving:
注意到人数也得算得上自己，然后因为每个人分到的pie必须是一块（所以不可以平均分），这个时候就用到二分答案了。
二分中检测是否满足题意的判断方法是，用一个for循环计算出以每人分到mid面积时可以分给多少人，跟需要分到的人数进行比较就行了。
Code:

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const double pi = acos(-1.0);
double       s[10005];
int main()
{
    int n;
    cin >> n;
    while (n--)
    {
        int a, b, x; double sum = 0, pm = 0;
        cin >> a >> b;
        b += 1;
        for (int i = 0; i < a; i++)
        {
            cin >> x;
            s[i] = x * x * pi;
            sum += s[i];
            pm   = max(pm, s[i]);
        }
        double l = 0, r = sum / b, mid;
        while (r - l > 0.000001)
        {
            mid = (r + l) / 2;
            int now = 0;
            for (int i = 0; i < a; i++)
            {
                now += int(s[i] / mid);
            }
            if (now < b)
                r = mid;
            else
                l = mid;
        }
        printf("%.4lf\n", mid);
    }
}

Best Cow Line

Description:
FJ is about to take his N (1 ≤ N ≤ 2,000) cows to the annual"Farmer of the Year" competition. In this contest every farmer arranges his cows in a line and herds them past the judges.

The contest organizers adopted a new registration scheme this year: simply register the initial letter of every cow in the order they will appear (i.e., If FJ takes Bessie, Sylvia, and Dora in that order he just registers BSD). After the registration phase ends, every group is judged in increasing lexicographic order according to the string of the initials of the cows' names.

FJ is very busy this year and has to hurry back to his farm, so he wants to be judged as early as possible. He decides to rearrange his cows, who have already lined up, before registering them.

FJ marks a location for a new line of the competing cows. He then proceeds to marshal the cows from the old line to the new one by repeatedly sending either the first or last cow in the (remainder of the) original line to the end of the new line. When he's finished, FJ takes his cows for registration in this new order.

Given the initial order of his cows, determine the least lexicographic string of initials he can make this way.

Input

• Line 1: A single integer: N
• Lines 2: N+1: Line i+1 contains a single initial ('A'..'Z') of the cow in the ith position in the original line

Output
The least lexicographic string he can make. Every line (except perhaps the last one) contains the initials of 80 cows ('A'..'Z') in the new line.

Sample Input

6
A
C
D
B
C
B

Sample Output

ABCBCD

Problem solving:
白书原题，经典贪心问题。先比较当前的第一个和最后一个字符，如果想等就比较第二个和倒数第二个字符，以此找到前后字符的大小关系，然后进行删除和添加的操作就行了。具体看代码。
注意，每输出80个字符就得换行！！！

Code:

#include<iostream>
#include<cstdio>
using namespace std;
int n;
char a[2005];
void solve()
{
    int p=0,x=0,b=n-1;
    while(x<=b)
    {
        int flag=0;
        for(int i=0;x+i<=b;i++)
        {
            if(a[x+i]<a[b-i])
            {
                flag=1;
                break;
            }
            else if(a[x+i]>a[b-i])
            {
                flag=0;
                break;
            }
        }
        if(flag)    putchar(a[x++]);
        else    putchar(a[b--]);
        p++;
        if(p%80==0)    puts("");
    }
    puts("");
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)    cin>>a[i];
    solve();
    return 0;
}

Trailing Zeroes (III)

Description:
You task is to find minimal natural number N, so that N! contains exactly Q zeroes on the trail in decimal notation. As you know N! = 12...*N. For example, 5! = 120, 120 contains one zero on the trail.

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

Each case contains an integer Q (1 ≤ Q ≤ 1e8) in a line.

Output
For each case, print the case number and N. If no solution is found then print 'impossible'.

Sample Input

3
1
2
5

Sample Output

Case 1: 5
Case 2: 10
Case 3: impossible

Problem solving:
求n的阶乘的0的个数，只需要求得n中5得个数即可。因为只有2*5=10，所以每一个0都对应着一个2和一个5，而二的个数多于5，所以我们只要找到5得个数就是0得个数。

\\找5得个数得方法
long long co(long long x)
{
    long long ans = 0;
    while (x)
    {
        ans += x / 5;

        x /= 5;
    }
    return ans;
}

剩下的就是二分答案。注意这道题存在着“impossible”得情况，所以在二分得过程中如果遇到了满足题意得mid，一定要记录下来。方便后面判断。

Code:

#include <iostream>
using namespace std;
long long co(long long x)
{
    long long ans = 0;
    while (x)
    {
        ans += x / 5;

        x /= 5;
    }
    return ans;
}
int main()
{
    long long t, q;
    cin >> t;
    long long cas = 1;
    while (t--)
    {
        cin >> q; long long flag = 0;
        long long           l = 1, r = 1000000000000, mid;
        while (l <= r)
        {
            mid = (l + r) / 2;
            if (co(mid) == q)
            {
                flag = mid;
                r    = mid - 1;
            }
            else if (co(mid) > q)
                r = mid - 1;
            else
                l = mid + 1;
        }
        if (flag)
            cout << "Case " << cas++ << ": " << flag << endl;
        else
            cout << "Case " << cas++ << ": " << "impossible" << endl;
    }
}

The Frog's Games

Description:
The annual Games in frogs' kingdom started again. The most famous game is the Ironfrog Triathlon. One test in the Ironfrog Triathlon is jumping. This project requires the frog athletes to jump over the river. The width of the river is L (1<= L <= 1000000000). There are n (0<= n <= 500000) stones lined up in a straight line from one side to the other side of the river. The frogs can only jump through the river, but they can land on the stones. If they fall into the river, they
are out. The frogs was asked to jump at most m (1<= m <= n+1) times. Now the frogs want to know if they want to jump across the river, at least what ability should they have. (That is the frog's longest jump distance).
Input
The input contains several cases. The first line of each case contains three positive integer L, n, and m.
Then n lines follow. Each stands for the distance from the starting banks to the nth stone, two stone appear in one place is impossible.
Output
For each case, output a integer standing for the frog's ability at least they should have.
Sample Input

6 1 2
2
25 3 3
11
2
18

Sample Output

4
11

Problem solving:
题意就是让你找到青蛙得最大的最小弹跳力，即每次可以跳的最远距离。
左边界时每个石头间距的最大值，右边界是河的宽度，然后进行二分。每次二分的时候，找到处于当前位置位置的青蛙跳一次mid的距离刚好最小到达的点，然后进行下一次循环（具体看代码吧）
Code:

#include<bits/stdc++.h>
using namespace std;
const int maxn=500005;
int a[maxn];
int main()
{
    int i,L,n,m;
    while(scanf("%d%d%d",&L,&n,&m)!=EOF)
    {
        memset(a,0,sizeof(a));
        for(i=1;i<=n;i++)
            scanf("%d",&a[i]);
        a[n+1]=L;
        sort(a+1,a+n+2);
        int maxx=0;
        for(i=1;i<=n+1;i++)
        {
            if(a[i]-a[i-1]>maxx)
            maxx=a[i]-a[i-1];        
        }
        int l=maxx,r=L;
        while(l<=r)
        {
            int ans=0,pos=0;
            int mid=(l+r)/2;
            for(i=1;i<=n;i++)
            {
                if(a[i]-a[pos]<=mid&&a[i+1]-a[pos]>mid)//i即为青蛙跳一次之后到达的最远的石头
                {
                    pos=i;
                    ans++;
                }
            }
            ans++;
            if(ans<=m)    r=mid-1;
            else    l=mid+1;
        }
        printf("%d\n",l);
    }
    return 0;
}

湫湫系列故事——消灭兔子

Description:
湫湫减肥
　　越减越肥！
　　
　　最近，减肥失败的湫湫为发泄心中郁闷，在玩一个消灭免子的游戏。
　　游戏规则很简单，用箭杀死免子即可。
　　箭是一种消耗品，已知有M种不同类型的箭可以选择，并且每种箭都会对兔子造成伤害，对应的伤害值分别为Di（1 <= i <= M），每种箭需要一定的QQ币购买。
　　假设每种箭只能使用一次，每只免子也只能被射一次，请计算要消灭地图上的所有兔子最少需要的QQ币。
Input
输入数据有多组，每组数据有四行；
第一行有两个整数N，M（1 <= N, M <= 100000），分别表示兔子的个数和箭的种类；
第二行有N个正整数，分别表示兔子的血量Bi（1 <= i <= N）；
第三行有M个正整数，表示每把箭所能造成的伤害值Di（1 <= i <= M）；
第四行有M个正整数，表示每把箭需要花费的QQ币Pi（1 <= i <= M）。

特别说明：
1、当箭的伤害值大于等于兔子的血量时，就能将兔子杀死；
2、血量Bi，箭的伤害值Di，箭的价格Pi，均小于等于100000。
Output
如果不能杀死所有兔子，请输出”No”，否则，请输出最少的QQ币数，每组输出一行。
Sample Input

3 3
1 2 3
2 3 4
1 2 3
3 4
1 2 3
1 2 3 4
1 2 3 1

Sample Output

6
4

Problem solving:
将兔子的血量进行降序排序，然后将剑按照攻击力降序排列，如果攻击力相等就按照qq币的花费降序排列。
要用到优先队列，对降序排列的兔子，找到攻击力大于它的剑，放进优先队列，直到攻击力小于兔子的血量，然后答案加上优先队列顶部的qq消费。如果兔子还没杀完队列就为空了，就输出no。贪心的思想。

Code:

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
struct node{
    int d,p;
    friend bool operator < (node a,node b)
    {
        return a.p>b.p;
    }
}x[maxn];
int b[maxn];
bool cmp2(int x,int y)
{
    return x>y;
}
bool cmp(node a,node b)
{
    if(a.d==b.d)    return a.p>b.p;
    return a.d>b.d;
}
int main()
{
    int n,m;
    while(cin>>n>>m)
    {
        for(int i=0;i<n;i++)    cin>>b[i];
        sort(b,b+n,cmp2);
        for(int i=0;i<m;i++)    cin>>x[i].d;
        for(int i=0;i<m;i++)    cin>>x[i].p;
        sort(x,x+m,cmp);
        priority_queue<node> sta;
        int pos=0;
        long long ans=0;
        int flag=0;
        for(int i=0;i<n;i++)
        {
            while(x[pos].d>=b[i]&&pos<m)
            {
                sta.push(x[pos]);
//                cout<<x[pos].d<<" "<<x[pos].p<<endl;
                pos++;
            }
            if(sta.empty())
            {
                flag=1;
                break;
            }
//            cout<<sta.top().p<<"?\n";
            ans+=sta.top().p;
            sta.pop();
        }
        if(flag)    puts("No");
        else    cout<<ans<<endl;
    }
}

Strange fuction

Description:
Now, here is a fuction:
F(x) = 6 x^7+8x^6+7x^3+5x^2-y*x (0 <= x <=100)
Can you find the minimum value when x is between 0 and 100.
Input
The first line of the input contains an integer T(1<=T<=100) which means the number of test cases. Then T lines follow, each line has only one real numbers Y.(0 < Y <1e10)
Output
Just the minimum value (accurate up to 4 decimal places),when x is between 0 and 100.
Sample Input

2
100
200

Sample Output

-74.4291
-178.8534

Problem solving:
简单的数学题，求函数极值，对函数求一阶导，另它为0即可，因为本题中二次导之后函数恒大于0所以一阶导为0求出来的极值就是极小值。确定x的值得时候用二分确定

Code:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int    t;
    double y;
    cin >> t;
    while (t--)
    {
        cin >> y;
        double l = 0, r = 100, x;
        while (r - l > 0.000001)
        {
            x = (l + r) / 2;
            double mmp;
            mmp = 42 * pow(x, 6) + 48 * pow(x, 5) + 21 * pow(x, 2) + 10 * x;
            if (mmp < y)
                l = x;
            else
                r = x;
        }
        double ans = 6 * pow(x, 7) + 8 * pow(x, 6) + 7 * pow(x, 3) + 5 * x * x - y * x;
        printf("%.4lf\n", ans);
    }
    return 0;
}

Can you find it?

Description:
Give you three sequences of numbers A, B, C, then we give you a number X. Now you need to calculate if you can find the three numbers Ai, Bj, Ck, which satisfy the formula Ai+Bj+Ck = X.
Input
There are many cases. Every data case is described as followed: In the first line there are three integers L, N, M, in the second line there are L integers represent the sequence A, in the third line there are N integers represent the sequences B, in the forth line there are M integers represent the sequence C. In the fifth line there is an integer S represents there are S integers X to be calculated. 1<=L, N, M<=500, 1<=S<=1000. all the integers are 32-integers.
Output
For each case, firstly you have to print the case number as the form "Case d:", then for the S queries, you calculate if the formula can be satisfied or not. If satisfied, you print "YES", otherwise print "NO".
Sample Input

3 3 3
1 2 3
1 2 3
1 2 3
3
1
4
10

Sample Output

Case 1:
NO
YES
NO

Problem solving:
优雅的暴力之后再二分查找。
把前两个数组可以组成的所有的和用一个数组存下来（这一步最坏的情况的复杂度也才O（2e5），显然不会超时。然后对接下来输入的需要判断的每个值进行查找，对第三个数组中的每一个数
使用二分查找去找两者的差值再上一步得到的新数组中有没有存在。有即YES，否则就是NO。
Code:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 505;
int       a[maxn], b[maxn], c[maxn], d[250005];
int main()
{
    int l, n, m, cas = 0;
    while (~scanf("%d %d %d", &l, &n, &m))
    {
        for (int i = 0; i < l; i++)
            cin >> a[i];
        for (int j = 0; j < n; j++)
            cin >> b[j];
        for (int k = 0; k < m; k++)
            cin >> c[k];
        int pos = 0;
        sort(a, a + l); sort(b, b + n);
        for (int i = 0; i < l; i++)
        {
            for (int j = 0; j < n; j++)
            {
                d[pos++] = a[i] + b[j];
            }
        }
        sort(d, d + pos); sort(c, c + m);
        cout << "Case " << ++cas << ":\n";
        int p, mid;
        cin >> p;
        while (p--)
        {
            int flag = 0;
            cin >> mid;
            for (int i = 0; i < m; i++)
            {
                if (binary_search(d, d + pos, mid - c[i]))
                {
                    flag = 1;
                    break;
                }
            }
            if (flag)
                puts("YES");
            else
                puts("NO");
        }
    }
}

pairs

Description:
John has n points on the X axis, and their coordinates are (x[i],0),(i=0,1,2,…,n−1). He wants to know how many pairs that |x[b]−x[a]|≤k.(a that |x[b]−x[a]|≤k.
Sample Input

2
5 5
-100
0
100
101
102
5 300
-100
0
100
101
102

Sample Output

3
10

Problem solving:
排序之后直接进行二分查找，用lower_bound()或者手写也行，复杂度是O(N)

Code:

#include<bits/stdc++.h>
using namespace std;
const long long maxn=1e5+7;
long long p[maxn];
int main()
{
    long long t,a,b;
    cin>>t;
    while(t--)
    {
        cin>>a>>b;
        for(long long i=0;i<a;i++    )    cin>>p[i];
        sort(p,p+a);
        long long ans=0,pos=0;
        for(long long i=0;i<a;i++)
        {
            while(p[pos]-p[i]<=b&&pos<a)    pos++;
            ans+=pos-i-1;
        }
        cout<<ans<<endl;
    }
}

Radar Installation

Description:
Assume the coasting is an infinite straight line. Land is in one side of coasting, sea in the other. Each small island is a point locating in the sea side. And any radar installation, locating on the coasting, can only cover d distance, so an island in the sea can be covered by a radius installation, if the distance between them is at most d.

We use Cartesian coordinate system, defining the coasting is the x-axis. The sea side is above x-axis, and the land side below. Given the position of each island in the sea, and given the distance of the coverage of the radar installation, your task is to write a program to find the minimal number of radar installations to cover all the islands. Note that the position of an island is represented by its x-y coordinates.

Figure A Sample Input of Radar Installations

Input
The input consists of several test cases. The first line of each case contains two integers n (1<=n<=1000) and d, where n is the number of islands in the sea and d is the distance of coverage of the radar installation. This is followed by n lines each containing two integers representing the coordinate of the position of each island. Then a blank line follows to separate the cases.

The input is terminated by a line containing pair of zeros
Output
For each test case output one line consisting of the test case number followed by the minimal number of radar installations needed. "-1" installation means no solution for that case.
Sample Input

3 2
1 2
-3 1
2 1
1 2
0 2
0 0

Sample Output

Case 1: 2
Case 2: 1

Problem solving:
这道题跟暑假不AC很像（在前几天的训练中做过），对每个岛的坐标求出来以它为圆心，雷达探测半径为半径的圆与x的两个交点，然后对得到的每组左右端点进行贪心。（我的代码这里写的有点麻烦了，直接输入求交点就行，不用存岛的坐标）。

Code:

#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
struct node{
    int x,y;
    double l,r;
}p[1005];
bool cmp(node x,node y)
{
    if(x.r==y.r)    return x.l>y.l;
    return x.r<y.r;
}
int main()
{
    int n,d,i=0;
    while(scanf("%d %d",&n,&d)&&n&&d)
    {
        int flag=0;
        for(int i=0;i<n;i++)    cin>>p[i].x>>p[i].y;
        for(int i=0;i<n;i++)
        {
            if(p[i].y>d)
            {
                flag=1;
            }
            double mid;
            mid=sqrt(d*d-p[i].y*p[i].y);
            p[i].l=p[i].x-mid;
            p[i].r=p[i].x+mid;
        }
        if(flag)    cout<<"Case "<<++i<<": -1"<<endl;
        else
        {
            sort(p,p+n,cmp);
            int ans=1;double ri=p[0].r;
            for(int i=1;i<n;i++)
            {
                if(p[i].l>ri)
                {
                    ans++;
                    ri=p[i].r;
                }
            }
            cout<<"Case "<<++i<<": "<<ans<<endl;            
        }

    }
}

Aggressive cows

Description:
Farmer John has built a new long barn, with N (2 <= N <= 100,000) stalls. The stalls are located along a straight line at positions x1,...,xN (0 <= xi <= 1,000,000,000).

His C (2 <= C <= N) cows don't like this barn layout and become aggressive towards each other once put into a stall. To prevent the cows from hurting each other, FJ want to assign the cows to the stalls, such that the minimum distance between any two of them is as large as possible. What is the largest minimum distance?
Input

• Line 1: Two space-separated integers: N and C

• Lines 2..N+1: Line i+1 contains an integer stall location, xi
  Output

• Line 1: One integer: the largest minimum distance

Sample Input

5 3
1
2
8
4
9

Sample Output

3

Hint
OUTPUT DETAILS:

FJ can put his 3 cows in the stalls at positions 1, 4 and 8, resulting in a minimum distance of 3.

Huge input data,scanf is recommended.

Problem solving:
白书原题，经典二分题，二分答案，对mid的检测方法是看它能不能满足以mid为最小的距离时能住下的牛的个数大于等于要求的个数。

Code:

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
typedef long long ll;
ll n,c;
ll a[100005];
bool check(ll x)
{
    ll mmp=0;
    for(int i=1;i<c;i++)
    {
        ll mid=mmp+1;
        while(mid<n&&a[mid]-a[mmp]<x)
        {
            mid++;
        }
        if(mid==n)    return 0;
        mmp=mid;
    }
    return 1;
}
int main()
{
    scanf("%lld %lld",&n,&c);
    for(ll i=0;i<n;i++)
    {
        scanf("%lld",&a[i]);
    }
    sort(a,a+n);
    ll l=0,r=1e18,mid;
    while(r-l>1)
    {
        mid=(l+r)/2;
        if(check(mid))
        {
            l=mid;
        }
        else
            r=mid;
    }
    printf("%lld\n",l);
}

River Hopscotch

Description:
Every year the cows hold an event featuring a peculiar version of hopscotch that involves carefully jumping from rock to rock in a river. The excitement takes place on a long, straight river with a rock at the start and another rock at the end, L units away from the start (1 ≤ L ≤ 1,000,000,000). Along the river between the starting and ending rocks, N (0 ≤ N ≤ 50,000) more rocks appear, each at an integral distance Di from the start (0 < Di < L).

To play the game, each cow in turn starts at the starting rock and tries to reach the finish at the ending rock, jumping only from rock to rock. Of course, less agile cows never make it to the final rock, ending up instead in the river.

Farmer John is proud of his cows and watches this event each year. But as time goes by, he tires of watching the timid cows of the other farmers limp across the short distances between rocks placed too closely together. He plans to remove several rocks in order to increase the shortest distance a cow will have to jump to reach the end. He knows he cannot remove the starting and ending rocks, but he calculates that he has enough resources to remove up to M rocks (0 ≤ M ≤ N).

FJ wants to know exactly how much he can increase the shortest distance before he starts removing the rocks. Help Farmer John determine the greatest possible shortest distance a cow has to jump after removing the optimal set of M rocks.

Input
Line 1: Three space-separated integers: L, N, and M
Lines 2.. N+1: Each line contains a single integer indicating how far some rock is away from the starting rock. No two rocks share the same position.
Output
Line 1: A single integer that is the maximum of the shortest distance a cow has to jump after removing M rocks
Sample Input

25 5 2
2
14
11
21
17

Sample Output

4

Hint
Before removing any rocks, the shortest jump was a jump of 2 from 0 (the start) to 2. After removing the rocks at 2 and 14, the shortest required jump is a jump of 4 (from 17 to 21 or from 21 to 25).

Problem solving:
一开始以为这道题用贪心，但是涉及到删除这个操作就很烦。
后来发现者就是一道二分答案的题，套板子就行。
check函数里面判断的条件就是当最小距离已知时，求出它对应的需要拿走石头的值，与输入的进行比较。（一开始直接循环判断样例都不过，后来才想到不能直接判断，因为有可能一次跳两个石头。所以需要这样写

int mid=0,pos=0;
for(int i=1;i<=n+1;i++)
{
    if(a[i]-a[pos]<x)
        mid++;
    else
        pos=i;
}

mid即为当前假设的最小距离所对应的需要拿走的石头个数，然后二分答案就行了。

Code:

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=50005;
int a[maxn];
int l,n,m;
bool check(int x)
{
    int mid=0,pos=0;
    for(int i=1;i<=n+1;i++)
    {
        if(a[i]-a[pos]<x)
            mid++;
        else
            pos=i;
    }
    if(mid>m)    return 0;
    return 1;
}
int main()
{
    cin>>l>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    a[n+1]=l,a[0]=0;
    int l=0,r=1e9,mid;
    while(l<=r)
    {
        mid=(l+r)/2;
        if(check(mid))    l=mid+1;
        else r=mid-1;
    }
    cout<<l-1<<endl;
}