ACM软件大赛之编程大赛题目(附部分答案)

比赛注意事项：

 比赛时间为3小时（180分钟）；比赛分两个阶段：第一阶段限时30分钟，完成公示的

3题，第二阶段限时150分钟（事先完成第一阶段题目的小组可提前进入第二阶段）；  比赛第一阶段的3道题目将在前期宣传中告知参赛选手，比赛第二阶段的题目将由赛事

当场公布竞赛题目；

 前两阶段题目分为三个分值（5分、10分、15分），第一阶段3道公示题都为5分；第

二阶段总共15道题，根据不同的难度分值不同，分别为5道5分题，5道10分题，5道15分题；第一阶段参赛队员不可参考任何相关资料；第二阶段参赛队员可以携带诸如书，手册，程序清单等参考资料。比赛过程中队员不得携带任何电子媒质的资料；参赛者可以选择自己擅长的语言（C,C++,JAVA等等）进行编写

 考虑到大一和大二学生的知识掌握程度，大一参加选手一开始就会有10分的分数，最后总分是由所做题目及初始的10分相加得到。

 每组队员根据安排使用电脑，小组人数为两人的使用一台电脑，超过两人的使用两台电

脑，每台的电脑配置完全相同；

 各小组每做完一题或几题，必须交予评委老师运行，评委老师当场给分；  如在比赛中发现作弊等行为，将取消比赛资格。

第一阶段公示题目：

题目一：（5分）

打印以下图形，纵遵从字母顺序，行字符数遵从斐波那契数列 A B CC DDD EEEEE FFFFFFFF

GGGGGGGGGGGGG

#include int f(int x){

int a = 1 , b = 0; int max_ = x; int sum = 0;

for(int i = 0; i < max_ ; i++){

sum = a + b; a = b; b = sum; }

return sum; }

void loop_print(int num,char chr){ for(int i = 0; i < num ;i++) std::cout<int main(){

int line_max = 7; char chr = 'A';

for(int line = 0; line < line_max; line++){ loop_print(f(line+1),chr); chr++; }

return 0; }

题目二：（5分）

有个电子钟，12点显示为12:00（即12小时制），那么请问一天24时间内，出现连续3个相同数字的钟点有几个？

#include using namespace std; bool check(int time){ int h=time/100; int m=time-100*h; return h<=12&&m<=59&&h>0?true:false;//12小时制 }

int main(){ int time=0;

int j(0);//总计数器

while(time<1270){//max 12:59 int t=time; int n[4]; for(int i=0;i<4;i++){ n[i]=t%10; t /= 10; } if(n[1]==n[2]&&(n[0]==n[1]||n[3]==n[1])&&check(time)){ //cout<time++; }

cout<<\"total: \"<题目三：（5分）

10进制的四位数中有几个符合如下特征：将其分别表示为16进制、10进制、12进制，在每种状态下，分别将各个位上的数相加，能得到3个相等10进制数。 例如2992

10进制：2992 2+9+9+2 = 22 12进制：14 1+8+9+4 = 22 16进制：BB0 11+11+0 = 22

2992-2999

#include #include using namespace std; int convert(int n,int c){ float high_p=0; int sum=0;

int a[4]={0,0,0,0}; for(int i=0;;i++){

float testN = pow(c,(float) i); if(n>=testN)high_p=i; else break; }

for(int i=0;high_p!=-1;i++){ a[i]=n/pow(c,high_p); n-=a[i]*pow(c,high_p); high_p--; }

for(int i=0;i<4;i++){sum+=a[i];} return sum; }

int main(){ int j=0;

for(int i=1000;i<=9999;i++){

if((convert(i,16)==convert(i,10))&&(convert(i,10)==convert(i,12))){ cout<cout<}

第二阶段题目：

题目一：（5分）

不引入临时变量写出swap(a,b)功能

void swap(int &a, int &b){ a += b; b = a-b; a -= b; }

题目二：（5分）

she分别代表3个数字，已知： (he)^2=she she=?

#include int main(){

for(int he=15;he<=96;he++) for(int s=1;s<=9;s++) if(he*he==100*s+he) std::cout<题目三：（5分）

有4条狗A、B、C、D，他们分别在一条100m的公路上步行，速率均为5m/s，A初始在30m处，B初始在65m处，C初始在75m处，D初始在95m处，初始左右方向是随意的，任意两狗相遇则各自掉头（掉头时间不计，速率保持5m/s）。请问，4条狗最终都离开公路的最大时间是几秒？ #include int main(){ std::cout<<95/5; return 0; }

题目四：（5分）

Big Bang 中的高级石头剪刀布问题 Scissors - Paper Paper - Rock Rock - Scissors Rock - Lizard

Lizard - Spock Spock - Scissors Scissors - Lizard Lizard - Paper Paper - Spock Spock - Rock

规则是左边的手势赢右边的手势，现有玩家P1、P2，输入各自选择的手势，得出胜负。

#include #include using namespace std; int main() { int p2, p1; cout << \"1.Paper\" << endl << \"2.Rock\" << endl << \"3.Lizard\" << endl << \"4.Spock\" << endl << \"5.Scissors\" << endl; cin >> p1 >> p2; float n = p1 - p2; if (n * pow(-1, fabs(n)) < 0)//此算法由@yaozizi提供 cout << \"p2 win\"; else if (n == 0) cout << \"duce\"; else cout << \"p1 win\"; return 0; }

题目五：（5分）

游戏规则：21根火柴，每次取1-4根，谁取走最后一根判输。现在人和计算机博弈，设计一个程序保证计算机必胜，要求每回合人与计算机各输入（或返回）一个代表取走火柴根数的数，直到游戏结束。

#include using namespace std; int main(){ int n=21; int p,c; while(n!=0){ cin>>p; while(p>4||p<=0||n-p<0){ cout<<\"err, input again\"<>p; } if(n!=0) {

}

}

}

if(n!=1)cout<<5-p<if(n>=5)n-=5;

题目六：（10分）

下列式子： 2+3+4=9 1+2+3+4=10

显然右边的数都能表示为n（n>2）个连续自然数之和（1开始），暂称之为囧数 但似乎23、32等数都不能写成几个数之和的形式，所以它们不是囧数 这里有个可行的判断方法为： 上限为N，则测试 1+2+3 1+2+3+4 „„

1+2+3+4……+N 2+3+4

„„

2+3+4+……+N „„

(N-2)+(N-1)+N 是否等于N

这是一种可行但非常暴力的穷举

实际上囧数还是有一些规律可循的，请设计一个优于之前提到的算法 要求输入一个数，并判断它是否为囧数 /*

1.如果一个数能被奇数（>=3）整除，则必能写成X=平均数*中间数的形式，所以是囧数 2.如果一个数是合数，如果其中有奇数因子，则回到1，为囧数;如果它是2的乘方，则不是囧数 证明：它无法写成奇数个相加，因为除不尽奇数；也不能写成偶数个相加，中间数有两个，和必为奇数，这个奇数必然是欲判断数的一个因子

3.如果一个数是素数，则必须是6、10、14、18„„个数相加得来，这样才能得到奇数，根据高斯求和公式，这样的和必有奇数因子

综上：只有2的乘方、素数、小于6的自然数，不是囧数 */

#include using namespace std; bool check(long tar){ bool flag = false; if(tar<6)flag = false;

else { if(tar%2==0){//偶数是否是2的阶乘 while(tar%2==0)tar/=2; tar==1?flag=false:flag=true; }

else {//奇数是否是素数 double end = tar; for(int i=3;i<=sqrt(end);i+=2){ if(tar%i==0){flag = true;break;} else continue; } } } return flag; }

int main(){ int tar;cin>>tar; bool flag = check(tar); cout<题目七：（10分）

现有一个固定的正方形区域，可以把它看作是一个数据库中的特别的二维码 11101 01001 01101 11011 00100

其中每一位表示黑和白，假设这种二维码容错性只有5%，即只要有1位以上不符合要求就无法识别。

现在输入一个5*5的类似区域（相当于扫描一个二维码），如果在容错范围内，则认为它可识别。如果不是精确匹配，需输出错误位的位置。

#include #include using namespace std; int main(){ int err = 0, j = 0; char a[26]; char b[26]= \"1110101001011011101100100\"; for(int i=0;i<25;i++){ cin>>a[i]; if(a[i]!=b[i]){ j=i; err++;

} } if(err==2)cout<<\"fail\"; else if (err==0)cout<<\"matched\"; else{ int y = (j+1)/5+1; int x = j%5+1; cout<<'('<题目八：（10分）

每个人每天早上都要思考一个问题，这个问题的历史已经悠久得无法追溯，那就是：今天午饭吃什么。

现在有个腻歪的人，他已经妥协于人工智能来解决日常问题，妄图找出吃饭问题的通解 已知：根据区域定位有以下地方可去： 范围1：a品尝坊、b张三疯、c南区食堂 范围2：d北区食堂、e咪哆 范围3：f大小姐的店

根据远近程度和价格因素，希望一周5天去范围1的几率为20%，去范围2的几率为70%，去范围3的几率为10%（理论值）。

请写一段程序，随机输出15个字母（实际值），确定半个月的吃饭问题（不考虑跨平台） 注意：以上概率是指【如果】取输出个数趋近于无穷时的概率，而不是指15次*20%等式四舍五入得到的输出结果。

#include

#include//linux /dev/random //#include using namespace std; /*

float set_rand(){

srand(time_t(time(NULL)));//低精度取种，需循环辅助 float r = rand()%1000; return r/10;//.000-.999 } */

float SetRand(){ LARGE_INTEGER Start; QueryPerformanceCounter(&Start); srand((long)Start.LowPart);//高精度取种 long RndNum = rand()%1000; return (float)RndNum/1000;//.000-.999 } int main(){ for(int i=0;i<15;i++){

}

if(SetRand()<=.2){ if(SetRand()<=1/3)cout<<'a'; else if(SetRand()>2/3)cout<<'c'; else cout<<'b'; } else if(SetRand()>.9)cout<<'f'; else { if(SetRand()<=.5)cout<<'d'; else cout<<'e'; } }

return 0;

题目九：（10分）

约瑟夫是一名犹太历史学家。他在自己的日记中写道，他和他朋友与39个战友（共41人）被罗马包围在洞中。他们讨论是自杀还是被俘，最终决定自杀。

自杀规则规定，所有人围成一个圈，由一人开始报数，报到3的被杀死，下面的人继续从1报数，约瑟夫终和他的朋友活了下来。

问：最初约瑟夫和他的朋友占据这个队伍的位置各为第几个？

无脑穷举，结果16、31 #include using namespace std; int main(){ int j=0; int s=0;//jmp 3 int n[41]; for(int i=0;i<41;i++)n[i]=1; for(int i=0;j<39;i++){ if(i==41)i=0; s+=n[i]; if(s==3){ s=0; n[i]=0; j++; } } for(int i=0;i<41;i++)if(n[i]==1)cout<题目十：（10分）

设计一个算法，计算输出1至这个自然数间‘1’共出现了几次，如1-11间‘1’出现了4次。假设数在int范围内，不考虑效率。（若算法效率足够高可先至14题） int count(int n){ int i = 0; while(n != 0){

i += (n % 10 == 1)?1:0; n/=10; } return i; }

int f(int n){ int c = 0; for (int i = 1;i<=n;i++){ c += count (i); } return c; }

题目十一：（15分）

假设5*4的代表一个逆时针旋转的字母区域，输入长宽，打印一个类似的字母区域，乘积若超过26继续由新一组的A、B、C„„填充，不要求输出边框，例如5*4的样式如下： A B C D E N O P Q F M T S R G L K J I H

#include #include #define N 100 char a[N][N];

int direction[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//左、右、下、上的顺序 int main() {

//freopen(\"in.txt\

int i,j,n,m,next_i,next_j,x,ch,count; while(scanf(\"%d%d\{

i=j=next_i=next_j=x=ch=count=0; memset(a,' ',sizeof(a)); while(counta[i][j]='A'+ch%26;

next_i=i+direction[x][0]; next_j=j+direction[x][1];

if(a[next_i][next_j]!=' '||next_i<0||next_i>=n||next_j<0||next_j>=m) {

x=(x+1)%4;//按顺序向其他方向 next_i=i+direction[x][0]; next_j=j+direction[x][1]; } ch++; count++;

i=next_i; j=next_j; }

for(i=0;ifor(j=0;jprintf(\"%4c\ printf(\"\\n\"); } }

return 0; }

题目十二：（15分）

设计一个函数f($a,$b)，其中“$a,$b”代替一个无限循环小数，$a为固定部分，$b为循环体。要求输出一个“x/y”的最简分数表达这个有理数，并测试-13.14(135)=-48623/3700

#include #include

using namespace std; int cal(int x,int y){

return (!y)?x:cal(y,x%y); }//辗转相除

void f(float s,char loop[]){

int sign=1;abs(s)==s?NULL:sign=-1; long n3=0;int i=0;

for(;loop[i]!='\\0';i++)n3=loop[i]-'0'+n3*10;//char[] to usigned long long m3 = pow(10,(float)i)-1; s=abs(s);

long n2=1,m2=1;float temp=s; for(int j=0;;j++){

long dj=(long)temp;

if(temp==(long)dj)break; temp=s*pow(10,(float)j); m2=pow(10,(float)(j)); }n2=temp; ;

long m1=m2*(m2*m3);

long n1=n3*m2+n2*(m2*m3); long h=cal(m1,n1);

m1/=h;n1/=h*sign;s*=sign;

cout<int main(){

f(-13.14,\"135\"); return 0; }

题目十三：（15分）

输入4个坐标（前3个互不相同，且不共线），判断第4个点与前3个点所组成的三角形的位置关系（内、外、上）。

#include #include

using namespace std; struct point{ double x,y; };

double len(point A,point B){

return sqrt(pow((A.x-B.x),2)+pow((A.y-B.y),2)); }

double area(point A,point B,point C){//海式

1/2*abs((A.x*B.y+B.x*C.y+C.x*A.y)-(A.x*C.y+B.x+A.y+C.x*B.y));//vector double a = len(B,C); double b = len(C,A); double c = len(A,B); double p = .5*(a+b+c);

return sqrt((p-a)*(p-b)*(p-c)*p); }

int flag(point A,point B,point C,point D){ double ABC = area(A,B,C); double ABD = area(A,B,D); double ACD = area(A,C,D); double BCD = area(B,C,D);

cout<return abs(ABD+ACD+BCD-ABC)>=1E-5?-1:(ABD||ACD||BCD?1:0); /*

相加与ABC不等在ABC外，返回-1

此处表示ABD+ACD+BCD与ABC误差超过10^-5，则说明在外 由于double开根导致精度损失，如要克服可以用行列式算法 相加与ABC相等，如果其中一个面积为0，则在线上，返回0 相加与ABC相等，如面积为0，则在ABC内，返回1 */ }

int main(){

point A,B,C,D;

cin>>A.x>>A.y;cout<>B.x>>B.y;cout<>C.x>>C.y;cout<>D.x>>D.y;cout<题目十四：（15分）

1至1,000,000,000间‘1’共出现了几次（3s内）。

#include long f(long n){

long j(0),f(1);//counter,factor

long l(0),h(0),c(0);//low,high,current while(n/f!=0){ l=n-(n/f)*f;

//cout<c==0?j+=h*f:(c==1?j+=h*f+l+1:j+=(h+1)*f); /*

curr=0 counter=High*factor curr=1 counter=High*(factor+1) 2f*=10;//l2h }

return j; }

int main(){

std::cout<题目十五：（15分）

已知在国际象棋中，女皇的走法是：可以像车一样控制整排横纵方向格子，也可以像象一样控制斜排（并且没有距离上的） 如果给定一个n*n的国际象棋棋盘，我们要求解“在棋盘上放上n个皇后使它们互相不阻挡各自的行进路线”的摆法，即任何一组“横竖斜”上有且仅有一个皇后 问题：n=8时，是否有解？ 如果无解请输出“no answer”

如果有解请按例子格式输出整个棋盘 如有多组解，仅输出其中一组 例：

假设题中n=3，no answer 假设题中n=4，输出 0010 1000 0001 0100

（1处有皇后0处空白）