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

.
ACM软件大赛之编程大赛

比赛注意事项：
l 比赛时间为3小时（180分钟）；比赛分两个阶段：第一阶段限时30分钟，完成公示的3题，第二阶段限时150分钟（事先完成第一阶段题目的小组可提前进入第二阶段）；
l 比赛第一阶段的3道题目将在前期宣传中告知参赛选手，比赛第二阶段的题目将由赛事主席当场公布竞赛题目；
l 前两阶段题目分为三个分值（5分、10分、15分），第一阶段3道公示题都为5分；第二阶段总共15道题，根据不同的难度分值不同，分别为5道5分题，5道10分题，5道15分题；第一阶段参赛队员不可参考任何相关资料；第二阶段参赛队员可以携带诸如书，手册，程序清单等参考资料。比赛过程中队员不得携带任何电子媒质的资料；参赛者可以选择自己擅长的语言（C,C++,JAVA等等）进行编写
l 考虑到大一和大二学生的知识掌握程度，大一参加选手一开始就会有10分的分数，最后总分是由所做题目与初始的10分相加得到。
l 每组队员根据安排使用电脑，小组人数为两人的使用一台电脑，超过两人的使用两台电脑，每台的电脑配置完全一样；
l 各小组每做完一题或几题，必须交予评委老师运行，评委老师当场给分；
l 如在比赛中发现作弊等行为，将取消比赛资格。

第一阶段公示题目：
题目一：（5分）
打印以下图形，纵遵从字母顺序，行字符数遵从斐波那契数列
A
B
CC
DDD
EEEEE
FFFFFFFF
GGGGGGGGGGGGG

#include<iostream>
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<<chr;
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<iostream>
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<<n[3]<<n[2]<<":"<<n[1]<<n[0]<<"\n";//test
j++;
}
time++;
}
cout<<"total: "<<j*2
<<endl;
}

题目三：（5分）
10进制的四位数中有几个符合如下特征：将其分别表示为16进制、10进制、12进制，在每种状态下，分别将各个位上的数相加，能得到3个相等10进制数。
例如2992
10进制：2992 2+9+9+2 = 22
12进制：1894 1+8+9+4 = 22
16进制：BB0 11+11+0 = 22

2992-2999

#include<iostream>
#include<cmath>
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<<i<<endl;
j++;
}
}
cout<<j;
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<iostream>
int main(){
for(int he=15;he<=96;he++)
for(int s=1;s<=9;s++)
if(he*he==100*s+he)
std::cout<<he*he<<endl;
return 0;
}

题目三：（5分）
有4条狗A、B、C、D，他们分别在一条100m的公路上步行，速率均为5m/s，A初始在30m处，B初始在65m处，C初始在75m处，D初始在95m处，初始左右方向是随意的，任意两狗相遇则各自掉头（掉头时间不计，速率保持5m/s）。请问，4条狗最终都离开公路的最大时间是几秒？
#include<iostream>
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<iostream>
#include<cmath>
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<iostream>
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"<<endl;
cin>>p;
}
if(n!=0) {
if(n!=1)cout<<5-p<<endl;
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<iostream>
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<<flag;
return 0;
}

题目七：（10分）
现有一个固定的正方形区域，可以把它看作是一个数据库中的特别的二维码
11101
01001
01101
11011
00100
其中每一位表示黑和白，假设这种二维码容错性只有5%，即只要有1位以上不符合要求就无法识别。
现在输入一个5*5的类似区域（相当于扫描一个二维码），如果在容错围，则认为它可识别。如果不是精确匹配，需输出错误位的位置。

#include<iostream>
#include<cmath>
using namespace std;
int main(){
int err = 0, j = 0;
char a[26];
char b[26]= "01100100";
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<<'('<<x<<','<<y<<')';
}
return 0;
}

题目八：（10分）
每个人每天早上都要思考一个问题，这个问题的历史已经悠久得无法追溯，那就是：今天午饭吃什么。
现在有个腻歪的人，他已经妥协于人工智能来解决日常问题，妄图找出吃饭问题的通解
已知：根据区域定位有以下地方可去：
围1：a品尝坊、b三疯、c南区食堂
围2：d北区食堂、e咪哆
围3：f大小姐的店
根据远近程度和价格因素，希望一周5天去围1的几率为20%，去围2的几率为70%，去围3的几率为10%（理论值）。
请写一段程序，随机输出15个字母（实际值），确定半个月的吃饭问题（不考虑跨平台）
注意：以上概率是指[如果]取输出个数趋近于无穷时的概率，而不是指15次*20%等式四舍五入得到的输出结果。

#include<iostream>
#include<windows.h>//linux /dev/random
//#include<ctime>
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<iostream>
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<<i+1<<endl;
return 0;
}
题目十：（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<iostream>
#include<cstring>
#define N 100
char a[N][N];
int direction[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//左、右、下、上的顺序
int main()
{
//freopen("in.txt","r",stdin);
int i,j,n,m,next_i,next_j,x,ch,count;
while(scanf("%d%d",&n,&m)!=EOF)
{
i=j=next_i=next_j=x=ch=count=0;
memset(a,' ',sizeof(a));
while(count<n*m)
{
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<n;i++)
{
for(j=0;j<m;j++)
printf("%4c",a[i][j]);
printf("\n");
}
}
return 0;
}

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

#include<iostream>
#include<cmath>
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<<s<<"("<<loop<<")="<<n1<<"/"<<m1<<endl;
}
int main(){
f(-13.14,"135");
return 0;
}

题目十三：（15分）
输入4个坐标（前3个互不一样，且不共线），判断第4个点与前3个点所组成的三角形的位置关系（、外、上）。

#include<iostream>
#include<cmath>
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<<endl<<ABD+ACD+BCD-ABC<<endl;
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<<endl;
cin>>B.x>>B.y;cout<<endl;
cin>>C.x>>C.y;cout<<endl;
cin>>D.x>>D.y;cout<<endl;
cout<<flag(A,B,C,D)<<endl;
return 0;
}

题目十四：（15分）
1至1,000,000,000间‘1’共出现了几次（限制3s）。

#include<iostream>
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<<l<<"L"<<endl;//test
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<curr<9 counter=(High+1)*factor
*/
f*=10;//l2h
}
return j;
}
int main(){
std::cout<<f(1E9);
return 0;
}

题目十五：（15分）
已知在国际象棋中，女皇的走法是：可以像车一样控制整排横纵方向格子，也可以像象一样控制斜排（并且没有距离上的限制）
如果给定一个n*n的国际象棋棋盘，我们要求解“在棋盘上放上n个皇后使它们互相不阻挡各自的行进路线”的摆法，即任何一组“横竖斜”上有且仅有一个皇后
问题：n=8时，是否有解？
如果无解请输出“no answer”
如果有解请按例子格式输出整个棋盘
如有多组解，仅输出其中一组
例：
假设题中n=3，no answer
假设题中n=4，输出
0010
1000
0001
0100
（1处有皇后0处空白）

27 / 27