杭电ACM基础题（2139、2143、2148、2153、2156、2161、2162、2164、2186、2192、2200）

2139、Calculate the formula[计算公式]

You just need to calculate the sum of the formula: 1²⁺³2+5^2+……+ n ^2.
Input
In each case, there is an odd positive integer n.
Output
Print the sum. Make sure the sum will not exceed 2^31-1
Sample Input

3

Sample Output

10

Code

/*计算公式1^2^+3^2^+5^2^+......n^2^ 直接用for循环计算会超时for(int i=1;i<=n;i+=2){sum+=i*i;} 利用公式s=n*(n+1)*(n+2)/6; */#include<iostream>
using namespace std;
int main(){
    __int64 n,sum;while(scanf("%I64d",&n)!=EOF){
    sum=n*(n+1)*(n+2)/6;//结果在int类型的范围内，但中间结果不一定在 printf("%I64d\n",sum);//cin cout会超时}return 0;
} 

2143、box[操作符和数]

One day, winnie received a box and a letter. In the letter, there are three integers and five operations(+,-,*,/,%). If one of the three integers can be calculated by the other two integers using any operations only once… He can open that mysterious box. Or that box will never be open.
Input
The input contains several test cases.Each test case consists of three non-negative integers.
Output
If winnie can open that box.print “oh,lucky!”.else print “what a pity!”
Sample Input

1 2 3

Sample Output

oh,lucky!

Code

/* 有五个操作符(+ - * / %)，输入三个非负整数，如果这三个非负整数中的任意一个可以被其他两个整数 使用五个操作符中的任意一个计算一次得到，则输出"oh,lucky!",否则输出"what a pity!" */
#include<iostream>
using namespace std;int f(__int64 a,__int64 b,__int64 c){
    if(b!=0&&c!=0){
    if(a==b+c||a==b-c||a==c-b||a==b*c||a==(double)b/c||a==(double)c/b||a==b%c||a==c%b){
    return 1;}elsereturn 0;}else if(b!=0&&c==0){
    if(a==b||a==-1*b||a==0){
    return 1;}else return 0;}else if(b==0&&c!=0){
    if(a==c||a==-1*c||a==0){
    return 1;}else return 0;}else if(b==0&&c==0){
    if(a==0){
    return 1;}else return 0;}
}int main(){
    __int64 a,b,c;while(cin>>a>>b>>c){
    if(f(a,b,c)||f(b,a,c)||f(c,a,b)){
    cout<<"oh,lucky!"<<endl;}else{
    cout<<"what a pity!"<<endl;}}return 0;
}

2148、Score[班里有多少同学高于该同学]

Lele拿到了全班的成绩单，这张成绩单是按学号顺序排好的。Lele很想知道班里到底有多少人分数比他高，现在就请你帮帮他，帮他数一下到底有多少人的分数比他高吧。
Input
数据的第一行有一个正整数T，表示测试的组数。接下来有T组测试。
每组数据包括两行。
第一行有两个正整数N K(0<N<1000,0<K<=N),分别表示成绩单上一共的学生数目，和Lele的学号。
第二行有N个整数Xi（0<=Xi<=100）分别表示各个学生的成绩，以学号递增顺序给出，第一个学生学号为1。
Output
对于每组数据，请在一行里输出班里一共有多少个学生成绩高于Lele
Sample Input

1
3 2
81 72 63

Sample Output

1

Code

/* 输入该班上同学的数目以及该同学的学号，以及按学号递增的学生的成绩，输出班里有多少同学高于该同学 */
#include<iostream>
using namespace std;
int score[1000];
int main(){
    int t;cin>>t;while(t--){
    int n,k;//n为学生人数，k为学号cin>>n>>k;for(int i=0;i<n;i++){
    cin>>score[i];}int count=0;//学号为k的同学的成绩为score[k-1] for(int i=0;i<n;i++){
    if(score[i]>score[k-1]){
    count++;}}cout<<count<<endl;}return 0;
} 

2153、仙人球的残影[数组模拟]

在美丽的HDU，有一名大三的同学，他的速度是众所周知的，跑100米仅仅用了2秒47，在他跑步过程中会留下残影的哎，大家很想知道他是谁了吧，他叫仙人球，既然名字这样了，于是他的思想是单一的，他总是喜欢从一点出发，经过3次转折（每次向右转90°），回到出发点，而且呢，他每次转折前总是跑相同长度的路程，所以很多人都想知道如果用‘1’算他跑步出发的第一个残影的话，那么回到起点的时候，他的残影是怎么样的呢？
Input
测试数据有多行，每一行为一个数N(1<=N<=10)(以0结尾,0不做处理)，即仙人球在没有回到起点的时候，跑过留下N个残影后突然90°右转。
Output
每组测试数据输出一个结果，并且每个残影的计数位长度为3个字符长度。（当然N等于1的话，它的结果也是占用3个字符位置的）
Sample Input

4

Sample Output

 1  2  3  412        511        610  9  8  7

Code

//按测试数据那样输出即可
#include<iostream>
#include<iomanip>
using namespace std;
int main(){
    int n;while(cin>>n){
    if(n==0) return 0;//规律for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
    //输出第一行 if(i==1){
    cout<<setw(3)<<j; }//输出最后一行 else if(i==n){
    cout<<setw(3)<<3*n-1-j;//设置输出为3个字符长度 }//输出中间几行else if(j==1){
    cout<<setw(3)<<4*n-2-i;} else if(j==n){
    cout<<setw(3)<<n+i-1;}else{
    cout<<" ";}}cout<<endl;} }return 0;
}

2156、分数矩阵[求和]

我们定义如下矩阵:
1/1 1/2 1/3
1/2 1/1 1/2
1/3 1/2 1/1
矩阵对角线上的元素始终是1/1，对角线两边分数的分母逐个递增。
请求出这个矩阵的总和。
Input
每行给定整数N (N<50000)，表示矩阵为 N*N.当N为0时，输入结束。
Output
输出答案，保留2位小数。
Sample Input

1
2
3
4
0

Sample Output

1.00
3.00
5.67
8.83

Code

//计算如下矩阵的和
//n+1/2*(n-1)*2+1/3*(n-2)*2+......1/n*2;
#include<iostream>
#include<iomanip>
using namespace std;
int main(){
    double n;while(cin>>n){
    if(n==0) return 0;double sum=n;for(int i=1;i<n;i++){
    sum+=1/(n+1-i)*i*2;}cout<<setiosflags(ios::fixed)<<setprecision(2)<<sum<<endl;}return 0;
} 

2161、Primes[判断一个数是否为素数]

Write a program to read in a list of integers and determine whether or not each number is prime. A number, n, is prime if its only divisors are 1 and n. For this problem, the numbers 1 and 2 are not considered primes.
Input
Each input line contains a single integer. The list of integers is terminated with a number<= 0. You may assume that the input contains at most 250 numbers and each number is less than or equal to 16000.
Output
The output should consists of one line for every number, where each line first lists the problem number, followed by a colon and space, followed by “yes” or “no”.
Sample Input

1
2
3
4
5
17
0

Sample Output

1: no
2: no
3: yes
4: no
5: yes
6: yes

Code
方法一、

//输入一个数，判断其是否为质数
#include<iostream>
#include<cmath>
using namespace std;
bool isPrime(int n){
    int k=sqrt(n);if(n==1||n==2){
    return false;}for(int i=2;i<=k;i++){
    if(n%i==0)return false;}return true;
}
int main(){
    int n,num=0;while(cin>>n){
    if(n<=0) return 0;num++;if(isPrime(n)==true){
    cout<<num<<": yes"<<endl;}else{
    cout<<num<<": no"<<endl;}}return 0;
} 

方法二
素数筛法

//输入一个数，判断其是否为质数
#include<iostream>
#include<cmath>
using namespace std;
int c[16010]={
    0,0,0,0}; 
int main(){
    int n,num=0;//素数筛法for(int i=2;i<=16000;i++){
    if(c[i]==0){
    for(int k=i*2;k<=16000;k+=i){
    c[k]=1;}}} while(cin>>n){
    if(n<=0) return 0;num++;if(n==1||n==2){
    cout<<num<<": no"<<endl;} else if(c[n]==0){
    cout<<num<<": yes"<<endl;}else{
    cout<<num<<": no"<<endl;}}return 0;
} 

2162、Add ‘em[计算连续的几个整数和]

Write a program to determine the summation of several sets of integers.
Input
The input file will consist of up to 250 sets of integers, where each set contains at most 100 integers and the integer values will be between –16000 and + 16000. Each set of numbers is started with the number of integers in the set, n. The next n input lines will each contain one integer of the set. You should stop processing when the size of the set, n, is<= 0.
Output
A single line of output should be generated for each set of integers. The line should have format shown below.
Sample Input

4
-1
3
1
1
2
19
17
5
-645
952
-1488
-5456
-9342
-1

Sample Output

Sum of #1 is 4
Sum of #2 is 36
Sum of #3 is -15979

Code

//计算连续的几个整数的和
#include<iostream>
using namespace std;
int main(){
    int n,num=0;//每个set中的整数个数 [1,100] while(cin>>n){
    if(n<=0) return 0;num++;int a;//[-16000,16000];int sum=0;for(int i=0;i<n;i++){
    cin>>a;sum+=a;}cout<<"Sum of #"<<num<<" is "<<sum<<endl;}return 0;
} 

2164、Rock, Paper, or Scissors?[石头剪刀布游戏]

Rock, Paper, Scissors is a two player game, where each player simultaneously chooses one of the three items after counting to three. The game typically lasts a pre-determined number of rounds. The player who wins the most rounds wins the game. Given the number of rounds the players will compete, it is your job to determine which player wins after those rounds have been played.

The rules for what item wins are as follows:

?Rock always beats Scissors (Rock crushes Scissors)
?Scissors always beat Paper (Scissors cut Paper)
?Paper always beats Rock (Paper covers Rock)
Input
The first value in the input file will be an integer t (0 < t < 1000) representing the number of test cases in the input file. Following this, on a case by case basis, will be an integer n (0 < n < 100) specifying the number of rounds of Rock, Paper, Scissors played. Next will be n lines, each with either a capital R, P, or S, followed by a space, followed by a capital R, P, or S, followed by a newline. The first letter is Player 1抯 choice; the second letter is Player 2抯 choice.
Output
For each test case, report the name of the player (Player 1 or Player 2) that wins the game, followed by a newline. If the game ends up in a tie, print TIE.
Sample Input

3
2
R P
S R
3
P P
R S
S R
1
P R

Sample Output

Player 2
TIE
Player 1

Code

/* 石头剪刀布游戏：给出两个人玩的圈数以及各自出的状态，输出胜利的人或者平局输出TLE R代表石头 S代表剪刀 P代表布 */
#include<iostream>
using namespace std;
int main(){
    int t;cin>>t;while(t--){
    int n;//玩的圈数cin>>n;char c1,c2; //player1和player2各自出的状态int count1=0,count2=0; for(int i=0;i<n;i++){
    cin>>c1>>c2;if(c1==c2){
    continue;}//player1赢的情况 else if((c1=='R'&&c2=='S')||(c1=='S'&&c2=='P')||(c1=='P'&&c2=='R')){
    count1++;}else if((c2=='R'&&c1=='S')||(c2=='S'&&c1=='P')||(c2=='P'&&c1=='R')){
    count2++;}}if(count1==count2){
    cout<<"TIE"<<endl;}else if(count1<count2){
    cout<<"Player 2"<<endl;}else{
    cout<<"Player 1"<<endl;}}return 0;
} 

2178、猜数字

A有1数m，B来猜.B每猜一次，A就说"太大"，“太小"或"对了” 。
问B猜n次可以猜到的最大数。
Input
第1行是整数T,表示有T组数据，下面有T行
每行一个整数n (1 ≤ n ≤ 30)
Output
猜n次可以猜到的最大数
Sample Input

2
1
3

Sample Output

1
7

Code

/* 猜数字：已知猜的次数n，求猜n次可以猜到的最大的数 最多猜n次一定可以猜到1-m内的任意数字，求m的最大值 公式：2^n-1 */
#include<iostream>
#include<cmath>
using namespace std;
int main(){
    int t,n;cin>>t;while(t--){
    cin>>n;__int64 result=pow(2,n)-1;cout<<result<<endl;}
}

2186、灾后支援组

灾后的救援需要很多的人员，现在又刚刚到达一批志愿者，他们一共有n（10<=n<=1000）人，根据指挥部的指示，他们将被分为抢险、医疗以及通信等3个小分队，并且规定，抢险小分队需要占总人数的一半（如果有小数的话，则舍去），医疗小分队需要占剩余人数的2/3（如果有小数的话，则舍去），剩余的则组成通信小分队。比如一共有55人，那么抢险小分队为55/2=27人，减去抢险小分队为27人剩下28人，则医疗小分队为28*2/3 = 18人，通信小分队为55-27-18=10人。

为了保证救援工作的顺利进行，指挥部决定为每个小分队指派若干当地的向导，原则是为每十个志愿者指派一个向导（如有不足10人的情况，也指派一个），现在请问：需要为这批志愿者指派多少个向导呢？
Input
输入数据首先包含一个正整数C，表示有C组测试用例，然后是C行数据，每行包含一个正整数n(10<=n<=1000)，表示志愿者的总人数。
Output
对于每组测试数据，请输出需要的向导数目，每个输出占一行。
Sample Input

2
14
55

Sample Output

3
6

Code

/* 有n个志愿者，其中抢救小分队需要占总人数的一半，医疗小分队占剩余人数的2/3，通信小分队为剩余的人 并且每个小分队中，每10个人会被指派一名当地的向导，不足10人也指派一个 */
#include<iostream>
using namespace std;
int main(){
    int t;cin>>t;while(t--){
    int n;cin>>n;int rescue,care,talk;rescue=n/2;  care=(n-rescue)*2/3;talk=n-rescue-care;int count=0;//计算志愿者的人数if(rescue%10==0){
    count+=rescue/10;}else{
    count+=rescue/10+1;}if(care%10==0){
    count+=care/10;}else{
    count+=care/10+1;}if(talk%10==0){
    count+=talk/10;}else{
    count+=talk/10+1;}cout<<count<<endl;}
} 

2192、MagicBuilding[建筑物聚集]

As the increase of population, the living space for people is becoming smaller and smaller. In MagicStar the problem is much worse. Dr. Mathematica is trying to save land by clustering buildings and then we call the set of buildings MagicBuilding. Now we can treat the buildings as a square of size d, and the height doesn’t matter. Buildings of d1,d2,d3…dn can be clustered into one MagicBuilding if they satisfy di != dj(i != j).
Given a series of buildings size , you need to calculate the minimal numbers of MagicBuildings that can be made. Note that one building can also be considered as a MagicBuilding.
Suppose there are five buildings : 1, 2, 2, 3, 3. We make three MagicBuildings (1,3), (2,3), (2) .And we can also make two MagicBuilding :(1,2,3), (2,3). There is at least two MagicBuildings obviously.
Input
The first line of the input is a single number t, indicating the number of test cases.
Each test case starts by n (1≤n≤10^4) in a line indicating the number of buildings. Next n positive numbers (less than 2^31) will be the size of the buildings.
Output
For each test case , output a number perline, meaning the minimal number of the MagicBuilding that can be made.
Sample Input

2
1
2 
5
1 2 2 3 3

Sample Output

1
2

Code

/* 告知建筑物的各个size，可以将不同的size的建筑聚集起来形成一个建筑，问最少能够形成多少个建筑 思路：事实上即找到size中出现次数最多的值的个数 */
#include<iostream>
#include<algorithm>
using namespace std;
int size[10000]; 
int main(){
    int t;cin>>t;while(t--){
    int n;//[1,10000];cin>>n;for(int i=0;i<n;i++){
    cin>>size[i];}//寻找出现次数最多的值的数量sort(size,size+n);int a=size[0],count=1,max=1;for(int i=1;i<n;i++){
    if(size[i]==a){
    count++;}else{
    a=size[i];count=1;}if(count>max){
    max=count;}}cout<<max<<endl;}return 0; 
} 

2200、Eddy’s AC难题[排列组合]

Eddy是个ACMer,他不仅喜欢做ACM题,而且对于Ranklist中每个人的ac数量也有一定的研究,他在无聊时经常在纸上把Ranklist上每个人的ac题目的数量摘录下来，然后从中选择一部分人(或者全部)按照ac的数量分成两组进行比较，他想使第一组中的最小ac数大于第二组中的最大ac数，但是这样的情况会有很多，聪明的你知道这样的情况有多少种吗?

特别说明：为了问题的简化，我们这里假设摘录下的人数为n人，而且每个人ac的数量不会相等，最后结果在64位整数范围内.
Input
输入包含多组数据，每组包含一个整数n,表示从Ranklist上摘录的总人数。
Output
对于每个实例，输出符合要求的总的方案数，每个输出占一行。
Sample Input

2
4

Sample Output

1
17

Code

/* 题目：总人数为n，然后从中选择一部分人分成两组进行比较，使得第一组中的最小ac数大于第二组中的最大ac数 这样的情况有多少种。 分析： 总人数为n， 则每次选中的人数为2到n。 若选中人数为2 ，则这2个人的ac数有1种分组方式。 从n个人中选2个人，共有C(n,2)中可能。 若选中人数为3 ，则这3个人的ac数有2种分组方式。 从n个人中选3个人，共有C(n,3)中可能。总数为 2*C(n,3) 若选中人数为4 ，则这4个人的ac数只有3种分组方式。 从n个人中选4个人，共有C(n,4)中可能。总数为3*C(n,4) 若选中人数为n ，则这n个人的ac数有n-1种分组方式。 从n个人中选n个人，共有C(n,n)中可能。(n-1)*C(n,n) */ 
#include<iostream>
using namespace std;//计算C(n,m),完全利用阶乘，特别容易溢出 
//将C(n,m)进行化简，算(n-m+1)*(n-m+2)*…*n / m!,
//此外 为了防止溢出，一边计算 (n-m+1)*(n-m+2)*…*n ，一边除掉1,2,3,...,m中能除的数
__int64 c(__int64 n,__int64 m){
    __int64 result=1,k=1;for(int i=n-m+1;i<=n;i++){
    result=result*i;result=result/k;k++;}return result;
}int main(){
    __int64 n;while(cin>>n){
    __int64 sum=0;for(__int64 i=2;i<=n;i++){
    sum+=(i-1)*c(n,i);}cout<<sum<<endl;}return 0;
}