Permutation Bo

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 0 Accepted Submission(s): 0
Special Judge

Problem Description

There are two sequences

h1∼hn and

c1∼cn.

h1∼hn is a permutation of

1∼n. particularly,

h0=hn+1=0.

We define the expression

[condition] is 1 when

condition is True,is 0 when

condition is False.

Define the function

f(h)=∑ni=1ci[hi>hi−1 and hi>hi+1]

Bo have gotten the value of

c1∼cn, and he wants to know the expected value of

f(h).

Input

This problem has multi test cases(no more than

12).

For each test case, the first line contains a non-negative integer

n(1≤n≤1000), second line contains

n non-negative integer

ci(0≤ci≤1000).

Output

For each test cases print a decimal - the expectation of

f(h).

If the absolute error between your answer and the standard answer is no more than

10−4, your solution will be accepted.

Sample Input

  4 3 2 4 5 5 3 5 99 32 12
 

Sample Output

  6.000000 52.833333
 

找规律！！

#include<stdio.h>
#include<cmath>
#include<string.h>
#include<algorithm>

using namespace std;
int n;
int c[1005];


double sum,aver,sum1;

int main()
{ 
	int i,j,k;

	while(scanf("%d",&n)!=EOF)
	{

		memset(c,0,sizeof(c));
		sum1=0;

		for(i=1;i<=n;i++)
		{
			scanf("%d",&c[i]);
			if(i!=1&&i!=n)
				sum1+=c[i];
		}
		
		
		if(n==1)  {
			aver=c[1];
			printf("%lf\n",aver);
		}
		else
		{
			aver=(sum1/3*2+c[1]+c[n])/2;
			printf("%lf\n",aver);		
		}
	}
	return 0;
}

Teacher Bo

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 0 Accepted Submission(s): 0

Problem Description

Teacher BoBo is a geography teacher in the school.One day in his class,he marked

N points in the map,the

i-th point is at

(Xi,Yi).He wonders,whether there is a tetrad

(A,B,C,D)(A<B,C<D,A≠CorB≠D) such that the manhattan distance between A and B is equal to the manhattan distance between C and D.

If there exists such tetrad,print "YES",else print "NO".

Input

First line, an integer

T. There are

T test cases.

(T≤50)

In each test case,the first line contains two intergers, N, M, means the number of points and the range of the coordinates.

(N,M≤105).

Next N lines, the

i-th line shows the coordinate of the

i-th point.

(Xi,Yi)(0≤Xi,Yi≤M).

Output

T lines, each line is "YES" or "NO".

Sample Input

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

Sample Output

  YES NO
 

map实现！

#include<stdio.h>
#include <map>
#include<cmath>
#include<string.h>
#include<string>
#include<algorithm>

using namespace std;
int n;

int c[1005];
typedef struct {
	int x;
	int y;
}NODE;

bool cmp(NODE A,NODE B)
{
	return A.x<B.x&&A.y<B.y;
}

NODE p[100005];

double sum,aver,sum1;

int main()
{ 

	int distance;
	int i,j,k,n,m,i1;
	int T;
	scanf("%d",&T);
	for(i1=0;i1<T;i1++)
	{
	 	map<int, string> my_map;  
		

		memset(p,0,sizeof(p));
		scanf("%d %d",&n,&m);
		for(i=1;i<=n;i++)
		{
			scanf("%d %d",&p[i].x,&p[i].y);
		}
		
		sort(p+1,p+n+1,cmp);
		for(i=2;i<=n;i++)
		{
			for(j=1;j<i;j++) 
			{
				distance=abs(p[i].x-p[j].x)+abs(p[i].y-p[j].y);
				
				map<int, string>::iterator iter;
       			iter = my_map.find(distance);
       			if(iter != my_map.end())
      			{
           			printf("YES\n");
           			goto loop;
       			}
       			my_map.insert(pair<int, string>(distance, "1"));  
			}
		}
		
		printf("NO\n");
		loop :;	
		 
	}
	return 0;
}