杭电ACM基础题（2048、2049、2053、2055、2056、2057、2060、2061、2071、2073）

2048、抽奖活动无人中奖的概率[错排问题]

HDU 2006’10 ACM contest的颁奖晚会隆重开始了！
为了活跃气氛，组织者举行了一个别开生面、奖品丰厚的抽奖活动，这个活动的具体要求是这样的：

首先，所有参加晚会的人员都将一张写有自己名字的字条放入抽奖箱中；
然后，待所有字条加入完毕，每人从箱中取一个字条；
最后，如果取得的字条上写的就是自己的名字，那么“恭喜你，中奖了！”

大家可以想象一下当时的气氛之热烈，毕竟中奖者的奖品是大家梦寐以求的Twins签名照呀！不过，正如所有试图设计的喜剧往往以悲剧结尾，这次抽奖活动最后竟然没有一个人中奖！

我的神、上帝以及老天爷呀，怎么会这样呢？

不过，先不要激动，现在问题来了，你能计算一下发生这种情况的概率吗？

不会算？难道你也想以悲剧结尾？！
Inupt
输入数据的第一行是一个整数C,表示测试实例的个数，然后是C 行数据，每行包含一个整数n(1<n<=20),表示参加抽奖的人数。
Output
对于每个测试实例，请输出发生这种情况的百分比，每个实例的输出占一行, 结果保留两位小数(四舍五入)，具体格式请参照sample output。
Sample Input

1
2

Sample Output

50.00%

Code

//错排公式的应用--n张纸条和n个人刚刚好都不对应
//概率：错排的方式总数/n张纸条的可能的排列总数 
#include<iostream>
#include<iomanip>
using namespace std;__int64 jiechen(int n){
    __int64 result=1;for(int i=n;i>0;i--){
    result=result*i;}return result;
}
int main(){
    int t;cin>>t;//错排公式__int64 a[21]={
    0,0,1};for(int i=3;i<=20;i++){
    a[i]=a[i-1]*(i-1)+a[i-2]*(i-1);} while(t--){
    int n;//人数[1,20]cin>>n;//计算n!__int64 m=jiechen(n);//概率 double x=(double)a[n]/(double)m;cout<<setiosflags(ios::fixed);cout<<setprecision(2)<<x*100<<"%"<<endl;} return 0;
} 

2049、不容易系列之(4)——考新郎[错排问题]

国庆期间,省城HZ刚刚举行了一场盛大的集体婚礼,为了使婚礼进行的丰富一些,司仪临时想出了有一个有意思的节目,叫做"考新郎",具体的操作是这样的:
首先,给每位新娘打扮得几乎一模一样,并盖上大大的红盖头随机坐成一排;
然后,让各位新郎寻找自己的新娘.每人只准找一个,并且不允许多人找一个.
最后,揭开盖头,如果找错了对象就要当众跪搓衣板…

看来做新郎也不是容易的事情…

假设一共有N对新婚夫妇,其中有M个新郎找错了新娘,求发生这种情况一共有多少种可能.
Input
输入数据的第一行是一个整数C,表示测试实例的个数，然后是C行数据，每行包含两个整数N和M(1<M<=N<=20)。
Output
对于每个测试实例，请输出一共有多少种发生这种情况的可能，每个实例的输出占一行。
Sample Input

2
2 2
3 2

Sample Output

1
3

Code

//一共有N对新婚夫妇,其中有M个新郎找错了新娘,发生这种情况一共有多少种可能. 
//思路：C(N,N-M)*错排M个元素的的D(M) 
#include<iostream>
using namespace std;__int64 f(int n){
    __int64 result=1;for(int i=n;i>=1;i--){
    result=result*i;}return result;
} 
int main(){
    int t;cin>>t;__int64 a[21]={
    0,0,1};for(int i=3;i<=20;i++){
    a[i]=a[i-1]*(i-1)+a[i-2]*(i-1);}while(t--){
    int n,m;cin>>n>>m;//n和m的范围[1,20],n对新婚夫妇，m对找错了;//C(n,c)的计算int c=n-m;__int64 b=f(n)/(f(c)*f(n-c));cout<<b*a[m]<<endl;}return 0;
}

2053、Switch Game[开关灯]

There are many lamps in a line. All of them are off at first. A series of operations are carried out on these lamps. On the i-th operation, the lamps whose numbers are the multiple of i change the condition ( on to off and off to on ).
Input
Each test case contains only a number n ( 0< n<= 10^5) in a line.
Output
Output the condition of the n-th lamp after infinity operations ( 0 - off, 1 - on ).
Sample Input

1
5

Sample Output

1
0

Code
题目：有一排灯，一开始处于关闭状态，第i次对是处于i的倍数位置的的台灯进行改变其状态(由开变为关或者由关变为开)，输出对其操作无穷次后第n个位置的台灯的状态(0代表关闭，1代表打开)
方法一：n的因数有m个，若m可以被2整除，则其状态为0，否则为1。因为n的因数有m个，表示其状态需要改变m次，而台灯的状态改变周期为2。

/*题目：有一排灯，一开始处于关闭状态，然后第i次对是处于i的倍数位置的的台灯进行改变其状态 (由开变为关或者由关变为开)，输出对其操作无穷次后第n个位置的台灯的状态(0代表关闭，1代表打开) 思路：第n个台灯在操作n次后状态即不再改变，故而实际上是求第n次第n个台灯的状态。 思路1：找规律--除了n*n是1，其余都是0 思路2：n的因数有m个，若m可以被2整除，则其状态为0，否则为1（对思路2的解释：n的因数有m个，表示其状态需要改变m次，而台灯的状态改变周期为2） */ 
#include<iostream>
using namespace std;
int main(){
    int n;//(0,100000];while(cin>>n){
    int sum=0;for(int i=1;i<=n;i++){
    if(n%i==0){
    sum++;}}if(sum%2==0)cout<<"0"<<endl;elsecout<<"1"<<endl;}return 0;
} 

**方法二：找规律–除了nn是1，其余都是0 ***

#include<iostream>
#include<cmath>
using namespace std;
int main(){
    int n;//(0,100000];while(cin>>n){
    double a=sqrt(n);int b=sqrt(n);if(a==b){
    cout<<"1"<<endl;}else{
    cout<<"0"<<endl;}}return 0;
} 

2055、An easy problem[计算n+f?]

we define f(A) = 1, f(a) = -1, f(B) = 2, f(b) = -2, … f(Z) = 26, f(z) = -26;
Give you a letter x and a number y , you should output the result of y+f(x).
Input
On the first line, contains a number T.then T lines follow, each line is a case.each case contains a letter and a number.
Output
for each case, you should the result of y+f(x) on a line.
Sample Input

6
R 1
P 2
G 3
r 1
p 2
g 3

Sample Output

19
18
10
-17
-14
-4

Code:
方法一：暴力

//按要求计算
#include<iostream>
using namespace std;
int main(){
    int t;cin>>t;while(t--){
    char c;int n;cin>>c>>n;//计算n+f(c) switch(c){
    case 'A':cout<<1+n<<endl;break;case 'a':cout<<n-1<<endl;break;case 'B':cout<<2+n<<endl;break;case 'b':cout<<n-2<<endl;break;case 'C':cout<<3+n<<endl;break;case 'c':cout<<n-3<<endl;break;case 'D':cout<<4+n<<endl;break;case 'd':cout<<n-4<<endl;break;case 'E':cout<<5+n<<endl;break;case 'e':cout<<n-5<<endl;break;case 'F':cout<<6+n<<endl;break;case 'f':cout<<n-6<<endl;break;case 'G':cout<<7+n<<endl;break;case 'g':cout<<n-7<<endl;break;case 'H':cout<<8+n<<endl;break;case 'h':cout<<n-8<<endl;break;case 'I':cout<<9+n<<endl;break;case 'i':cout<<n-9<<endl;break;case 'J':cout<<10+n<<endl;break;case 'j':cout<<n-10<<endl;break;case 'K':cout<<11+n<<endl;break;case 'k':cout<<n-11<<endl;break;case 'L':cout<<12+n<<endl;break;case 'l':cout<<n-12<<endl;break;case 'M':cout<<13+n<<endl;break;case 'm':cout<<n-13<<endl;break;case 'N':cout<<14+n<<endl;break;case 'n':cout<<n-14<<endl;break;case 'O':cout<<15+n<<endl;break;case 'o':cout<<n-15<<endl;break;case 'P':cout<<16+n<<endl;break;case 'p':cout<<n-16<<endl;break;case 'Q':cout<<17+n<<endl;break;case 'q':cout<<n-17<<endl;break;case 'R':cout<<18+n<<endl;break;case 'r':cout<<n-18<<endl;break;case 'S':cout<<19+n<<endl;break;case 's':cout<<n-19<<endl;break;case 'T':cout<<20+n<<endl;break;case 't':cout<<n-20<<endl;break;case 'U':cout<<21+n<<endl;break;case 'u':cout<<n-21<<endl;break;case 'V':cout<<22+n<<endl;break;case 'v':cout<<n-22<<endl;break;case 'W':cout<<23+n<<endl;break;case 'w':cout<<n-23<<endl;break;case 'X':cout<<24+n<<endl;break;case 'x':cout<<n-24<<endl;break;case 'Y':cout<<25+n<<endl;break;case 'y':cout<<n-25<<endl;break;case 'Z':cout<<26+n<<endl;break;case 'z':cout<<n-26<<endl;break;}}return 0;
} 

方法二、

#include<iostream>
using namespace std;int f(char c){
    if(c>='A'&&c<='Z'){
    return c-'A'+1;}else if(c>='a'&&c<='z'){
    return -1*(c-'a'+1);}
}
int main(){
    int t;cin>>t;while(t--){
    int n;char c;cin>>c>>n;cout<<n+f(c)<<endl;}return 0;
}

2056、Rectangles[计算重叠部分矩形面积]

Given two rectangles and the coordinates of two points on the diagonals of each rectangle,you have to calculate the area of the intersected part of two rectangles. its sides are parallel to OX and OY .
Input
Input The first line of input is 8 positive numbers which indicate the coordinates of four points that must be on each diagonal.The 8 numbers are x1,y1,x2,y2,x3,y3,x4,y4.That means the two points on the first rectangle are(x1,y1),(x2,y2);the other two points on the second rectangle are (x3,y3),(x4,y4).
Output
Output For each case output the area of their intersected part in a single line.accurate up to 2 decimal places.
Sample Input

1.00 1.00 3.00 3.00 2.00 2.00 4.00 4.00
5.00 5.00 13.00 13.00 4.00 4.00 12.50 12.50

Sample Output

1.00
56.25

Code
题目:给一个平面直角坐标中的两个矩形，每个矩形的每条边分别平行于x轴y轴，
给出两个矩形的对角的两个顶点，求出两个矩形重叠部分的面积。

/* 题目:给一个平面直角坐标中的两个矩形，每个矩形的每条边分别平行于x轴y轴， 给出两个矩形的对角的两个顶点，求出两个矩形重叠部分的面积。 */
#include<iostream>
#include<iomanip>
#include<cmath>
#include<algorithm>
using namespace std;
int main(){
    double x1,y1,x2,y2,x3,y3,x4,y4,a[4],b[4];while(cin>>x1>>y1>>x2>>y2>>x3>>y3>>x4>>y4){
    a[0]=x1;a[1]=x2;a[2]=x3;a[3]=x4;b[0]=y1;b[1]=y2;b[2]=y3;b[3]=y4;sort(a,a+4);sort(b,b+4);double c=fabs(x2-x1)+fabs(x4-x3)-(a[3]-a[0]);//长double h=fabs(y2-y1)+fabs(y4-y3)-(b[3]-b[0]);//宽cout<<setiosflags(ios::fixed);if(c>0&&h>0){
    //长和宽都大于0，则重叠部分存在cout<<setprecision(2)<<c*h<<endl;}else{
    cout<<0.00<<endl;}}return 0;
} 

2057、A + B Again[十六进制数相加]

There must be many A + B problems in our HDOJ , now a new one is coming.
Give you two hexadecimal integers , your task is to calculate the sum of them,and print it in hexadecimal too.
Easy ? AC it !
Input
The input contains several test cases, please process to the end of the file.
Each case consists of two hexadecimal integers A and B in a line seperated by a blank.
The length of A and B is less than 15.
Output
For each test case,print the sum of A and B in hexadecimal in one line.
Sample Input

+A -A
+1A 12
1A -9
-1A -12
1A -AA

Sample Output

0
2C
11
-2C
-90

Code
方法一：将十六进制数先转化为十进制数相加，再将相加结果转为十六进制数输出

//十六进制的数进行运算，将运算结果以十六进制的数显示出来
#include<iostream> 
#include<cstring>
#include<cmath>
using namespace std;void convert_hexa(__int64 n){
    bool flag=true;if(n<0){
    cout<<"-";n=-1*n;}else if(n==0){
    flag=false;cout<<0<<endl;} char c[16];int i=0,temp;while(n!=0){
    temp=n%16;switch(temp){
    case 10:c[i++]='A';break;case 11:c[i++]='B';break;case 12:c[i++]='C';break;case 13:c[i++]='D';break;case 14:c[i++]='E';break;case 15:c[i++]='F';break;default:c[i++]=temp+'0';break;}n=n/16;}if(flag==true){
    for(int k=i-1;k>=0;k--){
    cout<<c[k];}cout<<endl;}
}int main(){
    char a[16],b[16];while(cin>>a>>b){
    int len1=strlen(a);int len2=strlen(b);//将a转化为十进制数aa__int64 aa=0,bb=0,temp; for(int i=len1-1,j=0;i>=0;i--,j++){
    if(a[i]!='+'&&a[i]!='-'){
    switch(a[i]){
    case 'A':temp=10;break;case 'B':temp=11;break;case 'C':temp=12;break;case 'D':temp=13;break;case 'E':temp=14;break;case 'F':temp=15;break;default:temp=a[i]-'0';break;}aa=aa+temp*pow(16,j);}}if(a[0]=='-'){
    aa=-1*aa;}for(int i=len2-1,j=0;i>=0;i--,j++){
    if(b[i]!='+'&&b[i]!='-'){
    switch(b[i]){
    case 'A':temp=10;break;case 'B':temp=11;break;case 'C':temp=12;break;case 'D':temp=13;break;case 'E':temp=14;break;case 'F':temp=15;break;default:temp=b[i]-'0';break;}bb=bb+temp*pow(16,j);}}if(b[0]=='-'){
    bb=-1*bb;}    //将结果转为16进制__int64 sum=aa+bb;        convert_hexa(sum);} 
}

方法二、
利用cout<<hex<<a+b

/* 默认状态下，数据按十进制输入和输出。如果要求按八进制或十六进制输入输出，则需要在 cin或cout中指明相应的数据形式，oct为八进制，hex为十六进制，dec为十进制 */
#include<iostream>
#include<iomanip> 
using namespace std;
int main(){
    long long a,b;while(cin>>hex>>a>>b){
    //表示a和b是以16进制数输出 if(a+b<0){
    cout<<setiosflags(ios::uppercase)<<hex<<'-'<<-(a+b)<<endl;//将结果以十六进制（大写）表示出来 }else{
    cout<<setiosflags(ios::uppercase)<<hex<<a+b<<endl;} }
}

2060、Snooker[斯诺克比赛]

background:
Philip likes to play the QQ game of Snooker when he wants a relax, though he was just a little vegetable-bird. Maybe you hadn’t played that game yet, no matter, I’ll introduce the rule for you first.
There are 21 object balls on board, including 15 red balls and 6 color balls: yellow, green, brown, blue, pink, black.
The player should use a white main ball to make the object balls roll into the hole, the sum of the ball’s fixed value he made in the hole is the player’s score. The player should firstly made a red ball into the hole, after that he gains red-ball’s value(1 points), then he gets the chance to make a color ball, then alternately. The color ball should be took out until all the red-ball are in the hole. In other word, if there are only color balls left on board, the player should hit the object balls in this order: yellow(2 point), green(3 point), brown(4 point), blue(5 point), pink(6 point), black(7 point), after the ball being hit into the hole, they are not get out of the hole, after no ball left on board, the game ends, the player who has
the higher score wins the game. PS: red object balls never get out of the hole.
I just illustrate the rules that maybe used, if you want to contact more details, visit http://sports.tom.com/snooker/ after
the contest.

for example, if there are 12 red balls on board(if there are still red ball left on board, it can be sure that all the color
balls must be on board either). So suppose Philp can continuesly hit the ball into the hole, he can get the maximun score is
12 * 1 (12 red-ball in one shoot) + 7 * 12(after hit a red ball, a black ball which was the most valuable ball should be the target) + 2 + 3 + 4 + 5 + 6 + 7(when no red ball left, make all the color ball in hole).
Now, your task is to judge whether Philip should make the decision to give up when telling you the condition on board(How many object balls still left not in the hole and the other player’s score). If Philp still gets the chance to win, just print “Yes”, otherwise print “No”. (PS: if the max score he could get on board add his current score is equal to the opponent’s current score, still output “Yes”)
Input
The first line contains a numble N indicating the total conditions. Then followed by N lines, each line is made of three integers:
Ball_Left P_Score O_Score represeting the ball number left on board, Philp’s current score, and the opponent’s current score.
All the input value are in 32 bit integer value range.
Output
You should caculate the max score left Philp can gain, and judge whether he has the possiblity to win.
Sample Input

2
12 1 1
1 30 39

Sample Output

Yes
No

Code

/* 题目含义：斯诺克 开始共21个球，其中 15个红球，6个彩球（黄、绿、棕、蓝、粉、黑） 当有红球留在桌面时，先打红球，然后再打彩球 彩球的分值：红（1）,黄（2）,绿（3），棕（4）,蓝（5），粉（6）,黑（7） 红球没打完之前，彩色球击落之后可以重新拿回桌面 要求：输入n个测试用例，接下来n行，每行包含三项内容：桌面上剩余的球数Ball_Left;当前得分P_Score;对手得分:O_Score输出当前有没有可能取得最后的胜利。 思路：若Ball_left>7,可以每次都打进黑球，然后接着打彩色球，最后判断其是否大于O_Score;若Ball_left<7，可以计算得出当前的最大得分，比较 */ 
#include<iostream>
using namespace std;
int main() {
    int t,score[6]={
    7,6,5,4,3,2};cin>>t;while(t--){
    int ball_left,p_score,o_score;cin>>ball_left>>p_score>>o_score;if(ball_left<=6){
    //说明当前红色求均已进洞 for(int i=0;i<ball_left;i++){
    p_score=p_score+score[i];}if(p_score>=o_score){
    cout<<"Yes"<<endl;}else{
    cout<<"No"<<endl;}}else{
    //注意：红球没打完之前，彩色球击落之后可以重新拿回桌面 p_score=p_score+(ball_left-6)*1+(ball_left-6)*7+27;if(p_score>=o_score){
    cout<<"Yes"<<endl;}else{
    cout<<"No"<<endl;}}}
}

2061、计算课程的绩点

If there are K(K > 0) courses, the i-th course has the credit Ci, your score Si, then the result GPA is
GPA = (C1 * S1 + C2 * S2 +……+Ci * Si……) / (C1 + C2 + ……+ Ci……) (1 <= i <= K, Ci != 0)
If there is a 0 <= Si < 60, The GPA is always not existed.
Input
The first number N indicate that there are N test cases(N <= 50). In each case, there is a number K (the total courses number), then K lines followed, each line would obey the format: Course-Name (Length <= 30) , Credits(<= 10), Score(<= 100).
Notice: There is no blank in the Course Name. All the Inputs are legal
Output
Output the GPA of each case as discribed above, if the GPA is not existed, ouput:“Sorry!”, else just output the GPA value which is rounded to the 2 digits after the decimal point. There is a blank line between two test cases.
Sample Input

2
3
Algorithm 3 97
DataStruct 3 90
softwareProject 4 85
2
Database 4 59
English 4 81

Sample Output

90.10Sorry!

Code

/* 计算GPA 给出各门课程的课程名，学分，以及成绩，输出其GPA GPA = (C1 * S1 + C2 * S2 +……+Ci * Si……) / (C1 + C2 + ……+ Ci……) */
#include<iostream>
#include<iomanip>
using namespace std;struct Course{
    char coursename[31];double credits;//学分double score;//成绩 
}subject[100];int main(){
    int n;//[1,50]cin>>n;while(n--){
    int t;//t门课程cin>>t; double sum1=0;//各门课成绩的总分 for(int i=0;i<t;i++){
    cin>>subject[i].coursename>>subject[i].credits>>subject[i].score;sum1+=subject[i].credits; }double sum2=0;bool flag=true;for(int i=0;i<t;i++){
    if(subject[i].score<60){
    if(n==0)cout<<"Sorry!"<<endl;elsecout<<"Sorry!"<<endl<<endl;flag=false;break;}else{
    sum2+=subject[i].credits*subject[i].score;}}if(flag==true){
    if(n==0)cout<<setiosflags(ios::fixed)<<setprecision(2)<<sum2/sum1<<endl;elsecout<<setiosflags(ios::fixed)<<setprecision(2)<<sum2/sum1<<endl<<endl;}}return 0;
} 

2071、Max Num[最高身高]

There are some students in a class, Can you help teacher find the highest student .
Input
There are some cases. The first line contains an integer t, indicate the cases; Each case have an integer n ( 1 ≤ n ≤ 100 ) , followed n students’ height.
Output
For each case output the highest height, the height to two decimal plases;
Sample Input

2
3 170.00 165.00 180.00
4 165.00 182.00 172.00 160.00

Sample Output

180.00
182.00

Code

//寻找一组数值中身高最高的数
#include<iostream> 
#include<algorithm>
#include<iomanip>
using namespace std;
int main(){
    int t;cin>>t;while(t--){
    int n;double height[100];cin>>n;//[1,100] for(int i=0;i<n;i++){
    cin>>height[i];}sort(height,height+n);cout<<setiosflags(ios::fixed)<<setprecision(2)<<height[n-1]<<endl;}return 0;
}

2073、无限的路

甜甜从小就喜欢画图画，最近他买了一支智能画笔，由于刚刚接触，所以甜甜只会用它来画直线，于是他就在平面直角坐标系中画出如下的图形：

甜甜的好朋友蜜蜜发现上面的图还是有点规则的，于是他问甜甜：在你画的图中，我给你两个点，请你算一算连接两点的折线长度（即沿折线走的路线长度）吧。
Input
第一个数是正整数N（≤100）。代表数据的组数。
每组数据由四个非负整数组成x1，y1，x2，y2；所有的数都不会大于100。
Output
对于每组数据，输出两点(x1,y1),(x2,y2)之间的折线距离。注意输出结果精确到小数点后3位。
Sample Input

5
0 0 0 1
0 0 1 0
2 3 3 1
99 99 9 9
5 5 5 5

Sample Output

1.000
2.414
10.646
54985.047
0.000

思路
1、题目中所给的所有点除原点外均出现在x+y=1,2,3,4…
2、任意两点之间的距离可以拆分两点分别到原点之间距离的差值的绝对值
3、计算任意一点(x,y)到原点的距离时:
斜率为1的长度：sqrt(2)*边长

double sum1=0,t=sqrt(2);for(int i=1;i<x+y;i++){
    sum1=sum1+t*i;}//加上当前点所在边的长度 sum1=sum1+t*x; 

斜率不为1的长度

double sum2=0;for(int i=1;i<x+y;i++){
    sum2=sum2+sqrt((i*i)+(i+1)*(i+1));}//当起始点的坐标不是（0，0）时要加上最开始的一条竖直的边 sum2=sum2+1; 

实现：

#include<iostream>
#include<iomanip>
#include<cmath>
using namespace std;//计算（x,y）距离(0,0)的距离 
double distance1(int x,int y){
    double sum1=0,t=sqrt(2);//计算斜率为1的边的距离 for(int i=1;i<x+y;i++){
    sum1=sum1+t*i;}//加上当前点所在边的长度 sum1=sum1+t*x; //计算斜率不为1的距离 double sum2=0;for(int i=0;i<x+y;i++){
    //当i==0时候，加的是开始的那一条竖直的边 sum2=sum2+sqrt((i*i)+(i+1)*(i+1));} return sum1+sum2;
}
int main(){
    int n;cin>>n;while(n--){
    int x1,y1,x2,y2;cin>>x1>>y1>>x2>>y2;double length=fabs(distance1(x1,y1)-distance1(x2,y2));cout<<setiosflags(ios::fixed)<<setprecision(3)<<length<<endl;}return 0;
}