计蒜客----训练联盟赛ICPC Yokohama, 2018（Domestic）

admin管理员组

文章数量:1582366

我喜欢给自己压力，必须得定一个很高的目标，逼自己朝着这个目标前进，不管会不会实现，都是一个动力。                                      ----喻言

                                               A. Income Inequality

We often compute the average as the first step in processing statistical data. Yes, the average is a good tendency measure of data, but it is not always the best. In some cases, the average may hinder the understanding of the data.

For example, consider the national income of a country. As the term income inequalitysuggests, a small number of people earn a good portion of the gross national income in many countries. In such cases, the average income computes much higher than the income of the vast majority. It is not appropriate to regard the average as the income of typical people.

Let us observe the above-mentioned phenomenon in some concrete data. Incomes of n people, a_1a1​,a_2a2​

… , a_nan​,are given. You are asked to write a program that reports the number of people whose incomes are less than or equal to the average 

Input

The input consists of multiple datasets, each in the following format.

• n
• a_1a1​,a_2a2​ … a_nan​

A dataset consists of two lines. In the first line, the number of people n is given. n is an integer satisfying 2 ≤ n ≤ 10000. In the second line, incomes of n people are given. a_iai​ (1 ≤ i ≤ n) is the income of the i_{th}ith​ person. This value is an integer greater than or equal to 1 and less than or equal to 100000. The end of the input is indicated by a line containing a zero. The sum of n's of all the datasets does not exceed 50000.

Output

For each dataset, output the number of people whose incomes are less than or equal to the average.

样例输入复制

7
15 15 15 15 15 15 15
4
10 20 30 60
10
1 1 1 1 1 1 1 1 1 100
7
90 90 90 90 90 90 10
7
2 7 1 8 2 8 4
0

样例输出复制

7
3
9
1
4

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <ctime>
#include <cctype>
#include <bitset>
#include <utility>
#include <sstream>
#include <complex>
#include <iomanip>
#include<climits>//INT_MAX
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
const int mod=1e9+7;  
int n,s[10010];
int main(){
	while(cin>>n&&n!=0){
		int ct=0;
		double sum=0,ave;
		for(int i=0;i<n;i++){
			cin>>s[i];
			sum+=s[i];
		}
		ave=sum*1.0/n;
		for(int i=0;i<n;i++)
			if(s[i]<=ave)
				ct++;
		cout<<ct<<endl;
	}
	return 0;
} 

                                      B. Origami, or the art of folding paper

Master Grus is a famous origami (paper folding) artist, who is enthusiastic about exploring the possibility of origami art. For future creation, he is now planning fundamental experiments to establish the general theory of origami.One rectangular piece of paper is used in each of his experiments. He folds it horizontally and/or vertically several times and then punches through holes in the folded paper.The following figure illustrates the folding process of a simple experiment, which corresponds to the third data test of the Sample Input below. Folding the 10 × 8 rectangular piece of paper shown at top left three times results in the 6 × 6 square shape shown at bottom left. In the figure, dashed lines indicate the locations to fold the paper and round arrows indicate the directions of folding. Grid lines are shown as solid lines to tell the sizes of rectangular shapes and the exact locations of folding. Color densities represent the numbers of overlapping layers. Punching through holes at A and B in the folded paper makes nine holes in the paper, eight at A and another at B.

Your mission in this problem is to write a computer program to count the number of holes in the paper, given the information on a rectangular piece of paper and folding and punching instructions.

Input

The input consists of at most 1000 data tests, each in the following format.

• nn mm tt pp
• d_1d1​ c_1c1​
• ...
• d_tdt​ c_tct​
• x_1x1​ y_1y1​
• ...
• x_pxp​ y_pyp​

n and m are the width and the height, respectively, of a rectangular piece of paper. They are positive integers at most 32. tt and ppare the numbers of folding and punching instructions, respectively. They are positive integers at most 20. The pair of d_idi​ and c_ici​ gives the i_tit​_hh​ folding instruction as follows:

• d_idi​ is either 1 or 2.
• c_ici​ is a positive integer.
• If d_idi​ is 1, the left-hand side of the vertical folding line that passes at c_ici​ right to the left boundary is folded onto the right-hand side.
• If d_idi​ is 2, the lower side of the horizontal folding line that passes at c_ici​ above the lower boundary is folded onto the upper side.

After performing the first i−1 folding instructions, if d_idi​ is 1, the width of the shape is greater than c_ici​. Otherwise the height is greater than c_ici​. (x_ixi​ + 1\over{2}21​, y_iyi​ + 1\over{2}21​) gives the coordinates of the point where the i_tit​_hh​ punching instruction is performed. The origin (0, 0) is at the bottom left of the finally obtained shape. x_ixi​ and y_iyi​ are both non-negative integers and they are less than the width and the height, respectively, of the shape. You can assume that no two punching instructions punch holes at the same location.

The end of the input is indicated by a line containing four zeros.

Output

For each data test, output pp lines, the i_tit​_hh​ of which contains the number of holes punched in the paper by the i_tit​_hh​ punching instruction.

样例输入复制

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

样例输出复制

2
3
8
1
3
6

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <ctime>
#include <cctype>
#include <bitset>
#include <utility>
#include <sstream>
#include <complex>
#include <iomanip>
#include<climits>//INT_MAX
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
const int mod=1e9+7;  
ll fx[10010],fy[10010];
int n,m,t,p,u,v;
int main()
{
	while(scanf("%d%d%d%d",&n,&m,&t,&p)!=EOF&&n!=0){
		memset(fx,0,sizeof(fx));
		memset(fy,0,sizeof(fy));
		for(int i=0;i<n;i++)
			fx[i]=1;
		for(int i=0;i<m;i++)
			fy[i]=1;
		int x=0,y=0;
		while(t--){
			scanf("%d%d",&u,&v);
			if(u==1){
				for(int i=0;i<v;i++)
					fx[x+v*2-i-1]+=fx[x+i];
				x+=v;
			}
			else{
				for(int i=0;i<v;i++)
					fy[y+v*2-i-1]+=fy[y+i];
				y+=v;
			}
		}
		while(p--){
			scanf("%d%d",&u,&v);
			printf("%lld\n",fx[x+u]*fy[y+v]);
		}
	}
	return 0;
}

                                        C. Skyscraper “MinatoHarukas ”

Mr. Port plans to start a new business renting one or more floors of the new skyscraper with one giga floors, MinatoHarukas. He wants to rent as many vertically adjacent floors as possible, because he wants to show advertisement on as many vertically adjacent windows as possible. The rent for one floor is proportional to the floor number, that is, the rent per month for the n-th floor is n times that of the first floor. Here, the ground floor is called the first floor in the American style, and basement floors are out of consideration for the renting. In order to help Mr. Port, you should write a program that computes the vertically adjacent floors satisfying his requirement and whose total rental cost per month is exactly equal to his budget.For example, when his budget is 15 units, with one unit being the rent of the first floor, there are four possible rent plans, 1+2+3+4+5, 4+5+6, 7+8, and 15. For all of them, the sums are equal to 15. Of course in this example the rent of maximal number of the floors is that of 1+2+3+4+5, that is, the rent from the first floor to the fifth floor.

Input

The input consists of multiple datasets, each in the following format.

• b

A dataset consists of one line, the budget of Mr. Port b as multiples of the rent of the first floor. b is a positive integer satisfying 1 < b < 10^9109. The end of the input is indicated by a line containing a zero. The number of datasets does not exceed 1000.

Output

For each dataset, output a single line containing two positive integers representing the plan with the maximal number of vertically adjacent floors with its rent price exactly equal to the budget of Mr. Port. The first should be the lowest floor number and the second should be the number of floors.

样例输入复制

15
16
2
3
9699690
223092870
847288609
900660121
987698769
999999999
0

样例输出复制

1 5
16 1
2 1
1 2
16 4389
129 20995
4112949 206
15006 30011
46887 17718
163837 5994

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <ctime>
#include <cctype>
#include <bitset>
#include <utility>
#include <sstream>
#include <complex>
#include <iomanip>
#include<climits>//INT_MAX
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
const int mod=1e9+7;  
ll b;
int main(){
	while(cin>>b&&b!=0){
		int ct=0,ls;
		for(int i=50000;i>0;i--){
			if(2*b%i==0&&(2*b/i-i+1)%2==0&&2*b/i-i+1>=2){
				ls=(2*b/i-i+1)/2;
				ct=i;
				break;
			}
		}
		cout<<ls<<' '<<ct<<endl;
	}
	return 0;
} 

 

本文标签： 联盟ICPC计蒜客DomesticYokohama