请选择 进入手机版 | 继续访问电脑版

Lazarus中文社区

 找回密码
 立即注册

QQ登录

只需一步,快速开始

版权申明
查看: 3929|回复: 0

第二十二届全国信息学奥林匹克竞赛(2005)第二试

[复制链接]

该用户从未签到

发表于 2010-8-17 17:58:57 | 显示全部楼层 |阅读模式
题目名称                聪聪和可可            小H的聚会                  月下柠檬树
目录                           cchkk                     party                          lemon
可执行文件名             cchkk                     party                          lemon
输入文件名                cchkk.in         party1.in~party10.in           lemon.in
输出文件名               cchkk.out      party1.out~party10.out        lemon.out
试题类型                    传统型                 提交答案型                   传统型
是否有部分分                否                             是                            否
附加文件                       无                     party_check                   无
时限                              1秒                            \                           1秒

提交源程序须加后缀
对于Pascal语言          cchkk.pas       \            lemon.pas
对于C 语言                   cchkk.c         \            lemon.c
对于C++ 语言             cchkk.cpp       \            lemon.cpp

注意:最终测试时,所有编译命令均不打开任何优化开关


题1

聪聪与可可
主文件名:cchkk
【问题描述】
在一个魔法森林里,住着一只聪明的小猫聪聪和一只可爱的小老鼠可可。虽然灰姑娘非常喜欢她们俩,但是,聪聪终究是一只猫,而可可终究是一只老鼠,同样不变的是,聪聪成天想着要吃掉可可。
一天,聪聪意外得到了一台非常有用的机器,据说是叫GPS,对可可能准确的定位。有了这台机器,聪聪要吃可可就易如反掌了。于是,聪聪准备马上出发,去找可可。而可怜的可可还不知道大难即将临头,仍在森林里无忧无虑的玩耍。
小兔子乖乖听到这件事,马上向灰姑娘报告。灰姑娘决定尽快阻止聪聪,拯救可可,可她不知道还有没有足够的时间。
整个森林可以认为是一个无向图,图中有N 个美丽的景点,景点从1 至N编号。小动物们都只在景点休息、玩耍。在景点之间有一些路连接。
当聪聪得到GPS时,可可正在景点M(M≤N)处。以后的每个时间单位,可可都会选择去相邻的景点(可能有多个)中的一个或停留在原景点不动。而去这些地方所发生的概率是相等的。假设有P个景点与景点M相邻,它们分别是景点R、景点S,……景点Q,在时刻T可可处在景点M,则在(T+1)时刻,可可有(见附件1)的可能在景点R,有(见附件1)的可能在景点的可能在景点S,……,有(见附件1)的可能在景点Q,还有(见附件1)的可能停在景点M。
我们知道,聪聪是很聪明的,所以,当她在景点C时,她会选一个更靠近可可的景点,如果这样的景点有多个,她会选一个标号最小的景点。由于聪聪太想吃掉可可了,如果走完第一步以后仍然没吃到可可,她还可以在本段时间内再向可可走近一步。
在每个时间单位,假设聪聪先走,可可后走。在某一时刻,若聪聪和可可位于同一个景点,则可怜的可可就被吃掉了。
灰姑娘想知道,平均情况下,聪聪几步就可能吃到可可。而你需要帮助灰姑娘尽快的找到答案。

【输入格式】
从文件cchkk.in 中读入数据。
数据的第1行为两个整数N 和E,以空格分隔,分别表示森林中的景点数和连接相邻景点的路的条数。
第2行包含两个整数C 和M,以空格分隔,分别表示初始时聪聪和可可所在的景点的编号。
接下来E 行,每行两个整数,第i+2 行的两个整数Ai和Bi表示景点Ai和景点Bi之间有一条路。
所有的路都是无向的,即:如果能从A走到B,就可以从B走到A。
输入保证任何两个景点之间不会有多于一条路直接相连,且聪聪和可可之间必有路直接或间接的相连。

【输出格式】
输出到文件cchkk.out 中。
输出1个实数,四舍五入保留三位小数,表示平均多少个时间单位后聪聪会把可可吃掉。

【输入样例1】
4 3
1 4
1 2
2 3
3 4
【输出样例1】
1.500
【样例说明1】
开始时,聪聪和可可分别在景点1和景点4。
第一个时刻,聪聪先走,她向更靠近可可(景点4)的景点走动,走到景点2,
然后走到景点3;假定忽略走路所花时间。
可可后走,有两种可能:
第一种是走到景点3,这样聪聪和可可到达同一个景点,可可被吃掉,步数为1,概率为二分之一。
第二种是停在景点4,不被吃掉。概率为二分之一。
到第二个时刻,聪聪向更靠近可可(景点4)的景点走动,只需要走一步即和可可在同一景点。因此这种情况下聪聪会在两步吃掉可可。
所以平均的步数是1*二分之一+2*二分之一=1.5步。

【输入样例2】
9 9
9 3
1 2
2 3
3 4
4 5
3 6
4 6
4 7
7 8
8 9
【输出样例2】
2.167
【样例说明2】
森林如下图所示:
(见附件)

【数据范围】
对于所有的数据,1≤N,E≤1000。
对于50%的数据,1≤N≤50。


题2

小 H 的聚会
【任务描述】
小H从小就非常喜欢计算机,上了中学以后,他更是迷上了计算机编程。经过多年的不懈努力,小H 幸运的被选入信息学竞赛省队,就要去他日思夜想的河南郑州参加第22届全国信息学奥林匹克竞赛(NOI2005)。
小H的好朋友小Y和小Z得知了这个消息,都由衷的为他感到高兴。他们准备举办一个party,邀请小H和他的所有朋友参加,为小H庆祝一下。
经过好几天的调查,小Y和小Z列出了一个小H所有好友的名单,上面一共有N个人(方便起见,我们将他们编号为1至N 的整数)。然而名单上的人实在是太多了,而且其中不少人小Y 和小Z 并不认识。如何把他们都组织起来参加聚会呢?
小 Y 和小Z 希望为小H 的N 个好友设计一张联系的网络,这样,若某个人得知了关于聚会的最新情况,则其他人都可以直接或间接得到消息。同时为了尽量的保证消息传递得简单、高效以及最重要的一点:保密(为了给小H 一个惊喜,在party 的筹备阶段这个聚会的消息是绝对不能让他知道的),小Y 和小Z决定让尽量少的好友直接联系:为了保证N个好友都能互相直接或间接联系到,只需要让(N-1)对好友直接联系就可以了。
(图见附件)
显然,名单上的好友也不都互相认识,而即使是两个互相认识的人,他们之间的熟悉程度也是有区别的。因此小Y 和小Z 又根据调查的结果,列出了一个好友间的关系表,表中标明了哪些人是可以直接联系的,而对于每一对可以互相联系的好友,小Y 和小Z 又为他们标出了联系的愉快程度。如3 和4 的关系非常好,因此标记他们之间的联系愉快程度为10;而1 和3 是一般的朋友,则他们的愉快程度要小一些。上面的图1 表示一个N=5 的联系表,其中点表示名单上的好友,边则表示两个好友可以直接联系,边上的数字即为他们联系的愉快程度。
小Y和小Z希望大家都能喜欢这次聚会,因此决定在尽量最大化联系网络的愉快程度:所谓联系网络的愉快程度,即每一对直接联系人之间的愉快程度之和。如在图1 中,加粗的边表示了一个让愉快程度最大联系的网络,其愉快程度为5+6+10+5=26。
然而,如果让某个人直接和很多的人联系,这势必会给他增添很大的负担。因此小Y 和小Z还为每个人分别设定了一个最大的直接联系人数ki,表示在联系网络中,最多只能有ki个人和i直接联系。
还是用图1的例子,若我们为1至5每个点分别加上了ki = 1, 1, 4, 2, 2的限制,则上述方案就不能满足要求了。此时的最优方案如图2所示,其愉快程度为3+6+10+5 = 24。
(见附件)
你能帮小Y和小Z求出在满足限制条件的前提下,愉快程度尽量大的一个联系网络吗?
【输入格式】
输入文件party1.in到party10.in已经放在用户目录中。
每个输入文件的第1行都是两个整数N 和M。N表示小H的好友总数,M表示小Y和小Z列出来的可以直接联系的好友对数。
输入文件的第2行包含N个在[1, N-1]范围内的整数,依次描述k1, k2, …, kN。相邻的两个数字之间用一个空格隔开。
以下M行,每行描述一对可以互相联系的好友,格式为ui vi ci。表示ui和vi可以直接联系,他们的联系愉快程度为ci。
另外,在所有这些数据的最后还有单独的一行包括一个(0, 1]范围内的实数d作为评分系数。你的程序并不需要去理会这个参数,但你可以根据这个参数的提示去设计不同的算法。有关d的说明,可以参见后面的评分方法。
【输出格式】
本题是一道提交答案式的题目,你需要提供十个输出文件从party1.out 到party10.out。
每个文件的第1行为一个整数,表示你找到的最大的愉快程度。
以下(N-1)行,描述这个网络。每行一个数ei,表示在网络中,让输入文件中第(ei + 2)行描述的一对好友直接联系。

【输入样例】
5 6
1 1 4 2 2
1 2 5
1 3 3
2 3 6
2 5 3
3 4 10
4 5 5
0.00001
【输出样例】
24
2
3
5
6
【样例说明】
详见任务描述中的例子。

【评分方法】
本题设有部分分,对于每一个测试点:
Ø 如果你的输出方案不合法,即ei不符合范围或ei有重复或网络不连通等,该测试点得0分。
Ø 如果你输出的方案和输出文件第1 行的愉快程度不一致,该测试点得0分。
Ø 否则该测试点得分按如下方法计算:设
(见附件)
   如果你的结果小于a,该测试点得0分;
   如果你的结果大于b,该测试点得15分;
   否则你的得分为(见附件)

其中的d 为评分系数(输入数据中最后一行的实数),our_ans 为我们提供的参考解答,your_ans 为你的答案。

【你如何测试自己的输出】
我们提供party_check这个工具作为测试你的输出文件的办法。使用这个工具的方法是在控制台中输入:
./party_check <测试点编号X>
在你调用这个程序后,party_check将根据输入文件partyX.in和你的输出文件partyX.out 给出测试的结果,其中包括:
♢Error: Not connected:你的程序输出的联系网络不连通;
♢Error: Edge xxx is duplicated:第xxx条边被输出了两次;
♢Error: Edge in Line xxx is out of range:你的程序在第xxx行输出的边的编号不在[1, M]范围内;
♢Error: Degree of Friend xxx is out of range:在联系网络中,和编号为xxx的好友直接联系的人超过了限制;
♢Error: Scheme & happiness mismatch:方案和第一行的愉快程度不一致;
♢测试程序非法退出:其他情况;
Correct! Happiness = xxx:输出正确。


题3

月下柠檬树
主文件名:lemon
【问题描述】
李哲非常非常喜欢柠檬树,特别是在静静的夜晚,当天空中有一弯明月温柔地照亮地面上的景物时,他必会悠闲地坐在他亲手植下的那棵柠檬树旁,独自思索着人生的哲理。
李哲是一个喜爱思考的孩子,当他看到在月光的照射下柠檬树投在地面上的影子是如此的清晰,马上想到了一个问题:树影的面积是多大呢?
李哲知道,直接测量面积是很难的,他想用几何的方法算,因为他对这棵柠檬树的形状了解得非常清楚,而且想好了简化的方法。
李哲将整棵柠檬树分成了n 层,由下向上依次将层编号为1,2,…,n。从第1到n-1 层,每层都是一个圆台型,第n 层(最上面一层)是圆锥型。对于圆台型,其上下底面都是水平的圆。对于相邻的两个圆台,上层的下底面和下层的上底面
重合。第n 层(最上面一层)圆锥的底面就是第n-1 层圆台的上底面。所有的底面的圆心(包括树顶)处在同一条与地面垂直的直线上。李哲知道每一层的高度为h1,h2,…,hn,第1 层圆台的下底面距地面的高度为h0,以及每层的下底面的圆的
半径r1,r2,…,rn。李哲用熟知的方法测出了月亮的光线与地面的夹角为alpha。
(见附件)
为了便于计算,假设月亮的光线是平行光,且地面是水平的,在计算时忽略树干所产生的影子。李哲当然会算了,但是他希望你也来练练手。

【输入格式】
从文件lemon.in 中读入数据。
文件的第 1 行包含一个整数n 和一个实数alpha,表示柠檬树的层数和月亮
的光线与地面夹角(单位为弧度)。
第2行包含n+1个实数h0,h1,h2,…,hn,表示树离地的高度和每层的高度。
第3行包含n个实数r1,r2,…,rn,表示柠檬树每层下底面的圆的半径。
上述输入文件中的数据,同一行相邻的两个数之间用一个空格分隔。
输入的所有实数的小数点后可能包含1至10 位有效数字。

【输出格式】
将你的结果输出到文件lemon.out 中。
输出1个实数,表示树影的面积。四舍五入保留两位小数。

【输入样例】
2 0.7853981633
10.0 10.00 10.00
4.00 5.00
【输出样例】
171.97

【数据范围】
1≤n≤500,0.3<alpha<π/2,0<hi≤100,0<ri≤100。
10%的数据中,n=1。
30%的数据中,n≤2。
60%的数据中,n≤20。
100%的数据中,n≤500。

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
回复

使用道具 举报

QQ|手机版|小黑屋|Lazarus中国|Lazarus中文社区 ( 鄂ICP备16006501号-1

GMT+8, 2021-4-18 07:01 , Processed in 0.064412 second(s), 25 queries .

Powered by Discuz! F1.0 Build 20160930

© 2001-2021 Comsenz Inc. & Discuz! Fans

快速回复 返回顶部 返回列表