2018年HPUACM暑期集训招新赛

我就是我 2022-05-21 06:17 169阅读 0赞

## [A - 青年歌手大奖赛\_评委会打分][A -] ##

#### 青年歌手大奖赛\_评委会打分 ####

**Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)  
Total Submission(s): 104819 Accepted Submission(s): 51776**

Problem Description

青年歌手大奖赛中，评委会给参赛选手打分。选手得分规则为去掉一个最高分和一个最低分，然后计算平均得分，请编程输出某选手的得分。

Input

输入数据有多组，每组占一行，每行的第一个数是n(2<n<=100)，表示评委的人数，然后是n个评委的打分。

Output

对于每组输入数据，输出选手的得分，结果保留2位小数，每组输出占一行。

Sample Input

3 99 98 974 100 99 98 97

Sample Output

98.0098.50

Author

lcy

**注意一下数据类型为浮点型就好了**

#include<cstdio>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    const int maxn=1e3+6;
    double a[maxn];
    int main()
    {
    	int n;
    	while(~scanf("%d",&n))
    	{
    		for(int i=0;i<n;i++)
    			scanf("%lf",a+i);
    		sort(a,a+n);
    		double sum=0;
    		for(int i=1;i<n-1;i++)
    			sum+=a[i];
    		printf("%.2f\n",sum/(n-2));
    	}
    	return 0;
    }

## [B - 偶数求和][B -] ##

<table> 
 <tbody> 
  <tr> 
   <td><h5><br></h5> 
    <div> 
    </div></td> 
  </tr> 
  <tr> 
   <td align="center"><h1 style="color:#1a5cc8;"><span style="font-size:16px;">偶数求和</span></h1><strong><span style="font-size:12px;font-family:Arial;color:#008000;">Time Limit: 2000/1000 MS (Java/Others)&nbsp;&nbsp;&nbsp;&nbsp;Memory Limit: 65536/32768 K (Java/Others)<br>Total Submission(s): 106685&nbsp;&nbsp;&nbsp;&nbsp;Accepted Submission(s): 44357<br></span></strong><br><br> 
    <div>
      Problem Description 
    </div> 
    <div>
      有一个长度为n(n&lt;=100)的数列，该数列定义为从2开始的递增有序偶数，现在要求你按照顺序每m个数求出一个平均值，如果最后不足m个，则以实际数量求平均值。编程输出该平均值序列。 
    </div> 
    <div>
      &nbsp; 
    </div><br> 
    <div>
      Input 
    </div> 
    <div>
      输入数据有多组，每组占一行，包含两个正整数n和m，n和m的含义如上所述。 
     <br> 
    </div> 
    <div>
      &nbsp; 
    </div><br> 
    <div>
      Output 
    </div> 
    <div>
      对于每组输入数据，输出一个平均值序列，每组输出占一行。 
     <br> 
    </div> 
    <div>
      &nbsp; 
    </div><br> 
    <div>
      Sample Input 
    </div> 
    <div> 
     <pre></pre> 
     <div style="font-family:'Courier New', Courier, monospace;">
       3 24 2 
     </div> 
    </div> 
    <div>
      &nbsp; 
    </div> 
    <div>
      Sample Output 
    </div> 
    <div> 
     <pre></pre> 
     <div style="font-family:'Courier New', Courier, monospace;">
       3 63 7 
     </div> 
    </div> 
    <div>
      &nbsp; 
    </div></td> 
  </tr> 
 </tbody> 
</table>

**细心一点儿就好了**

#include<cstdio>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    const int maxn=1e5+6;
    int a[120];
    
    int main()
    {
    	for(int i=0;i<102;i++)
    		a[i]=i*2;
    	int n,m,sum;
    	while(~scanf("%d %d",&n,&m))
    	{
    		
    		for(int i=0;i<n/m;i++) 
    		{
    			sum=0;
    			for(int j=i*m+1;j<=m*(i+1);j++)
    			{
    				sum+=a[j];
    			} 
    			if(i)	printf(" ");
    			printf("%d",sum/m);
    		}		
    		if(n%m)
    		{
    			sum=0;
    			int x=n-(n/m)*m;
    			for(int i=m*(n/m)+1;i<=n;i++)
    				sum+=a[i];
    			printf(" %d",sum/x);
    		}
    		printf("\n");
    	}
    	return 0;
    }

[C - 三角形][C -]

# 三角形 #

**Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)  
Total Submission(s): 108913 Accepted Submission(s): 35707**

Problem Description

给定三条边，请你判断一下能不能组成一个三角形。

Input

输入数据第一行包含一个数M，接下有M行，每行一个实例，包含三个正数A,B,C。其中A,B,C <1000;

Output

对于每个测试实例，如果三条边长A,B,C能组成三角形的话，输出YES，否则NO。

Sample Input

21 2 32 2 2

Sample Output

NOYES

Author

linle

**水题，注意一下数据范围是实数**

#include<cstdio>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    const int maxn=1e3+6;
    
    int main()
    {
    	double a,b,c;
    	int t;
    	scanf("%d",&t);
    	while(t--)
    	{
    		scanf("%lf %lf %lf",&a,&b,&c);
    		double x=max(a,max(b,c));
    		if(x<(a+b+c-x))	printf("YES\n");
    		else			printf("NO\n");
    	}
    	return 0;
    }

[D - Text Volume][]

A. Text Volume

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given a text of single-space separated words, consisting of small and capital Latin letters.

*Volume* of the word is number of capital letters in the word. *Volume* of the text is maximum *volume* of all words in the text.

Calculate the *volume* of the given text.

Input

The first line contains one integer number *n* (1 ≤ *n* ≤ 200) — length of the text.

The second line contains text of single-space separated words *s*1, *s*2, ..., *s**i*, consisting only of small and capital Latin letters.

Output

Print one integer number — *volume* of text.

Examples

input

Copy

7
    NonZERO

output

Copy

input

Copy

24
    this is zero answer text

output

Copy

input

Copy

24
    Harbour Space University

output

Copy

给你一行短文, 由单个空格分开的一些单词组成,仅包含大写字母和小写字母.  
  
  
单词的Volume代表: 这个单词中大写字母的个数  
  
  
短文的Volume等于该短文包含的所有单词的Volume的最大值  
  
  
你的目标是计算给定短文的Volume.  
  
  
Input  
第一行包含一个整数n (1 ≤ n ≤ 200) — 代表短文的长度.  
  
  
第二行包含一行短文,由单个空格分开的一些单词s1, s2, ..., si组成,由大写字母和小写字母组成.  
  
  
Output

输出一个整数 — 该短文的Volume.

#include<cstdio>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    const int maxn=1e3+6;
    char s[maxn];
    int main()
    {
    	int n;
    	scanf("%d",&n);
    	getchar();//吸收回车符 
    	gets(s);
    	int v=0;//记录单词的Volume 
    	int ans=0;//记录短文的Volume 
    	for(int i=0;i<n;i++)
    	{
    		if(s[i]==' ')
    		{
    			ans=max(ans,v);
    			v=0;
    		}
    		if(s[i]>='A'&&s[i]<='Z')	v++;
    	 } 
    	 ans=max(ans,v);
    	 printf("%d\n",ans);
    	return 0;
    }

[E - Digit Sums][]

## Digit Sums ##

--------------------

Time limit : 2sec / Memory limit : 1024MB

Score : 200 points

### Problem Statement ###

Let *S*(*n*) denote the sum of the digits in the decimal notation of *n*. For example, *S*(101)=1+0+1=2.

Given an integer *N*, determine if *S*(*N*) divides *N*.

### Constraints ###

*  1≤*N*≤109

--------------------

### Input ###

Input is given from Standard Input in the following format:

### Output ###

If *S*(*N*) divides *N*, print `Yes`; if it does not, print `No`.

--------------------

### Sample Input 1 ###

Copy

### Sample Output 1 ###

Copy

Yes

In this input, *N*=12. As *S*(12)=1+2=3, *S*(*N*) divides *N*.

--------------------

### Sample Input 2 ###

Copy

101

### Sample Output 2 ###

Copy

As *S*(101)=1+0+1=2, *S*(*N*) does not divide *N*.

--------------------

### Sample Input 3 ###

Copy

999999999

### Sample Output 3 ###

Copy

Yes

令S(N) : 十进制表示法中，N 的各位数字相加之和. 例如, S(101) = 1 + 0 + 1 = 2.  
  
  
给你一个整数 N, 判断 S(N) 能否整除 N .  
  
  
Constraints  
1 <= N <= 10^9  
  
  
Input  
输入仅一行，一个整数N  
  
  
Output  
如果 S(N) 能整除 N, 输出 Yes; 否则, 输出 No.

**根据题意直接做就行了**

#include<cstdio>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    const int maxn=1e3+6;
    
    
    int s(int n)
    {
    	int ans=0;
    	while(n)
    	{
    		ans+=n%10;
    		n/=10;
    	}
    	return ans;
    }
    
    int main()
    {
    	int n;
    	while(~scanf("%d",&n))
    	{
    		if(n%s(n))	printf("No\n");
    		else		printf("Yes\n");
    	}
    	return 0;
    }

[F - Generous Kefa][]

Generous Kefa

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

One day Kefa found *n* baloons. For convenience, we denote color of *i*\-th baloon as *s**i* — lowercase letter of the Latin alphabet. Also Kefa has *k* friends. Friend will be upset, If he get two baloons of the same color. Kefa want to give out **all** baloons to his friends. Help Kefa to find out, can he give out all his baloons, such that no one of his friens will be upset — print «YES», if he can, and «NO», otherwise. Note, that Kefa's friend will not upset, if he doesn't get baloons at all.

Input

The first line contains two integers *n* and *k* (1 ≤ *n*, *k* ≤ 100) — the number of baloons and friends.

Next line contains string *s* — colors of baloons.

Output

Answer to the task — «YES» or «NO» in a single line.

You can choose the case (lower or upper) for each letter arbitrary.

Examples

input

Copy

4 2
    aabb

output

Copy

YES

input

Copy

6 3
    aacaab

output

Copy

Note

In the first sample Kefa can give 1\-st and 3\-rd baloon to the first friend, and 2\-nd and 4\-th to the second.

In the second sample Kefa needs to give to all his friends baloons of color *a*, but one baloon will stay, thats why answer is «NO».

**别想太多......**

#include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    const int maxn=1e5+6;
    int a[100];
    bool cmp(int x,int y)
    {
    	return x>y;
    }
    int main()
    {
    	int n,m;
    	while(~scanf("%d %d",&n,&m))
    	{
    		memset(a,0,sizeof(a));
    		char s[maxn];
    		scanf("%s",s);
    		for(int i=0;i<strlen(s);i++)
    			a[s[i]-'A']++;
    		sort(a,a+100,cmp);
    		if(a[0]>m)	printf("NO\n");
    		else		printf("YES\n");
    	}
    	return 0;
    }

# [G - Godsend][] #

Godsend

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Leha somehow found an array consisting of *n* integers. Looking at it, he came up with a task. Two players play the game on the array. Players move one by one. The first player can choose for his move a subsegment of non-zero length with an odd sum of numbers and remove it from the array, after that the remaining parts are glued together into one array and the game continues. The second player can choose a subsegment of non-zero length with an even sum and remove it. Loses the one who can not make a move. Who will win if both play optimally?

Input

First line of input data contains single integer *n* (1 ≤ *n* ≤ 106) — length of the array.

Next line contains *n* integers *a*1, *a*2, ..., *a**n* (0 ≤ *a**i* ≤ 109).

Output

Output answer in single line. "First", if first player wins, and "Second" otherwise (without quotes).

Examples

input

Copy

4
    1 3 2 3

output

Copy

First

input

Copy

2
    2 2

output

Copy

Second

Note

In first sample first player remove whole array in one move and win.

In second sample first player can't make a move and lose.

![70][]

#include<cstdio>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    const int maxn=1e3+6;
    
    
    int main()
    {
    	int n;
    	while(~scanf("%d",&n))
    	{
    		ll sum=0;
    		int k=0;
    		for(int i=0;i<n;i++)
    		{
    			int x;
    			scanf("%d",&x);
    			sum+=x;
    			if(x&1)	k=1;
    		}
    		if(sum&1)	printf("First\n");
    		else if(k)	printf("First\n");
    		else		printf("Second\n");
    	}
    	return 0;
    }

# [H - Sorting Railway Cars][] #

Sorting Railway Cars

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

An infinitely long railway has a train consisting of *n* cars, numbered from 1 to *n* (the numbers of all the cars are distinct) and positioned in arbitrary order. David Blaine wants to sort the railway cars in the order of increasing numbers. In one move he can make one of the cars disappear from its place and teleport it either to the beginning of the train, or to the end of the train, at his desire. What is the minimum number of actions David Blaine needs to perform in order to sort the train?

Input

The first line of the input contains integer *n* (1 ≤ *n* ≤ 100 000) — the number of cars in the train.

The second line contains *n* integers *p**i* (1 ≤ *p**i* ≤ *n*, *p**i* ≠ *p**j* if *i* ≠ *j*) — the sequence of the numbers of the cars in the train.

Output

Print a single integer — the minimum number of actions needed to sort the railway cars.

Examples

input

Copy

5
    4 1 2 5 3

output

Copy

input

Copy

4
    4 1 3 2

output

Copy

Note

In the first sample you need first to teleport the 4\-th car, and then the 5\-th car to the end of the train.

**这一题是要找最长的连续递增子序列，自己想了好久没想出来，竞赛结束后看了网上大佬们写的代码，发现原来是这样做的，**

#include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<iostream>
    using namespace  std;
    const int maxn=1e5+6;
    typedef long long ll;
    int a[maxn];
    int main()
    {
    	int n;
    	while(~scanf("%d",&n))
    	{
    		int k;
    		int ans=0;
    		memset(a,0,sizeof(a));
    		for(int i=0;i<n;i++)
    		{
    			scanf("%d",&k);
    			if(a[k-1])
    			{
    				a[k]=a[k-1]+1;
    			}
    			else
    				a[k]=1;
    			ans=max(ans,a[k]);
    		 } 
    		printf("%d\n",n-ans);
    	}
    	return 0;
    }

[A -]: https://cn.vjudge.net/problem/HDU-2014
[B -]: https://cn.vjudge.net/problem/HDU-2015
[C -]: https://cn.vjudge.net/problem/HDU-2039
[D - Text Volume]: https://cn.vjudge.net/problem/CodeForces-837A
[E - Digit Sums]: https://cn.vjudge.net/problem/AtCoder-4159
[F - Generous Kefa]: https://cn.vjudge.net/problem/CodeForces-841A
[G - Godsend]: https://cn.vjudge.net/problem/CodeForces-841B
[70]: /images/20220521/e30e713bc43f455b8fbb0ed068f14d77.png
[H - Sorting Railway Cars]: https://cn.vjudge.net/problem/CodeForces-606C