杭电ACM基础题（1236、1266、1279、1283、1302、1303）

1236、排名（排序）

今天的上机考试虽然有实时的Ranklist，但上面的排名只是根据完成的题数排序，没有考虑
每题的分值，所以并不是最后的排名。给定录取分数线，请你写程序找出最后通过分数线的
考生，并将他们的成绩按降序打印。
Input
测试输入包含若干场考试的信息。每场考试信息的第1行给出考生人数N ( 0 < N
< 1000 )、考题数M ( 0 < M < = 10 )、分数线（正整数）G；第2行排序给出第1题至第M题的正整数分值；以下N行，每行给出一
名考生的准考证号（长度不超过20的字符串）、该生解决的题目总数m、以及这m道题的题号
（题目号由1到M）。
当读入的考生人数为0时，输入结束，该场考试不予处理。
Output
对每场考试，首先在第1行输出不低于分数线的考生人数n，随后n行按分数从高
到低输出上线考生的考号与分数，其间用1空格分隔。若有多名考生分数相同，则按他们考
号的升序输出。
Sample Input

4 5 25
10 10 12 13 15
CS004 3 5 1 3
CS003 5 2 4 1 3 5
CS002 2 1 2
CS001 3 2 3 5
1 2 40
10 30
CS001 1 2
2 3 20
10 10 10
CS000000000000000001 0
CS000000000000000002 2 1 2
0

Sample Output

3
CS003 60
CS001 37
CS004 37
0
1
CS000000000000000002 20

Code:
1、结构体数组的使用，以及对结构体数组按照某一属性值进行排序

//排名
#include<iostream>
#include<string.h>
using namespace std;
struct Student{
    char id[21];int sm;int mid[10];int grade; 
}; 
int main(){
    //n表示考生人数(o,1000) m表示考题数(0,10] g表示分数线(正整数)int n,m,g;while(cin>>n){
    if(n==0) return 0;cin>>m>>g;//存储m道题目的分数,分数为正整数 int score[10]; for(int i=0;i<m;i++){
    cin>>score[i];}//考生的准考证号，长度不超过20的字符串，解决的题目总数sm(0,m] ,题号mid(0,m] Student stu[1000];//输入n名同学的准考证号，解决的题目数，以及题号for(int i=0;i<n;i++){
    stu[i].grade=0;cin>>stu[i].id>>stu[i].sm;for(int j=0;j<stu[i].sm;j++){
    cin>>stu[i].mid[j];stu[i].grade+=score[stu[i].mid[j]-1];//该名同学的得分 }}struct Student temp;bool flag=true; //对结构体数组按成绩、学号进行排序 //结构体数组可直接进行交换 for(int i=0;i<n-1;i++){
    int k=i;for(int j=i+1;j<n;j++){
    if(stu[k].grade<stu[j].grade){
    k=j;flag=false;}else if(stu[k].grade==stu[j].grade){
    if(strcmp(stu[k].id,stu[j].id)>0){
    k=j;flag=false;}}}if(flag==false){
    temp=stu[i];stu[i]=stu[k];stu[k]=temp;}    }int count=0;for(int i=0;i<n;i++){
    if(stu[i].grade>=g){
    count++;}}cout<<count<<endl;for(int i=0;i<n;i++){
    if(stu[i].grade>=g){
    cout<<stu[i].id<<" "<<stu[i].grade<<endl;}}}
} 

1266、Reverse Number

Welcome to 2006’4 computer college programming contest!

Specially, I give my best regards to all freshmen! You are the future of HDU ACM! And now, I must tell you that ACM problems are always not so easy, but, except this one… Ha-Ha!

Give you an integer; your task is to output its reverse number. Here, reverse number is defined as follows:

1. The reverse number of a positive integer ending without 0 is general reverse, for example, reverse (12) = 21;
2. The reverse number of a negative integer is negative, for example, reverse (-12) = -21;
3. The reverse number of an integer ending with 0 is described as example, reverse (1200) = 2100.
   Input
   Input file contains multiple test cases. There is a positive integer n (n<100) in the first line, which means the number of test cases, and then n 32-bit integers follow.
   Output
   For each test case, you should output its reverse number, one case per line.
   Sample Input

3
12
-12
1200

Sample Output

21
-21
2100

Code:
1、输出一个整数的相反数
2、利用两个字符数组，遍历num1[],赋值给num2[]，输出num2[]

//输出一个整数的相反数 
//利用两个字符数组，遍历num1[],赋值给num2[]
//char[] 防止输出的数组出现乱码，要在最后一个位置加'\0' 
#include<iostream>
#include<string.h>
using namespace std;
int main(){
    //n组数据(0,100) int n;cin>>n;while(n--){
    //输入一个32位的整数 char num1[33];char num2[33];cin>>num1;int len=strlen(num1);bool flag1=false,flag2=false;for(int i=len-1,j=0;i>=0;i--){
    if(num1[j]=='-'){
    //第一个数字是‘-’num2[j]='-';j++;i=len;flag1=true;continue;}if(i==0&&flag1==true){
    //在负数的情况break;}if(num1[i]=='0'&&flag2==false){
    //以0结尾num2[i]='0';}else{
    num2[j]=num1[i];j++;flag2=true;}} num2[len]='\0';//防止输出的字符数组出现乱码 cout<<num2<<endl;}
} 

1279、验证角谷猜想

数论中有许多猜想尚未解决，其中有一个被称为“角谷猜想”的问题，该问题在五、六十年代的美国多个著名高校中曾风行一时，这个问题是这样描述的：任何一个大于一的自然数，如果是奇数，则乘以三再加一；如果是偶数，则除以二；得出的结果继续按照前面的规则进行运算，最后必定得到一。现在请你编写一个程序验证他的正确性。
Input
本题有多个测试数据组，第一行为测试数据组数N，接着是N行的正整数。
Output
输出验证“角谷猜想”过程中的奇数，最后得到的1不用输出；每个测试题输出一行；每行中只有两个输出之间才能有一个空格；如果没有这样的输出，则输出：No number can be output !。
Sample Input

4
5
9
16
11 

Sample Output

5
9 7 11 17 13 5
No number can be output !
11 17 13 5

Code:
输出角谷猜想过程中的奇数,注意格式即可

//验证角谷猜想 
//输出角谷猜想过程中的奇数 
#include<iostream>
using namespace std;int main(){
    int N;cin>>N;while(N--){
    int n;//输入一个正整数 cin>>n;bool flag=false;while(n!=1){
    if(n%2==1){
    //n为奇数 if(flag==false){
    cout<<n;}else{
    cout<<" "<<n;}n=n*3+1; flag=true;}else{
    n=n/2;}}if(flag==false){
    cout<<"No number can be output !"<<endl;}else{
    cout<<endl;}} 
}

1282、回文猜想数

一个正整数，如果从左向右读（称之为正序数）和从右向左读（称之为倒序数）是一样的，这样的数就叫回文数。任取一个正整数，如果不是回文数，将该数与他的倒序数相加，若其和不是回文数，则重复上述步骤，一直到获得回文数为止。例如：68变成154（68+86），再变成605（154+451），最后变成1111（605+506），而1111是回文数。于是有数学家提出一个猜想：不论开始是什么正整数，在经过有限次正序数和倒序数相加的步骤后，都会得到一个回文数。至今为止还不知道这个猜想是对还是错。现在请你编程序验证之。
Input
每行一个正整数。
特别说明：输入的数据保证中间结果小于2^31。
Output
对应每个输入，输出两行，一行是变换的次数，一行是变换的过程。
Sample Input

27228
37649

Sample Output

3
27228--->109500--->115401--->219912
2
37649--->132322--->355553

Code
1、回文猜想数，利用vector数组存储中间过程

//回文数猜想#include<iostream>#include<string.h>#include<vector>using namespace std;//判断一个数是否是回文数
int f(int n){
    int temp,rev=0,p=n;while(n!=0){
    temp=n%10;rev=rev*10+temp;n=n/10;}if(rev==p){
    return 1;}else{
    return p+rev;//该数与其倒序数之和 }
} int main(){
    int n;while(cin>>n){
    vector<int>a;a.push_back(n);int count=0;    while(1){
    n=f(n);if(n==1){
    break;}     else{
        count++;a.push_back(n);}}cout<<count<<endl;for(int i=0;i<a.size();i++){
    if(i==0)cout<<a[i];elsecout<<"--->"<<a[i];}cout<<endl;}} 

1283、最简单的计算机

一个名叫是PigHeadThree的研究组织设计了一台实验用的计算机，命名为PpMm。PpMm只能执行简单的六种命令A，B，C，D，E，F；只有二个内存M1，M2；三个寄存器R1，R2，R3。六种命令的含义如下：
命令A：将内存M1的数据装到寄存器R1中；
命令B：将内存M2的数据装到寄存器R2中；
命令C：将寄存器R3的数据装到内存M1中；
命令D：将寄存器R3的数据装到内存M2中；
命令E：将寄存器R1中的数据和寄存器R2中的数据相加，结果放到寄存器R3中；
命令F：将寄存器R1中的数据和寄存器R2中的数据相减，结果放到寄存器R3中。
你的任务是：设计一个程序模拟PpMm的运行。
Input
有若干组，每组有2行，第一行是2个整数，分别表示M1和M2中的初始内容；第二行是一串长度不超过200的由大写字母A到F组成的命令串，命令串的含义如上所述。
Output
对应每一组的输入，输出只有一行，二个整数，分别表示M1，M2的内容；其中M1和M2之间用逗号隔开。

其他说明：R1，R2，R3的初始值为0，所有中间结果都在-2^31和231之间。
Sample Input

100 288
ABECED
876356 321456
ABECAEDBECAF

Sample Output

388,388
2717080,1519268

Code:
switch-case的运行

//程序模拟PpMm运行 
# include<iostream> 
#include<string.h>
using namespace std;
int main(){
    //初始内存中的数值为0 int M1=0,M2=0;    while(cin>>M1>>M2){
    //寄存器中的数值 int R1=0,R2=0,R3=0;//控制命令 char command[201];cin>>command;int len=strlen(command);for(int i=0;i<len;i++){
    switch(command[i]){
    case 'A':R1=M1;break;case 'B':R2=M2;break;case 'C':M1=R3;break;case 'D':M2=R3;break;case 'E':R3=R1+R2;break;case 'F':R3=R1-R2;break;} }cout<<M1<<","<<M2<<endl;}
} 

1302、The Snail[蜗牛爬出井底]

A snail is at the bottom of a 6-foot well and wants to climb to the top. The snail can climb 3 feet while the sun is up, but slides down 1 foot at night while sleeping. The snail has a fatigue factor of 10%, which means that on each successive day the snail climbs 10% * 3 = 0.3 feet less than it did the previous day. (The distance lost to fatigue is always 10% of the first day’s climbing distance.) On what day does the snail leave the well, i.e., what is the first day during which the snail’s height exceeds 6 feet? (A day consists of a period of sunlight followed by a period of darkness.) As you can see from the following table, the snail leaves the well during the third day.

Day Initial Height Distance Climbed Height After Climbing Height After Sliding
1 0 3 3 2
2 2 2.7 4.7 3.7
3 3.7 2.4 6.1 -

Your job is to solve this problem in general. Depending on the parameters of the problem, the snail will eventually either leave the well or slide back to the bottom of the well. (In other words, the snail’s height will exceed the height of the well or become negative.) You must find out which happens first and on what day.
Input
The input file contains one or more test cases, each on a line by itself. Each line contains four integers H, U, D, and F, separated by a single space. If H = 0 it signals the end of the input; otherwise, all four numbers will be between 1 and 100, inclusive. H is the height of the well in feet, U is the distance in feet that the snail can climb during the day, D is the distance in feet that the snail slides down during the night, and F is the fatigue factor expressed as a percentage. The snail never climbs a negative distance. If the fatigue factor drops the snail’s climbing distance below zero, the snail does not climb at all that day. Regardless of how far the snail climbed, it always slides D feet at night.
Output
For each test case, output a line indicating whether the snail succeeded (left the well) or failed (slid back to the bottom) and on what day. Format the output exactly as shown in the example.
Sample Input

6 3 1 10
10 2 1 50
50 5 3 14
50 6 4 1
50 6 3 1
1 1 1 1
0 0 0 0

Sample Output

success on day 3
failure on day 4
failure on day 7
failure on day 68
success on day 20
failure on day 2

Code
1、输出的字符串单词拼错了，会显示WA

//分析题意
//井深H，蜗牛白天爬U，晚上会下降D，疲劳系数为F，问蜗牛能否爬出井口，若能的话需要几天
#include<iostream>
using namespace std;int main(){
    double H,U,D,F;//[1,100] while(cin>>H>>U>>D>>F){
    if(H==0&&U==0&&D==0&&F==0){
    return 0;}int days=1;//由于疲劳因素使得蜗牛在之后每天爬行比第一天下降的距离 double FD=F*U*0.01;//蜗牛每天爬行的距离 double Ud=U;bool flag=true;while(U<=H){
    //蜗牛白天没有爬出来U=U-D;//一天白天爬的加晚上下降的总距离 Ud=Ud-FD;//下一天可以向上爬的距离 if(Ud<0){
    Ud=0;} if(U<0){
     cout<<"failure on day "<<days<<endl;flag=false;break;}U=U+Ud;days++;}if(flag==true)cout<<"success on day "<<days<<endl;}
} 

1303、Doubles[统计两倍的数的个数]

As part of an arithmetic competency program, your students will be given randomly generated lists of from 2 to 15 unique positive integers and asked to determine how many items in each list are twice some other item in the same list. You will need a program to help you with the grading. This program should be able to scan the lists and output the correct answer for each one. For example, given the list
1 4 3 2 9 7 18 22

your program should answer 3, as 2 is twice 1, 4 is twice 2, and 18 is twice 9.
Input
The input file will consist of one or more lists of numbers. There will be one list of numbers per line. Each list will contain from 2 to 15 unique positive integers. No integer will be larger than 99. Each line will be terminated with the integer 0, which is not considered part of the list. A line with the single number -1 will mark the end of the file. The example input below shows 3 separate lists. Some lists may not contain any doubles.
Output
The output will consist of one line per input list, containing a count of the items that are double some other item.
Sample Input

1 4 3 2 9 7 18 22 0
2 4 8 10 0
7 5 11 13 1 3 0
-1 

Sample Output

3
2
0

Code
1、统计一行数字中，一个数字是另外一个两倍的数，比较简单

//统计一行数字中，一个数字是另外一个两倍的数 
//how many items in each list are twice some other item in the same list 
#include<iostream>
using namespace std;
int main(){
    int flag=1;while(flag){
    int num[16],len=0;for(int i=0;i<16;i++){
    cin>>num[i];if(num[i]==0){
    break;}else if(num[i]==-1){
    return 0;}len++; }int count=0;for(int i=0;i<len;i++){
    for(int j=0;j<len;j++){
    if(num[i]*2==num[j]){
    count++;break;} }}cout<<count<<endl;}}