第一届河南省ACM竞赛正式赛.docx
- 文档编号:17971355
- 上传时间:2023-08-05
- 格式:DOCX
- 页数:13
- 大小:28.59KB
第一届河南省ACM竞赛正式赛.docx
《第一届河南省ACM竞赛正式赛.docx》由会员分享,可在线阅读,更多相关《第一届河南省ACM竞赛正式赛.docx(13页珍藏版)》请在冰点文库上搜索。
第一届河南省ACM竞赛正式赛
863软件园杯
第一届河南省大学生程序设计竞赛
(正式比赛试题)
主办:
河南省计算机学会
承办:
郑州大学信息工程学院
协办:
YOCSEF郑州分论坛
地点:
郑州大学南校区软件学院
时间:
2008年5月18日
考试时间:
5小时(9:
00~14:
00)
分数分布:
共8题,满分800分。
文件命名:
程序文件名为:
T题号。
如第二题应提交:
T2.c
5月12日14时28分,四川汶川县发生了7.8级地震。
突如其来的地震灾害,把全国人民和灾区人民的心紧紧连在一起。
中共中央政治局常务委员会召开会议,全面部署当前抗震救灾工作。
会议强调,灾情就是命令,时间就是生命。
各有关部门一定要紧急行动起来,把抗震救灾作为当前的首要任务,一方有难、八方支援,想一想,我们选手能为灾区做点什么?
【试题一】
灾区已经非常困难,灾民需要帐篷、衣物、食品和血浆。
可通往灾区的道路到处都是塌方,70%以上的路面损坏,桥梁全部被毁。
中国空军立即启动应急预案,展开史上最大强度非作战空运行动,准备向灾区空投急需物资。
由于余震不断,天气恶劣,怎样知道空投的物资是否落在某灾区的区域内呢?
经过空中观测,某灾区为一凸多边形,空投的物资落在P(X,Y)点。
你能否给出一个正确判断?
【标准输入】
第1行:
NXY(N为凸形的边数,X,Y为空投物资的坐标)
第2行:
X1Y1X2Y2…….XnYn(逆序给出的N个顶点坐标)
【标准输出】
YES(物资落在灾区的区域内)
或
NO(物资落在灾区的区域外)
【约束条件】
(1)3≤N≤20
(2)所有的坐标Xi和Yi为整数-10000≤Xi,Yi≤10000
(3)X,Y为整数-10000≤X,Y≤10000
(4)时间限制:
1000MS
【样例】
标准输入
标准输出
422
YES
-103-2109-1110
【试题二】
据不完全统计,受地震影响,四川大部分灾区通信陷入瘫痪,数千个基站因断电、传输中断等原因退出服务,目前总公司已紧急部署对受灾地区进行通信抢修。
按照应急通信保障预案,必须尽快、付出代价最小,效率更高来全力恢复通信。
由于四川大部分灾区都处于山区,有很多基站之间不能直接建立通信。
现已知建立各基站之间直接通信的代价,问如何建立总代价最小的通信网,使得任意两个基站之间都能通信?
【标准输入】
第1行:
N(N为的个数)
第2~N+1行:
Pi1Pi2……Pin(Pij为建立基站i与基站j直接通信的代价
i,j=1,2,….,N)
【标准输出】
T(建立通信网的最小代价数)
【约束条件】
(1)10≤N≤1000
(2)-1≤Pij≤1000Pij为整数,若Pij=-1,表示基站i与基站j不能直接通信
(3)时间限制:
1000MS
【样例】
标准输入
标准输出
5
280
01603020-1
1600200–1–1
3020005080
20–150070
-1–180700
#defineN1000
#defineinf1001
#definetrue1
#definefalse0
#include“stdio.h”
intp[N+1][N+1];
//======================================
longPrim(intn)
{longT=0;inti,j,k,s[N+1];
intlowcost[N+1],closest[N+1];
s[1]=true;//先选择顶点1
for(i=2;i<=n;++i)
{lowcost[i]=p[i][1];closest[i]=1;s[i]=false;}
for(i=1;i {intmin=inf;//设inf为无穷大 j=1; for(k=2;k<=n;++k) if((! s[k])&&(lowcost[k] {min=lowcost[k];j=k;} //prinf(“%d%d\n”,j,closest[j]); T+=p[j][closest[j]];s[j]=true; for(k=2;k<=n;++k)//调整未加入顶点的最小边 if((! s[k])&&(p[k][j] {lowcost[k]=p[k][j]closest[k]=j;} } returnT;} //============================ intmain() {inti,j,n;longT; scanf(“%d\n”,&n); for(i=1;i<=n;i++) for(j=1;j<=n;j++) {scanf(“%d”,&p[i][j]; if(p[i][j]<=0)p[i][j]=1001;} T=Prim(n); Printf(“ld”,T); } //参见<<算法设计与分析>>P117 【试题三】 密码破译 某组织欲破获一个外星人的密码,密码由一定长度的字串组成。 此组织拥有一些破译此密码的长度不同的钥匙,若两个钥匙的长度之和恰好为此密码的长度,则此密码被成功破译。 现在就请你编程找出能破译此密码的两个钥匙。 【标准输入】 第一行: NN为钥匙的个数(1<=N<=1000) 第二行: LL为密码的长度 以下有N行: Ai每行为一把钥匙的长度i=1,2,……,N 【标准输出】 若无法找到破译此密码的钥匙,则输出0 若找到两把破译的钥匙,则输出文件有两行,分别为两把钥匙的编号,按从小到大输出。 若有多种破译方案,则只输出包含起始编号最小的一组即可。 [【约束条件】 (1)1<=N,L,Ai<=1000(i=1,2,…..,N) (2)时间限制: 1000MS 【样例】 标准输入 标准输出 10 80 27 9 4 73 23 68 12 64 92 16 6 7 【试题四】 在灾区,多数人已经受伤,缺水,少食物,精神处在崩溃的边缘。 很多人的生存条件仅能维持几天。 灾民需要帐篷、衣物、食品和医疗器材、药品等物资。 14日上午,中央军委委员、空军司令员许其亮组织召开空军首长办公会,将空军下一步救灾重点确定为抢救伤员、空投、空运。 空军各部队都派出多架运输机,准备向灾区空运急需物品。 现在已知四种打包过的急需物品重量分别为C1,C2,C3,C4,数量分别为M1,M2,M3,M4包。 一架运输机的载重量为W,现在各部队关心将一架运输机装满共有多少种运载方案,以便调度进行空运。 比如C={100,200,500,1000},M={3,2,3,1},W=1000,一共有4种运载方案: 1000=100+100+100+200+500 1000=100+200+200+500 1000=500+500 1000=1000 【标准输入】 第一行: C1C2C3C4N其中N为空运的部队数 接下来n行: Mi1Mi2Mi3Mi4Wi表示各运载部队需空运的4种物品数量Mi 和各自运输机的载重量Wii=1,2,…..,N 【标准输出】 输出有N行,表示各部队运载物品的方案总数,保证答案在10000范围内 【约束条件】 (1)0 (2)N<=10000 (3)时间限制: 1000MS 【样例】 标准输入 标准输出 125102 4 27 323110 1000222900 【试题五】 从5月12日下午地震发生至今已经超过48小时,根据地震救灾的常识推算,未来24小时将是救灾最后的黄金时间。 时间在无情的流逝,数以万计的灾民依旧命悬喘息之间。 现在,数万军民正日夜奋战在抢救灾民第一线。 从人员的组织协调到救灾物资的后援运输,每一个环节都直接关系到救灾的效果好坏。 由于通往各灾区的道路完全中断,大批救援物资只好空投到各个灾区。 某军区准备了一批物资,恰好能均分到处于环形的N个灾区中。 遗憾的是,由于余震不断,天气恶劣等原因,落到各灾区的数量不相同。 正如温家宝总理所一再强调的“抢救人的生命,是这次救灾工作的重中之重”。 为了保证救灾的效率不会平白消耗,当地的民间救助组织可以选择将落到自己所在区的物资传送到左边或者右边相邻的灾区。 为了公平起见,我们希望通过相邻灾区的相互传送,最终使所有的灾区获得相同数量的物资。 假设一个物资从一个灾区传送到另一个灾区付出的代价是1,问怎样进行传送,使得所付出的总代价最小。 【标准输入】 第一行: N表示处于环形的灾区数 接下来n行: 每行一个整数Ai,表示第i个灾区得到的物质数量。 【标准输出】 输出只有一个数,表示传送物资付出的最小总代价 【约束条件】 (1)N<=1000000 (2)Ai>=0,保证Ai在长整型范围内,Ai的总和在int64/longlong范围内. (3)时间限制: 1000MS 【样例】 标准输入 标准输出 4 4 1 2 5 4 【试题六】TimeLimit: 1000MS 灾情就是命令,时间就是生命,救灾部队要以最快的速度赶到救灾现场。 13日10时,成都军区抗震救灾联合指挥部里,成都军区司令员李世明大声命令: “不管将军还是士兵,告诉大家,谁先到就给谁立功! ” Wemayassumethatallthesoldierexcept"Yongshi"runfromChengdutoWenchuanatafixedspeed.Yongshiisasoldierwithadifferentrunninghabit–healwaystriestofollowanothersoldiertoavoidrunningalone.WhenYongshigetstoChengdu,hewilllookforsomeonewhoissettingofftoWenchuan.Ifhefindssomeone,hewillfollowthatsoldier,orifnot,hewillwaitforsomeonetofollow.OnthewayfromChengdutoWencuan,atanytimeifafastersoldiersurpassedYongshi,hewillleavethesoldierheisfollowingandspeeduptofollowthefasterone. WeassumethedistancefromChengdutoWenchuanis95kilometersandthetimethatYongshigetstoChengduiszero.Giventhesetofftimeandspeedoftheothersoldier,yourtaskistogivethetimewhenYongshiarrivesatWenchuan. 【Input】 Thereareseveraltestcases(<=10testcases).ThefirstlineofeachcaseisN(1<=N<=1000)representingthenumberofsoldier(excludingYongshi).N=0endstheinput.ThefollowingNlinesareinformationofNdifferentsoldiers,insuchformat: ViTi Viisapositiveinteger<=30,indicatingthespeedofthei-thsoldier(kph,kilometersperhour).Tiisthesetofftimeofthei-thsoldier,whichisanintegerandcountedinminutes.InanycaseitisassuredthattherealwaysexistsanonnegativeTi.-1000<=Ti<=1000 【Output】 Outputonelineforeachcase: thearrivaltimeofYongshi.Roundup(ceiling)thevaluewhendealingwithafraction. SampleInputSampleOutput 4214 100271 12-15 1519 3024 2 210 2234 0 【试题七】 Georgetooksticksofthesamelengthandcutthemrandomlyuntilallpartsbecameatmost20unitslong.Nowhewantstoreturnstickstotheoriginalstate,butheforgothowmanystickshehadoriginallyandhowlongtheywereoriginally.Pleasehelphimanddesignaprogramwhichcomputesthesmallestpossibleoriginallengthofthosesticks.Alllengthsexpressedinunitsareintegersgreaterthanzero. 【Input】 Inputconsistsofmultipleprobleminstances.Eachinstancecontainsblocksof2lines.Thefirstlinecontainsthenumberofstickspartsaftercutting,thereareatmost64sticks.Thesecondlinecontainsthelengthsofthosepartsseparatedbythespace.Thelastlineofthefilecontainszero. 【Output】 Theoutputshouldcontainsthesmallestpossiblelengthoforiginalsticks,oneperline. SampleInput 9 521521521 4 1234 0 SampleOutput 6 5 TimeLimit: 1000MS 【试题八】 Anascendingsortedsequenceofdistinctvaluesisoneinwhichsomeformofaless-thanoperatorisusedtoordertheelementsfromsmallesttolargest.Forexample,thesortedsequenceA,B,C,DimpliesthatA 【Input】 Inputconsistsofmultipleprobleminstances.Eachinstancestartswithalinecontainingtwopositiveintegersnandm.thefirstvalueindicatedthenumberofobjectstosort,where2<=n<=26.Theobjectstobesortedwillbethefirstncharactersoftheuppercasealphabet.ThesecondvaluemindicatesthenumberofrelationsoftheformA anuppercaseletter,thecharacter"<"andaseconduppercaseletter.Noletterwillbeoutsidetherangeofthefirstnlettersofthealphabet.Valuesofn=m=0indicateendofinput. 【Output】 Foreachprobleminstance,outputconsistsofoneline.Thislineshouldbeoneofthefollowingthree: Sortedsequencedetermined: yyy…y. Sortedsequencecannotbedetermined. Inconsistencyfound. yyy…yisthesorted,ascendingsequence. SampleInputSampleOutput 46Sortedsequencedetermined: ABCD. A A B C B A 32 A
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第一 河南省 ACM 竞赛 正式