杭电ACM基础题（2201、2212、2304、2309、2317、2401、2500、2502、2503、1708、1161）

2201、熊猫阿波的故事[概率问题]

凡看过功夫熊猫这部电影的人都会对影片中那只憨憨的熊猫阿波留下相当深的印象。一日，阿波收到了一张请柬，请柬里说在遥远的美国将召开全球比武大会，特邀请阿波过去做嘉宾。阿波当然很高兴，因为自己长这么大都还没出过和平谷，更何况是出国去那遥远的美国。于是他托人买了当晚的机票，阿波来到机场发现其他乘客们正准备按机票上的号码(1,2,3,…,n)依次排队上飞机，由于阿波是第一次坐飞机，所以他想先一步登机，因此他插队第一个登上了飞机，并且他也不看机票，随机的选择了一个座位坐下了。乘客们都很气氛，他们想：既然阿波都不遵守规定，那么我为什么要遵守呢？因此后面所有的人也都随意地找了位置坐下来，并且坚决不让座给其他的乘客。
现在的问题是这样的：在这样的情况下，第i个乘客(除去熊猫阿波外)坐到原机票位置的概率是多少?
Input
输入包含多组测试数据，每组数据占一行，包含两个整数，分别是n和m(n>=m)，n表示共有n个乘客(包括阿波)，m表示第m个乘客。
Output
对于每组数据，请输出第m个乘客(除去熊猫阿波外)坐到原机票位置的概率是多少?(结果保留2位小数)
每组输出占一行。
Sample Input

2 1
11 3

Sample Output

0.50
0.09

Code

/*关于概率的问题： n位乘客中，第m位坐到正确位置的概率 如： 有11个乘客，第3位坐到正确的位置的概率--首先为了使第三个乘客坐到正确的位置，熊猫坐位置的概率为10/11;第一个乘客选择一个位置的概率为9/10；第二个乘客选择一个位置的概率是8/9；第三个乘客坐到正确位置的概率为1/8；其乘积便是11位乘客中，第3位坐到正确位置的概率：10/11*9/10*8/9*1/8= 1/11; */ 
#include<iostream>
#include<iomanip>
using namespace std;
int main(){
    int n,m;while(cin>>n>>m){
    cout<<setiosflags(ios::fixed)<<setprecision(2)<<1.0/n<<endl;}
}

2212、DFS[各位数的阶乘之和等于该数]

A DFS(digital factorial sum) number is found by summing the factorial of every digit of a positive integer.

For example ,consider the positive integer 145 = 1!+4!+5!, so it’s a DFS number.

Now you should find out all the DFS numbers in the range of int( [1, 2147483647] ).

There is no input for this problem. Output all the DFS numbers in increasing order. The first 2 lines of the output are shown below.
Input
no input
Output
Output all the DFS number in increasing order.
Sample Output

1
2
......

Code

/*找出[1,2147483647]范围内所有的DFS数 DFS数定义：各位数的阶乘之和等于该数，如145=1！+4！+5！; */ 
#include <iostream>
using namespace std;
/* int factorial(int n){int result=1;for(int i=n;i>=1;i--){result*=i;}return result; }*/int main(){
    /*for(int i=1;i<=2147483647;i++){int sum=0,a=i,temp;while(a!=0){temp=a%10;sum+=factorial(temp);//计算阶乘 if(sum>i){break;}a=a/10;}if(sum==i){cout<<i<<endl;}}*/cout<<1<<endl;cout<<2<<endl;cout<<145<<endl;cout<<40585<<endl;return 0;
}

2304、Electrical Outlets[电源板接口]

Roy has just moved into a new apartment. Well, actually the apartment itself is not very new, even dating back to the days before people had electricity in their houses. Because of this, Roy’s apartment has only one single wall outlet, so Roy can only power one of his electrical appliances at a time.
Roy likes to watch TV as he works on his computer, and to listen to his HiFi system (on high volume) while he vacuums, so using just the single outlet is not an option. Actually, he wants to have all his appliances connected to a powered outlet, all the time. The answer, of course, is power strips, and Roy has some old ones that he used in his old apartment. However, that apartment had many more wall outlets, so he is not sure whether his power strips will provide him with enough outlets now.Your task is to help Roy compute how many appliances he can provide with electricity, given a set of power strips. Note that without any power strips, Roy can power one single appliance through the wall outlet. Also, remember that a power strip has to be powered itself to be of any use.
Input
Input will start with a single integer 1 <= N <= 20, indicating the number of test cases to follow. Then follow N lines, each describing a test case. Each test case starts with an integer 1 <= K <= 10, indicating the number of power strips in the test case. Then follow, on the same line, K integers separated by single spaces, O1 O2 . . . OK, where 2 <= Oi <= 10, indicating the number of outlets in each power strip.
Output
Output one line per test case, with the maximum number of appliances that can be powered.
Sample Input

3
3 2 3 4
10 4 4 4 4 4 4 4 4 4 4
4 10 10 10 10

Sample Output

7
31
37

Code

/* 已知墙上只有一个外接电源的接口，有n个电源板，每个电源板的接口有O1,O2...On个,问这些电源板最多能够结多少电器？ 思路：n个电源板的接口有sum=O1+O2+...On个，但相互之间的连接会占用（n-1个接口）故最多剩下 sum-（n-1）个； */
#include<iostream>
using namespace std;
int main(){
    int t;cin>>t;while(t--){
    int n,sum=0,out;cin>>n;for(int i=0;i<n;i++){
    cin>>out;sum+=out; }cout<<sum-n+1<<endl;}return 0;
} 

2309、ICPC Score Totalizer Software[去掉一个最高分，去掉一个最低分的最终得分]

The International Clown and Pierrot Competition (ICPC), is one of the most distinguished and also the most popular events on earth in the show business.
One of the unique features of this contest is the great number of judges that sometimes counts up to one hundred. The number of judges may differ from one contestant to another, because judges with any relationship whatsoever with a specific contestant are temporarily excluded for scoring his/her performance.

Basically, scores given to a contestant’s performance by the judges are averaged to decide his/her score. To avoid letting judges with eccentric viewpoints too much influence the score, the highest and the lowest scores are set aside in this calculation. If the same highest score is marked by two or more judges, only one of them is ignored. The same is with the lowest score. The average, which may contain fractions, are truncated down to obtain final score as an integer.

You are asked to write a program that computes the scores of performances, given the scores of all the judges, to speed up the event to be suited for a TV program.
Input
The input consists of a number of datasets, each corresponding to a contestant’s performance. There are no more than 20 datasets in the input.

A dataset begins with a line with an integer n, the number of judges participated in scoring the performance (3 ≤ n ≤ 100). Each of the n lines following it has an integral score s (0 ≤ s ≤ 1000) marked by a judge. No other characters except for digits to express these numbers are in the input. Judges’ names are kept secret.

The end of the input is indicated by a line with a single zero in it.
Output
For each dataset, a line containing a single decimal integer indicating the score for the corresponding performance should be output. No other characters should be on the output line.
Sample Input

3
1000
342
0
5
2
2
9
11
932
5
300
1000
0
200
400
8
353
242
402
274
283
132
402
523
0

Sample Output

342
7
300
326

Code

//给出裁判的打分情况，去掉一个最高分，去掉一个最低分，计算该同学的最终得分、
#include<iostream>
#include<algorithm>
using namespace std;
int score[100]={
    0};
int main(){
    int n;//裁判人数[3,100]while(cin>>n){
    if(n==0) return 0;for(int i=0;i<n;i++){
    cin>>score[i];}sort(score,score+n);int sum=0;for(int k=1;k<n-1;k++){
    sum+=score[k];}int aver;aver=sum/(n-2);cout<<aver<<endl;} 
} 

2317、Nasty Hacks[广告宣传与不进行广告的收入比较]

You are the CEO of Nasty Hacks Inc., a company that creates small pieces of malicious software which teenagers may use
to fool their friends. The company has just finished their first product and it is time to sell it. You want to make as much money as possible and consider advertising in order to increase sales. You get an analyst to predict the expected revenue, both with and without advertising. You now want to make a decision as to whether you should advertise or not, given the expected revenues.

Input
The input consists of n cases, and the first line consists of one positive integer giving n. The next n lines each contain 3 integers, r, e and c. The first, r, is the expected revenue if you do not advertise, the second, e, is the expected revenue if you do advertise, and the third, c, is the cost of advertising. You can assume that the input will follow these restrictions: -106 ≤ r, e ≤ 106 and 0 ≤ c ≤ 106.

Output
Output one line for each test case: “advertise”, “do not advertise” or “does not matter”, presenting whether it is most profitable to advertise or not, or whether it does not make any difference.

Sample Input

3
0 100 70
100 130 30
-100 -70 40

Sample Output

advertise
does not matter
do not advertise

Code

//题目：已知不打广告的收入为r,打广告的预期收入为e,打广告的成本为c，判断是否要打广告
#include<iostream>
using namespace std;
int main(){
    int t;cin>>t;while(t--){
    int r,e,c;cin>>r>>e>>c;if(r>(e-c)){
    cout<<"do not advertise"<<endl;}else if(r==(e-c)){
    cout<<"does not matter"<<endl;}else{
    cout<<"advertise"<<endl;}}return 0;
} 

2401、Baskets of Gold Coins[金币的重量]

You are given N baskets of gold coins. The baskets are numbered from 1 to N. In all except one of the baskets, each gold coin weighs w grams. In the one exceptional basket, each gold coin weighs w-d grams. A wizard appears on the scene and takes 1 coin from Basket 1, 2 coins from Basket 2, and so on, up to and including N-1 coins from Basket N-1. He does not take any coins from Basket N. He weighs the selected coins and concludes which of the N baskets contains the lighter coins. Your mission is to emulate the wizard’s computation.
Input
The input file will consist of one or more lines; each line will contain data for one instance of the problem. More specifically, each line will contain four positive integers, separated by one blank space. The first three integers are, respectively, the numbers N, w, and d, as described above. The fourth integer is the result of weighing the selected coins.

N will be at least 2 and not more than 8000. The value of w will be at most 30. The value of d will be less than w.
Output
For each instance of the problem, your program will produce one line of output, consisting of one positive integer: the number of the basket that contains lighter coins than the other baskets.
Sample Input

10 25 8 1109
10 25 8 1045
8000 30 12 959879400

Sample Output

2
10
50

Code

/* 有1-N篮子的金币，每个篮子中有很多金币， 除了一个特殊的篮子中的每个金币重w-d克，其余篮子中的金币重w克 现从第一个篮子中取一个金币，第二个篮子取两个金币....依次，第N个篮子不取金币，已知取出的金币的重量， 问第几个篮子中放着比较轻的金币 思路：n个篮子，则取出的金币的数量为sum=1+2+...(n-1)=n*(n-1)/2;若所有的金币均为重的金币，则总的重量sum*w;现在已称出的重量为weight,则若(sum*w-weight)为差值 则light=(sum*w-weight)/d，light=0，则轻金币在第n号篮子中，light=m，则轻金币在第m个篮子 */
#include <iostream>
using namespace std;
int main(){
    int n,w,d,s;while(cin>>n>>w>>d>>s){
    int m=(w*n*(n-1)/2-s)/d;if(m==0){
    cout<<n<<endl;}elsecout<<m<<endl;} return 0;
} 

2500、输出指定大小的方形字符串

本题是要求输出指定大小的"HDU"字符串，特别地，为了体现“正气”二字，我们要求输出的字符串也是正方形的（行数和列数相等）。
Input
输入的第一行包含一个正整数N（N<=20），表示一共有N组数据，接着是N行数据，每行包含一个正整数M（M<=50），表示一行内有M个“HDU”相连。
Output
输出指定大小的方形字符串，输出格式参见样本数据。
Sample Input

2
1
2

Sample Output

HDU
HDU
HDU
HDUHDU
HDUHDU
HDUHDU
HDUHDU
HDUHDU
HDUHDU

Code

//输出指定大小的方形字符串
#include<iostream>
using namespace std;
int main(){
    char c[4]="HDU"; int t;cin>>t;while(t--){
    int n;cin>>n;for(int i=0;i<n*3;i++){
    for(int j=0;j<n*3;j++){
    cout<<c[j%3];}cout<<endl;}}return 0;
} 

2502、月之数 [规律题]

如果一个正整数m表示成二进制，它的位数为n（不包含前导0），寒月称它为一个n二进制数。所有的n二进制数中，1的总个数被称为n对应的月之数。
例如，3二进制数总共有4个，分别是4（100）、5（101）、6（110）、7（111），他们中1的个数一共是1＋2＋2＋3=8，所以3对应的月之数就是8。
Input
给你一个整数T，表示输入数据的组数，接下来有T行，每行包含一个正整数 n（1<=n<=20）。
Output
对于每个n ，在一行内输出n对应的月之数。
Sample Input

3
1
2
3

Sample Output

1
3
8

Code

//正整数m表示成二进制的位数称为一个n二进制数，所有的n二进制数中1的总个数即为n对应的月之数 
//规律题：a[n]=(a[n-1]-a[n-2])*4; 
#include<iostream>
#include<cmath>
using namespace std;
int main(){
    int a[21]={
    0};a[1]=1;a[2]=3;for(int i=3;i<=20;i++){
    a[i]=(a[i-1]-a[i-2])*4;}int t;cin>>t;while(t--){
    int n;cin>>n;cout<<a[n]<<endl;}return 0;
}

2503、a/b + c/d[计算分数之和]

给你2个分数，求他们的和，并要求和为最简形式。
Input
输入首先包含一个正整数T（T<=1000），表示有T组测试数据，然后是T行数据，每行包含四个正整数a,b,c,d（0<a,b,c,d<1000），表示两个分数a/b 和 c/d。
Output
对于每组测试数据，输出两个整数e和f，表示a/b + c/d的最简化结果是e/f，每组输出占一行。
Sample Input

2
1 2 1 3
4 3 2 3

Sample Output

5 6
2 1

Code

//计算两个分数之和，结果仍用分数表示
#include<iostream>
using namespace std;
//寻找最大公约数 
int f1(int a,int b){
    int t,c;if(a<b){
    t=a;a=b;b=t;}c=a%b;while(c!=0){
    a=b;b=c;c=a%b;}return b;
}
//寻找最小公倍数 
int f2(int a,int b){
    int t,c,m;m=a*b;if(a<b){
    t=a;a=b;b=t;}c=a%b;while(c!=0){
    a=b;b=c;c=a%b;}return m/b;
}int main(){
    int t;cin>>t;while(t--){
    int a,b,c,d,t,s;//a/b+c/d; cin>>a>>b>>c>>d;//分母相同，直接相加 if(b==d){
    t=a+c;s=b;//结果为t/s,对其进行约分，即寻找s和t的最大公约数int m=f1(s,t); if(m==1){
    cout<<t<<" "<<s<<endl;}else{
    s=s/m;t=t/m;cout<<t<<" "<<s<<endl;}} else{
    //a/b+c/d;分母不相同，首先要对分母进行通分，即寻找b和d的最小公倍数 int n=f2(b,d);a=a*n/b;c=c*n/d;t=a+c;s=n;//通分后计算得结果t/s，对结果进行约分 int m=f1(s,t); if(m==1){
    cout<<t<<" "<<s<<endl;}else{
    s=s/m;t=t/m;cout<<t<<" "<<s<<endl;}}}return 0;
} 

1708、Fibonacci String[字符串递推]

After little Jim learned Fibonacci Number in the class , he was very interest in it.
Now he is thinking about a new thing – Fibonacci String .

He defines : str[n] = str[n-1] + str[n-2] ( n > 1 )

He is so crazying that if someone gives him two strings str[0] and str[1], he will calculate the str[2],str[3],str[4] , str[5]…

For example :
If str[0] = “ab”; str[1] = “bc”;
he will get the result , str[2]=“abbc”, str[3]=“bcabbc” , str[4]=“abbcbcabbc” …………;

As the string is too long ,Jim can’t write down all the strings in paper. So he just want to know how many times each letter appears in Kth Fibonacci String . Can you help him ?
Input
The first line contains a integer N which indicates the number of test cases.
Then N cases follow.
In each case,there are two strings str[0], str[1] and a integer K (0 <= K < 50) which are separated by a blank.
The string in the input will only contains less than 30 low-case letters.
Output
For each case,you should count how many times each letter appears in the Kth Fibonacci String and print out them in the format “X:N”.
If you still have some questions, look the sample output carefully.
Please output a blank line after each test case.

To make the problem easier, you can assume the result will in the range of int.
Sample Input

1
ab bc 3

Sample Output

a:1
b:3
c:2
d:0
e:0
f:0
g:0
h:0
i:0
j:0
k:0
l:0
m:0
n:0
o:0
p:0
q:0
r:0
s:0
t:0
u:0
v:0
w:0
x:0
y:0
z:0

Code
方法一：内存超限

//str[n]=str[n-1]+str[n-2](n>1) str[0]="ab" str[1]="bc"
//统计一个字符串中每个字母的数量 
#include<iostream>
#include<string>
#include<cstring>
using namespace std;int main() {
    int t;//t个测试用例cin>>t;while(t--){
    string str[50];int k;//k[0,50)cin>>str[0]>>str[1]>>k;for(int i=2;i<=k;i++){
    str[i]=str[i-2]+str[i-1];//字符串连接 }//因为str[50]的时候字符串应该很大，故内存超限char c[32];//每个字符串最多30个字符 char letter[27]={
    'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z','\0'};int num[26]={
    0}; strcpy(c,str[k].c_str()); //将字符串转变为字符数组int len=strlen(c);//统计str[k]中各个字符的个数for(int i=0;i<len;i++){
    switch(c[i]){
    case 'a':num[0]++;break;case 'b':num[1]++;break;case 'c':num[2]++;break;case 'd':num[3]++;break;case 'e':num[4]++;break;case 'f':num[5]++;break;case 'g':num[6]++;break;case 'h':num[7]++;break;case 'i':num[8]++;break;case 'j':num[9]++;break;case 'k':num[10]++;break;case 'l':num[11]++;break;case 'm':num[12]++;break;case 'n':num[13]++;break;case 'o':num[14]++;break;case 'p':num[15]++;break;case 'q':num[16]++;break;case 'r':num[17]++;break;case 's':num[18]++;break;case 't':num[19]++;break;case 'u':num[20]++;break;case 'v':num[21]++;break;case 'w':num[22]++;break;case 'x':num[23]++;break;case 'y':num[24]++;break;case 'z':num[25]++;break;}} for(int i=0;i<26;i++){
    cout<<letter[i]<<":"<<num[i]<<endl;}} 
}

方法二、利用二维数组存储数量
AC

//str[n]=str[n-1]+str[n-2](n>1) str[0]="ab" str[1]="bc"
//统计一个字符串中每个字母的数量 
//利用一个二维数组a[i][j]来存放第j个字符串中的第i个字母的数量
#include<iostream>
#include<cstring>
using namespace std;
int a[27][50];
int main(){
    int t;cin>>t;while(t--){
    memset(a,0,sizeof(a));//初始化数组char str1[50],str2[50];int n;cin>>str1>>str2>>n;//str1中各个字母的数量int len1=strlen(str1);for(int k=0;k<len1;k++){
    for(int i=1;i<=26;i++){
    if(str1[k]==char(i+'a'-1)){
    a[i][0]++;break;}}}//计算出str1中各字符的数量int len2=strlen(str2);for(int k=0;k<len2;k++){
    for(int i=1;i<=26;i++){
    if(str2[k]==char(i+'a'-1)){
    a[i][1]++;break;}}}//计算出str2中各字符的数量//斐波那契递推for(int i=1;i<=26;i++){
    for(int j=2;j<=n;j++){
    a[i][j]=a[i][j-2]+a[i][j-1];}}//输出for(int k=1;k<=26;k++){
    cout<<(char)(k+'a'-1)<<":"<<a[k][n]<<endl;} cout<<endl;}return 0;
} 

1161、Eddy’s mistakes[将字符串中大写改外小写]

Eddy usually writes articles ,but he likes mixing the English letter uses, for example “computer science” is written frequently “coMpUtEr scIeNce” by him, this mistakes lets Eddy’s English teacher be extremely discontentment.Now please you to write a procedure to be able in the Bob article English letter to turn completely the small letter.
Input
The input contains several test cases.each line consists a test case，Expressed Eddy writes in an article , by letter, blank space,numeral as well as each kind of punctuation
composition, the writing length does not surpass 1000 characters.
Output
For each test case, you should output an only line, after namely the result of transforms the lowercase letter.
Sample Input

weLcOmE tO HDOj Acm 2005!

Sample Output

welcome to hdoj acm 2005!

Code

/*将输入的一串有大写有小写的字符串，全部转化为小写 大写转小写，加32 getline()函数读入一行字符串，在遇到换行时停止读入 */
#include<iostream>
#include<string> 
using namespace std;
int main(){
    string str;while(getline(cin,str)){
    for(int i=0;str[i]!='\0';i++){
    if(str[i]>='A'&&str[i]<='Z'){
    str[i]=str[i]+32;}}cout<<str<<endl;}return 0;
}