3.-简单计算题(二)

第三讲简单计算题（二）ACM算法与程序设计数学科学学院：汪小平[e-mail]2/55CDOJ_1365木杆上的蚂蚁=1365Description在一根细木杆上，有一些速度相同蚂蚁，它们有的往左走，有的往右走，木杆很细，只允许一只蚂蚁通过，所以当两只蚂蚁碰头的时候，它们会掉头继续前进，直到走出边界，掉下木杆。已知木杆的长度和每只蚂蚁的名字、位置和初始方向，问依次掉下木杆的蚂蚁花费的时间以及它的名字。3/55Input输入包含多组测试数据。第一行包含一个整数T(T=20)，代表测试数据组数。每组测试数据的第一行包含两个整数NL，表示有N只蚂蚁(N=100)，木杆长度为L(L=1000)。假设蚂蚁每秒前进一个单位距离，掉头转向的时间忽略不计。以下N行，每行依次为蚂蚁的名字（长度不超过10，仅由英文字母组成），初始位置p（0pL，整数，表示蚂蚁离木杆最左端的距离），初始方向（一个字符，L表示向左，R表示向右），以单个空格分隔，数据保证初始不会有两只蚂蚁在同一个位置。4/55Output对于第k组测试数据，首先输出一行为“Case#k:”。然后输出N行，给出依次掉下木杆的蚂蚁花费的时间以及它的名字，以单个空格分隔。（按照掉下木杆的先后顺序输出，数据保证不会有两支蚂蚁同时掉下木杆）。SampleInput225GG1LMM3R25GG1RMM2LSampleOutputCase#1:1GG2MMCase#2:2GG4MM5/55#includecstdio#includealgorithm//因为要用sort算法#defineN100usingnamespacestd;//必须引用名字空间stdstructant_type{intpos;charname[11];}ants[N];structevent_type{intdrop_time;chardir;}events[N];boolcmp_ant(constant_type&p,constant_type&q){returnp.posq.pos;}6/55boolcmp_event(constevent_type&p,constevent_type&q){returnp.drop_timeq.drop_time;}intmain(){chardir[2];inti,k,n,L,R,T;scanf(%d,&T);for(k=1;k=T;k++){scanf(%d%d,&n,&L);for(i=0;in;i++){scanf(%s%d%s,ants[i].name,&ants[i].pos,dir);events[i].dir=dir[0];events[i].drop_time=(dir[0]=='L'?ants[i].pos:L-ants[i].pos);}7/55sort(ants,ants+n,cmp_ant);sort(events,events+n,cmp_event);printf(Case#%d:\n,k);L=0;R=n-1;for(i=0;in;i++){if(events[i].dir=='L'){printf(%d%s\n,events[i].drop_time,ants[L].name);L++;}else{printf(%d%s\n,events[i].drop_time,ants[R].name);R--;}}}return0;}8/55往届校赛题目精选CDOJ_10048球胜负(eight)=10049/55•Description8球是一种台球竞赛的规则。台面上有7个红球、7个黄球以及一个黑球，当然还有一个白球。对于本题，我们使用如下的简化规则：红、黄两名选手轮流用白球击打各自颜色的球，如果将该颜色的7个球全部打进，则这名选手可以打黑球，如果打进则算他胜。如果在打进自己颜色的所有球之前就把黑球打进，则算输。如果选手不慎打进了对手的球，入球依然有效。现在给出打进的球（白球除外）的顺序，以及黑球由哪方打进，你的任务是判定哪方是胜者。假设不会有一杆同时打进一颗黑球和其他彩球。10/55•Input输入包含多组数据。每组数据第一行是一个整数N(1=N=15)，表示打进的球的个数，N=0表示结束。随后有一行，包含N个字符，依序表示打进的是何种球。如果是’B’，表示是红方打进的黑球，如果是’L’，表示是黄方打进的黑球。如果是’Y’则表示是黄球，’R’表示红球。字符间没有空格。所有输入都满足如下条件：最后一颗球打进时这局比赛正好结束，而且打进的红球和黑球都不超过7个。•Output对每组数据，输出一行。如果红方胜，输出’Red’；黄方胜，输出’Yellow’。11/55•SampleInput5RYRRB9RRRRYRRRB0•SampleOutputYellowRed12/55•2008年校赛最简单的题目。•只需要判断最后一个球是谁打进的，然后统计这个人自己的球是不是已经全部打进了，就可以得到答案。13/55#includecstdio#includecstringintmain(){charstr[30];inti,n,cnt,k;boolflag;while(1){scanf(%d,&n);if(n==0)break;scanf(%s,str);k=strlen(str)-1;//最后一个球下标if(str[k]=='B')//最后一个球是红方打进的黑球{cnt=0;for(i=0;ik;i++)if(str[i]=='R')cnt++;//统计黑球之前进了几个红球if(cnt==7)flag=true;//进了7个红球则红方胜elseflag=false;//否则黄方胜}14/55else//最后一个球是黄方打进的黑球{cnt=0;for(i=0;ik;i++)if(str[i]=='Y')cnt++;//统计黑球之前进了几个黄球if(cnt==7)flag=false;//进了7个红球则黄方胜elseflag=true;//否则红方胜}if(flag)printf(Red\n);elseprintf(Yellow\n);}return0;}15/55CDOJ_1005点球大战(penalty)=100516/55•Description在足球比赛中，有不少赛事，例如世界杯淘汰赛和欧洲冠军联赛淘汰赛中，当比赛双方经过正规比赛和加时赛之后仍然不分胜负时，需要进行点球大战来决定谁能够获得最终的胜利。点球大战的规则非常简单，两方轮流派出球员罚点球，每方各罚5个。当5轮点球结束以后如果仍然不分胜负，则进入一轮定胜负的阶段。两方各派一名球员罚点球，直到有一方罚进而另一方没有进为止。在北美职业冰球联赛中，也有点球大战。与足球的规则不同的是，它只先罚3轮点球，随后就进入一轮定胜负的阶段，而其他的规则完全一样。在本题中，输入将给出每次点球是否罚进，而你的任务则是输出一个“比分板”。17/55•Input输入包含多组数据。每组数据的第一行包含一个整数N(1=N=18)，表示双方总共罚了多少个点球，N=0表示输入结束。随后有N行，每行是一个如下形式的字符串：XXXXgood：表示这个点球罚进或者XXXXnogood：表示这个点球没有罚进其中XXXX表示球员名字（全部由字母和空格组成，保证不会出现歧义）每一行保证不超过100个字符。XXXX和good以及XXXX和no、no和good之间保证有且只有1个空格。good、nogood都是小写。本题是大小写相关的。数据不保证点球大战一定结束，也不保证在结束以后立即结束这组数据（即：不用判断点球大战是否结束，只用把罚进的点球往比分上加即可）。•Output对每组数据，输出一个比分板。一个点球如果罚进，则在对应的地方标上’O’，如果没有进则标上’X’。先罚球的队伍的信息在上面，后罚的在下面。最右边标上两队的比分。具体格式参考样例输出。注意如果一轮点球只罚了一个，则后面那个点球对应的地方写上’-’。18/55•SampleInput6RiisegoodBallackgoodGerrardnogoodLampardnogoodFernandoTorresgoodMaloudagood9ChristianoRonaldonogoodMessinogoodGiggsgoodAbidalnogoodCarrickgoodRonaldinhogoodRooneygoodHenrynogoodTevezgood0•SampleOutput123ScoreOXO2OXO212345ScoreXOOOO4XXOX-119/55•名字可以包含空格，甚至可以包含no、good（事实上，大部分数据都包含no和good中的至少一个），所以此题比较好的处理方法是找跳过名字，直接找倒数第二个单词，看它是不是no，是就是没踢进，反之就是踢进；•数据可能很诡异，比如有两种特殊情况，一种是只有一个good，另一种是直接nogood。这两组数据不是太满足题意（第一组名字为空，第二组有歧义）•空格数要和样例输出一样，否则很可能会被判为“格式错误”(PresentationError)。20/55#includecstdio#includecstringbooljudge(char*str){intpos=strlen(str)-1;while(str[pos]!='')pos--;//从一行字符串的最后开始向前寻找第一个空格str[pos]='\0';pos--;while(str[pos]!='')pos--;//继续向前寻找第二个空格if(strcmp(str+pos+1,no)==0)return0;return1;}参考源代码21/55intmain(){inti,j,n;while(1){scanf(%d,&n);//扫描双方罚点球的人数if(n==0)break;intboard[15][2]={0};//至多15个回合，每回合两队各罚一次charstr[110];gets(str);str[0]='';for(i=0;in;i++){gets(str+1);//扫描一行罚点球信息if(judge(str))//判断是否踢进点球board[i/2][i%2]=1;//1或2表示踢进，否则为0elseboard[i/2][i%2]=2;}参考源代码22/55intcnt[2]={0};//存放两队点球比分for(i=0;i(n+1)/2;i++)printf(%d,i+1);//输出点球进行的回合数量，之间空格隔开printf(Score\n);for(i=0;i2;i++){for(j=0;j(n+1)/2;j++){if(board[j][i]==1){printf(O);cnt[i]++;}elseif(board[j][i]==2)printf(X);elseprintf(-);}printf(%d\n,cnt[i]);}}return0;}23/55CDOJ_1048Clock=1048•DescriptionClockisinventedbyancientArabicengineersandwhichcontributestobuildtheconceptofaccuratetimeforushumanbeingsandevencouldbeessentialtoolthatwidelyusedinindustry,businessandourroutinelives.Nevertheless,theideologyofclockturnsou