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

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<std::cout<<\"\\n\";

}

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<j++;

}

time++;

}

cout<<\"total: \"<<}

题目三：（5分）

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

例如2992

10进制：2992 2+9+9+2 = 22

.

进12.

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<.

.

j++;

}

}

cout<return 0;

}

第二阶段题目：

题目一：（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<return 0;

}

题目三：（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\"<cin>>p;

}

.

.

if(n!=0) {

if(n!=1)cout<<5-p<else {

cout<<\"PC wins\";

break;

}

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<return 0;

}

题目七：（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<<'('<}

return 0;

.

.

}

题目八：（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<.

.

return 0;

}

题目十：（10分）

设计一个算法，计算输出1至这个自然数间‘1’共出现了几次，如1-11间‘现了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){

.

1’出

.

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(count{

.

.

a[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;i{

for(j=0;jprintf(\"%4c\j]);

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<cin>>B.x>>B.y;cout<cin>>C.x>>C.y;cout<cin>>D.x>>D.y;cout<cout<.

.

return 0;

}

题目十四：（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=(n/f)%10;

h=n/(f*10);

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)

2*/

f*=10;//l2h

}

return j;

}

int main(){

std::cout<return 0;

}

题目十五：（15分）

.

.

已知在国际象棋中，女皇的走法是：可以像车一样控制整排横纵方向格子，也可以像象一样控制斜排（并且没有距离上的）

如果给定一个n*n的国际象棋棋盘，我们要求解“在棋盘上放上n个皇后使它们互相不阻挡各自的行进路线”的摆法，即任何一组“横竖斜”上有且仅有一个皇后

问题：n=8时，是否有解？

如果无解请输出“no answer”

如果有解请按例子格式输出整个棋盘

如有多组解，仅输出其中一组

例：

假设题中n=3，no answer

假设题中n=4，输出

0010

1000

0001

0100

.

.

（1处有皇后0处空白）

.