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
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<
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< 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<
int main(){
for(int he=15;he<=96;he++)
for(int s=1;s<=9;s++)
if(he*he==100*s+he)
std::cout<
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<=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<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]= "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<<'('<协于人工智能来解决日常问题，妄图找出吃饭问题的通解
已知：根据区域定位有以下地方可去：
围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<t围，不考虑效率。（若算法效率足够高可先至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","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||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个无限循环小数，$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<
#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<=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<
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<0;
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