A. Arpa and a research in Mexican wave
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Arpa is researching the Mexican wave.

There are n spectators in the stadium, labeled from 1 to n. They start the Mexican wave at time 0.

  • At time 1, the first spectator stands.
  • At time 2, the second spectator stands.
  • ...
  • At time k, the k-th spectator stands.
  • At time k + 1, the (k + 1)-th spectator stands and the first spectator sits.
  • At time k + 2, the (k + 2)-th spectator stands and the second spectator sits.
  • ...
  • At time n, the n-th spectator stands and the (n - k)-th spectator sits.
  • At time n + 1, the (n + 1 - k)-th spectator sits.
  • ...
  • At time n + k, the n-th spectator sits.

Arpa wants to know how many spectators are standing at time t.

Input

The first line contains three integers n, k, t (1 ≤ n ≤ 109, 1 ≤ k ≤ n, 1 ≤ t < n + k).

Output

Print single integer: how many spectators are standing at time t.

Examples
input 
10 5 3
output 
3
input 
10 5 7
output 
5
input 
10 5 12
output 
3
Note

In the following a sitting spectator is represented as -, a standing spectator is represented as ^.

  • At t = 0  ----------  number of standing spectators = 0.
  • At t = 1  ^---------  number of standing spectators = 1.
  • At t = 2  ^^--------  number of standing spectators = 2.
  • At t = 3  ^^^-------  number of standing spectators = 3.
  • At t = 4  ^^^^------  number of standing spectators = 4.
  • At t = 5  ^^^^^-----  number of standing spectators = 5.
  • At t = 6  -^^^^^----  number of standing spectators = 5.
  • At t = 7  --^^^^^---  number of standing spectators = 5.
  • At t = 8  ---^^^^^--  number of standing spectators = 5.
  • At t = 9  ----^^^^^-  number of standing spectators = 5.
  • At t = 10 -----^^^^^  number of standing spectators = 5.
  • At t = 11 ------^^^^  number of standing spectators = 4.
  • At t = 12 -------^^^  number of standing spectators = 3.
  • At t = 13 --------^^  number of standing spectators = 2.
  • At t = 14 ---------^  number of standing spectators = 1.
  • At t = 15 ----------  number of standing spectators = 0.

就是分段讨论即可。n+k为一个周期。

#include<bits/stdc++.h>
using namespace std;

int main(){
	long long n , k ,t;
	while(cin>>n>>k>>t){
		if(t>=n+k)t=t-(n+k)*(t/(n+k));
		if(t<=k)
			cout<<t<<endl;
		else if (t>=n)cout<<k-t+n<<endl;
		else
			cout<<k<<endl;
		
	}
	return 0;
}


B. Arpa and an exam about geometry
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Arpa is taking a geometry exam. Here is the last problem of the exam.

You are given three points a, b, c.

Find a point and an angle such that if we rotate the page around the point by the angle, the new position of a is the same as the old position of b, and the new position of b is the same as the old position of c.

Arpa is doubting if the problem has a solution or not (i.e. if there exists a point and an angle satisfying the condition). Help Arpa determine if the question has a solution or not.

Input

The only line contains six integers ax, ay, bx, by, cx, cy (|ax|, |ay|, |bx|, |by|, |cx|, |cy| ≤ 109). It's guaranteed that the points are distinct.

Output

Print "Yes" if the problem has a solution, "No" otherwise.

You can print each letter in any case (upper or lower).

Examples
input 
0 1 1 1 1 0
output 
Yes
input 
1 1 0 0 1000 1000
output 
No
Note

In the first sample test, rotate the page around (0.5, 0.5) by .

In the second sample test, you can't find any solution.


题意就是问是否存在一角度和一个圆心，使得abc绕这个点旋转之后b在a位置，c在b位置。

所以肯定只有当abc是圆弧的一段，并且b是弧abc的中点时候才可以。

所以只需要判断ab=bc，并且abc不共线即可。（不共线可用海伦公式求）

//不知道为啥  我讨论斜率不存在反而多余了- - 不考虑反而过了

#include<bits/stdc++.h>
using namespace std;
#define INF 100861111  
#define ll long long  
#define eps 1e-5  
#define maxn 20  
int main()  
{  
    double x1,y1,x2,y2,x3,y3,k1,k2,d1,d2;  
    scanf("%lf%lf%lf%lf%lf%lf",&x1,&y1,&x2,&y2,&x3,&y3);  
    d1=(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);  
    d2=(x2-x3)*(x2-x3)+(y2-y3)*(y2-y3);  
    if(d1!=d2)  
    {  
        printf("No\n");  
        return 0;  
    }  
    k1=(y1-y2)/(x1-x2);  
    k2=(y2-y3)/(x2-x3);  
    if(k1==k2)  
    {  
        printf("No\n");  
    }  
    else  
        printf("Yes\n");  
    return 0;  
}




C. Five Dimensional Points
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given set of n points in 5-dimensional space. The points are labeled from 1 to n. No two points coincide.

We will call point a bad if there are different points b and c, not equal to a, from the given set such that angle between vectors  and is acute (i.e. strictly less than ). Otherwise, the point is called good.

The angle between vectors  and  in 5-dimensional space is defined as , where  is the scalar product and  is length of .

Given the list of points, print the indices of the good points in ascending order.

Input

The first line of input contains a single integer n (1 ≤ n ≤ 103) — the number of points.

The next n lines of input contain five integers ai, bi, ci, di, ei (|ai|, |bi|, |ci|, |di|, |ei| ≤ 103)  — the coordinates of the i-th point. All points are distinct.

Output

First, print a single integer k — the number of good points.

Then, print k integers, each on their own line — the indices of the good points in ascending order.

Examples
input 
6
0 0 0 0 0
1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
output 
1
1
input 
3
0 0 1 2 0
0 0 9 2 0
0 0 5 9 0
output 
0
Note

In the first sample, the first point forms exactly a  angle with all other pairs of points, so it is good.

In the second sample, along the cd plane, we can see the points look as follows:

We can see that all angles here are acute, so no points are good.

题意：
有n个五维的点，求有多少个“好“点，对于“好”点、“坏”点的定义如下：
“好”点：设该点为a，在所给点中任意两个不相等且不为a的点b,c，向量ab与向量bc的夹角均不为锐角。
“坏”点：不是“好”点的点都是“坏”点

可以从二维三维的方向来考虑，在二维中，一个“好”点的周围最多有4个点（x正负方向两个，y正负方向两个），三维则有6个（加上z方向上两个），可以知道，五维的情况下，一个“好”点周围最多有10个点，加上自身，即图中有“好”点的情况下，最多有11个点，即n>11时不可能存在“好”点，然后n<=11的情况就枚举一下就行了。

#include <bits/stdc++.h>  
  
using namespace std;  
const double pi  = acos(-1.0);  
int arr[1001][5];  
int ans[1001];  
int main()  
{  
    int n;  
    cin>>n;  
    if(n<3)  
    {  
        for(int i = 0;i<n;i++)  
        {  
            int a;  
            scanf("%d%d%d%d%d%d",&a,&a,&a,&a,&a,&a);  
        }  
        printf("%d\n",n);  
        for(int i = 0;i<n;i++)  
            printf("%d\n",i+1);  
    }  
    else  
    {  
        for(int i = 0;i<n;i++)  
        {  
            for(int j = 0;j<5;j++)  
            {  
                scanf("%d",&arr[i][j]);  
            }  
        }  
        int len = 0;  
        for(int i = 0;i<n;i++)  
        {  
            int flag = 0;  
            for(int j = 0;j<n&&flag==0;j++)  
            {  
                if(i==j)  
                    continue;  
                for(int k = 0;k<n&&flag==0;k++)  
                {  
                    if(k==i||k==j)  
                        continue;  
                    double xy = 0,xx = 0,yy = 0;  
                    for(int z = 0;z<5;z++)  
                    {  
                        xx += (arr[j][z]-arr[i][z])*(arr[j][z]-arr[i][z]);  
                        yy += (arr[k][z]-arr[i][z])*(arr[k][z]-arr[i][z]);  
                        xy+=(arr[j][z]-arr[i][z])*(arr[k][z]-arr[i][z]);  
                    }  
                    double s=sqrt(xx)*sqrt(yy);  
                    if(acos(xy/s)>=0&&acos(xy/s)<pi/2)  
                    {  
                        flag = 1;  
                    }  
                }  
            }  
            if(!flag)  
            {  
                ans[len++] = i+1;  
            }  
        }  
        printf("%d\n",len);  
        for(int i = 0;i<len;i++)  
            printf("%d\n",ans[i]);  
    }  
    return 0;  
}