第三届ACM竞赛试题

第三届ACM竞赛试题

第一届河南省赛区ACM/ICPC国际大学生程序设计竞赛试题(1)

考试时间：5小时（9：00~14：00）

分数公布：共8题，满分800分。

文件命名：程序文件名为：T题号。例如：若用C语言，第二题应提交：T2.c

【试题一】

灾区已经非常困难，灾民需要帐篷、衣物、食品和血浆。可通往灾区的道路到处都是塌方，70%以上的路面损毁，桥梁全部被毁。中国空军立即启动应急预案，展开史上最大强度非作战空运行动，准备向灾区空投急需物资。由于余震不断，天气恶劣，怎么知道空投的物资是否落在某灾区的区域内？

经过空中观测，多数灾区为一圆形，空投的物资落在p（Xj,Yj）点。你能否给出一个正确的判断？

【标准输入】

第一行：N M (N为灾区数，M为空投物资数)

接下来N行：Xi0 Yi0 Ri (Xi0,Yi0)为圆心坐标，Ri为圆半径i=1，2，3，... ，N 接下来M行：Xi Yi (Xi, Yi)为空投物资的坐标 j=1,2,3,...,M

【标准输出】

输出有M行，一行输出YES

或者NO (若物资落在某个圆上或圆内，输出YES否则为NO)

【约束条件】

(1) 1<=N<=3 2<=M<=10

(2) Ri 是一个整数 Ri<=50 i=1,2,3,..,N

(3) 所有的圆心坐标和物资的坐标都为整数 范围在[-100,100]内

(4) 时间限制:1000MS

【 样 例 】

标准输入

2 3

0 0 20

-70 30 50

10 10

-30 60

第三届ACM竞赛试题

30 30

标准输出

YES

YES

NO

第三届河南省大学生程序设计竞赛

主办：河南省计算机学会

承办：河南理工大学

（正式赛）

地点：河南理工大学

时间：2010年5月16日

所有的题目 时间限制： 1秒

【试题一】 房间安排

2010年上海世界博览会（Expo 2010），是第41届世界博览会。于2010年5月1日至10月31日期间，在中国上海市举行。本次世博会也是由中国举办的首届世界博览会。上海世博会以“城市，让生活更美好”（Better City, Better Life）为主题，将充分探索21世纪城市生活。

这次世博会总投资达450亿人民币，创造了世界博览会史上最大规模记录。吸引200个国家和国际组织参展。预计有7000万人次的参观者。

为了更好地接待在这期间来自世界各地的参观者，如何合理安排各宾馆的住房问题提到了日程。组委会已接到了大量的客房住宿定单，每张定单的内容包括要住宿的房间数，开始住宿时间和要住的天数。为了便于整个城市各宾馆的管理，组委会希望对这些定单进行安排，目的是用尽可能少的房间来满足这些定单，以便空出更多的房间用于安排流动游客。

组委会请求DR. Kong来完成这个任务，对这些定单进行合理安排，使得满足这些定单要求的房间数最少。

假设：某个定单上的游客一旦被安排到某房间，在他预定住宿的期间内是不换房间的。为了简化描述，定单上的开始住宿时间为距离现在的第几天。例如，定单为（10，30，5）表示游客要求使用10个房间，第30天开始连住5天。

第三届ACM竞赛试题

【标准输入】

第一行： N 表示定单数

接下来有N行，每行有三个整数 A B C 表示房间数，开始住宿时间和天数

【标准输出】

输出一个整数，为满足所有定单要求的最少房间数。

【约束条件】

1≤N≤10000 1≤A≤10，1≤B≤180， 1≤C≤10

【 样 例 】

标准输入 标准输出

3 7

3 10 4

4 9 3

3 12 6

【试题二】

素 数

走进世博园某信息通信馆，参观者将获得前所未有的尖端互动体验，一场充满创想和喜悦的信息通信互动体验秀将以全新形式呈现，从观众踏入展馆的第一步起，就将与手持终端密不可分，人类未来梦想的惊喜从参观者的掌上展开。

在等候区的梦想花园中，参观者便开始了他们奇妙的体验之旅，等待中的游客可利用手机等终端参与互动小游戏,与梦想剧场内的虚拟人物Kr. Kong进行猜数比赛。当屏幕出现一个整数X时，若你能比Kr. Kong更快的发出最接近它的素数答案，你将会获得一个意想不到的礼物。

例如：当屏幕出现22时，你的回答应是23；当屏幕出现8时，你的回答应是7；若X本身是素数，则回答X；若最接近X的素数有两个时， 则回答大于它的素数。

【标准输入】

第一行： N 要竞猜的整数个数

接下来有N行， 每行有一个正整数 X

【标准输出】

输出有N行，每行是对应X的最接近它的素数。

【约束条件】

1≤N≤5 1≤X≤1000

【 样 例 】

标准输入 标准输出

4 23

22 5

5 19

18 7

8

第三届ACM竞赛试题

【试题三】 网络的可靠性

A公司是全球领先的互联网解决方案提供商，也是 2010 年世博会的高级赞助商。它将提供先进的网络协作技术，展示其 智能+互联 的生活概念，同时为参观者提供高品质的个人体验和互动，以“信息通信，尽情城市梦想”为主题贯穿。借助奇幻的剧场大屏幕和特效，展现信息通信技术的应用前景，通过生动形象的故事，向观众展示沟通无限制的未来社会前景。 为此，A公司为世博园的N个区域建立了视频通信系统，其中每个区域建立一个基站，编号依次为1，2， ，N。通过基站之间的通信线路为各区域的参观者提供视频服务。 已知在各基站之间已铺设了一些光纤通讯线路，这些线路覆盖了所有区域，即任意两个区域都可以进行视频传递。但为了节约成本开支，目前只铺设了N-1条线路，同时为了减轻各基站的信息传递负载，每个基站最多有三条光纤通讯线路与之连接。

但在通信系统试运行期间, A公司发现当某个基站发生故障时,会导致其它区域之间无法进行信息传递。为了提高该通信网络的可靠性，A公司准备在基站之间再新铺设一些光纤线路，使得任意一个基站故障后，其它基站之间仍然可以通讯。

由于铺设线路的成本昂贵，A公司希望新增设的光纤线路越少越好。A公司请求Dr. Kong来完成这个任务。

【标准输入】

第一行： N 表示有N个基站

接下来有N-1行： X Y 表示第X个基站与第Y个基站直连

【标准输出】

输出一个整数， 表示至少需新铺设的光纤线路数。

【约束条件】

1≤ N ≤ 10000 （线路是双向通信的）

【 样 例 】

标准输入 标准输出

8 3

1 3

3 2

5 3

5 4

5 6

2 7

2 8

【试题四】

虚拟城市之旅

展馆是未来城市的缩影，个人体验和互动是不变的主题。在A国展馆通过多维模式和高科技手段，引领参观者在展示空间踏上一段虚拟的城市之旅。

梦幻国有N个城市和M条道路，每条道路连接某两个城市。任意两个城市之间最多只有一条道路直接相连。这M条道路中有一部分为单向通行的道路 …… 此处隐藏：9182字，全部文档内容请下载后查看。喜欢就下载吧 ……