### 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:

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:

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:

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

x /= 5;
}
return ans;
}

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:

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

1、当箭的伤害值大于等于兔子的血量时，就能将兔子杀死；
2、血量Bi，箭的伤害值Di，箭的价格Pi，均小于等于100000。
Output

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:

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-yx (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:

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:

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<a,b> that |x[b]−x[a]|≤k.(a<b)
Input
The first line contains a single integer T (about 5), indicating the number of cases.
Each test case begins with two integers n,k(1≤n≤100000,1≤k≤1e9).
Next n lines contain an integer xi(−1e9≤x[i]≤1e9), means the X coordinates.
Output
For each case, output an integer means how many pairs<a,b> 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:

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;
}
}

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:

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:

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;
}