1、NOIP2009全国信息学奥林匹克联赛模拟试题（第三阶段集训） 2009 年 X月 XX日- 1 -BYVoid 魔兽世界邀请赛-NOIP2009 模拟赛 II测试时间：3 小时【题目一览】题号 第一题 第二题 第三题 第四题题目名称 沙漠赛道 美酒节赛羊 地精的贸易 奥术能量环流提交文件 mirage.pas/cpp goat.pas/c/cp goblin.pas/c/cpp arcane.pas/c/cpp输入文件 mirage.in goat.in goblin.in arcane.in输出文件 mirage.out goat.out goblin.out arcane.out时间限制
2、 1s 1s 1s 1s空间限制 64MB 64MB 64MB 64MB分值 100 100 100 100沙漠赛道【问题描述】在闪光平原的沙漠上，侏儒和地精正在进行着竞速比赛。侏儒和地精都把他们最先进的科技应用到了赛车的提速上，唯一的目的就是超越对方，而不考虑危险与否。精彩激烈的比赛吸引了来自艾泽拉斯各地的观众们。他们根据自己的喜好在比赛开始之前对两支队伍投注，胜者将赢得不菲的回报。如果投注的车队胜出，那么投注者可以获得赌注金额的两倍的回报。如果投注的车队落败，那么就没有任何回报了。如果两队平局，每个投注者可以获得所有投注者赌注金额的几何平均数。作为沙漠赛道赌场的老板，你在一开始就获得了两支
3、车队的信息。你已经知道了两个赛车的发动机的动力指数，以及发生各种事故的概率。赛车在行驶的过程中，可能会陷入沙坑，零件损坏，撞击赛道或者被沙漠虫群袭击。每种事故都是致命的，只要赛车发生其中任何一种（或多种）事故，就算是退出比赛了。任何一辆车发生事故，另一辆车就一定获胜，当然如果两辆车都发生事故，那就是平局了。现在，有许多观众已经投注了，请你算出侏儒队和地精队获胜和平局的概率，以及赌场利润的期望。详细说明：下面以一个例子（样例）详细说明。下表是两队发生各种故障的概率。陷入沙坑 零件损坏 撞击赛道 虫群袭击侏儒队 0.05 0.10 0.08 0.12地精队 0.10 0.15 0.04 0.00下
4、表为两队赛车发动机动力指数，我们规定，当两车都不发生事故时，每个队获胜的概率为(该队发动机动力指数 / 两队发动机动力指数和)。动力 概率侏儒 120 120/200=0.6地精 80 80/200=0.4根据以上数据，我们可以算出，侏儒队获胜概率约为 0.4889，地精队获胜概率约为 0.4294，两队平局概率约为 0.0817。下表为观众投注的金额。赛队 侏儒 侏儒 侏儒 侏儒 侏儒 地精 地精 地精 地精 地精金额 100 200 300 400 500 600 500 400 300 100NOIP2009全国信息学奥林匹克联赛模拟试题（第三阶段集训） 2009 年 X月 XX日- 2
5、 -投注总额为 3400，当侏儒获胜时，你要支付 1500*2=3000，利润为 400。当地精获胜时，1900*2=3800，利润为-400。当两队平局时，几何平均数为 290.7692，你要支付290.7692*10=2907.692，利润为 492.308。侏儒胜 地精胜 平局利润 400 -400 492.308概率 P 0.4889 0.4294 0.0817由以上可得，比赛利润的期望：E=400*0.4889+(-400)*0.4294+492.308*0.0817=64.038【输入格式】输入文件中的第一行为四个小于 1的非负实数，表示侏儒队赛车发生各种故障的概率。第二行中为四个
6、小于 1的非负实数，表示地精队赛车发生各种故障的概率。第三行中为两个正整数，表示侏儒队赛车和地精队赛车的发动机动力指数。第四行中为一个整数 N（0=N=100000） ，表示下注的观众的数目。第 5行至第 N+5行，每行有一个正实数和一个整数，表示下注的金额和支持的队伍。其中：0 表示侏儒队，1 表示地精队。注意：1.0=每个赌注金额=100000.0。【输出格式】输出文件中的第一行为三个正实数，分别表示侏儒队获胜概率，地精队获胜概率，平局概率。保留两位小数。第二行中为一个实数，表示利润的期望。保留两位小数。【输入输出样例】输入：0.05 0.10 0.08 0.120.10 0.15 0.0
7、4 0.00120 8010100.0 0200.0 0300.0 0400.0 0500.0 0600.0 1500.0 1400.0 1300.0 1100.0 1输出：0.49 0.43 0.0864.04NOIP2009全国信息学奥林匹克联赛模拟试题（第三阶段集训） 2009 年 X月 XX日- 3 -【概念参考】几何平均数：n 个正实数乘积的 n次算术根。即给定 n个正实数 a1，a2，an，其几何平均数为：(a1*a2*an)(1/n)。期望：数学期望的简称。离散随机变量的一切可能值与对应的概率 P的乘积之和称为数学期望。美酒节赛羊【问题描述】又到了一年一度的艾泽拉斯美酒节，联盟和
8、部落都会用自己的粮食来酿造最好的美酒来庆祝这个节日。山羊大赛一向是美酒节的亮点，冒险者们带着他们从世界各地找来的山羊一起来参加山羊大赛。他们各自骑上自己的山羊，在银月城到剃刀岭的路上比赛驾驭技术，最先到达终点的选手可以获得一笔数额不菲的奖金。比赛的规则是这样的：1参赛的山羊有以下特征：（a）山羊都会疲劳的，它的疲劳度上限为 P；（b）山羊只能有三种行进方式：慢速奔跑，每秒行进 1码，每秒疲劳度减少 1；中速奔跑，每秒行进 5码，每秒疲劳度增加 2；快速奔跑，每秒行进 10码，每秒疲劳度增加 5。2所有选手骑着各自的山羊，同时从起点出发，出发时疲劳度为 0。3如果某一时刻山羊的疲劳度达到了上限，
9、山羊就会进入一个精疲力竭的状态，必须持续至少 10秒的慢速奔跑。4赛道的长度为 S码，首先到达终点的选手为获胜者，嗜财如命的地精们听到这一消息后，想不顾一切得获得奖金。地精总工程师尼克斯斯普克斯宾，用最好的外壳加上最强的地精专用动力装置组装了一个“山羊” 。为了胜过他们的强劲对手侏儒队，他们想在比赛前就知道侏儒队的山羊能在最少多少秒的时间内到达终点。地精雇佣迪菲亚兄弟会的间谍，已经获得了侏儒山羊的疲劳度上限 P。现在地精们找到了你，请你为他们“山羊”的芯片编写一个程序，算出侏儒队能在最少多少秒的时间内到达终点。【输入格式】输入文件中仅一行为两个整数 S，P。【输出格式】输出文件中仅一行为一个整
10、数 T，表示侏儒队最少到达终点的时间。【输入输出样例】输入：50 20输出：10NOIP2009全国信息学奥林匹克联赛模拟试题（第三阶段集训） 2009 年 X月 XX日- 4 -样例说明：下面是一种可能的最优方案。方式 快 慢 中 快时间 1 6 7 10疲劳度 5 0 2 17距离 10 15 20 50【数据范围】对于 30%的数据，满足：S=100；对于 50%的数据，满足：S=300000；对于 100%的数据，满足：S=25000000，P=100。地精的贸易【问题描述】聪明地地精发现，联盟与部落的市场上的某些商品存在着很大的差价。这决定了地精可以从中获取相当可观的利润。然而这个发
11、现还并没有被大部分地精知道，于是年轻的地精菲利克斯决定从事此业。菲利克斯几乎花光了他所有的积蓄购买了一个相当大的飞艇，以及往返于暴风城和银月城之间的各种通行证。暴风城和银月城分别是联盟和部落的商业中心。菲利克斯决定在暴风城购买一些商品，驾驶飞艇到银月城以当地市场价卖掉，然后在银月城买一些商品，驾驶飞艇再回到暴风城卖掉。这样一个来回，菲利克斯可以赚到不少钱。通过商业调查，他已经在出发前就知道了联盟和部落的各种商品的价格。在他现有的资产的前提下，他希望能够在一次旅行中赚取尽可能多的金币。那么请你设计一个程序，为菲利克斯设计一个购买方案，使一次来回能够赚到最多的金币。【输入格式】输入文件中的第一行为
12、两个整数 N，M（1=N=100000，1=M=100） ，表示他在出发前有 N个金币，联盟和部落的市场中都有 M种商品。第二行至第 M+1行，每行有两个整数 Ai，Bi，表示第 i种商品在暴风城的市场价为 Ai，在银月城的市场价为 Bi。【输出格式】输出文件中的第一行为一个整数，表示菲利克斯一次来回最多能够赚到的金币数。最后结果不超过4000000。第二行至第 M+1行，其中：第 i+1行中为第 i个商品的购买方法，输出一个句子：如果要从联盟购买 k个，输出“Buy k from Alliance” ；如果要从部落购买 k个，输出“Buy k from Horde” ；如果不需要购买，输出“
13、Buy 0” ；如果多个的方案赚得的金币都是最大，则输出购买的商品序号最靠前的这种方案。【输入输出样例】NOIP2009全国信息学奥林匹克联赛模拟试题（第三阶段集训） 2009 年 X月 XX日- 5 -输入：23 56 911 73 24 65 3输出：33Buy 3 from AllianceBuy 1 from HordeBuy 0Buy 1 from AllianceBuy 9 from Horde样例说明：初始时，菲利克斯在暴风城，他有 23个金币，这时他购买 3个商品 1，1 个商品 4，花费3*6+1*4=22个金币，剩余 1个金币。到达银月城，他把它们卖掉，可以获得 3*9+1
14、*6=33个金币，赚了11个金币。这时，他用他的 34个金币，在银月城购买 1个商品 2，9 个商品 5，花费 1*7+9*3=34个金币。回到暴风城，卖掉可以获得 1*11+9*5=56个金币，赚了 22个金币。与起始时他的 23个金币相比，他赚了 33个金币。奥术能量环流【问题描述】为了远征诺森德，暴风城正在被改建为一个港口城市。在教堂广场和花园区之间的运河的尽头，有一堵坚固的城墙。然而现在这里却被规划成为了通向港口的唯一途径，于是矮人们正在考虑如何将这堵墙拆掉。这堵墙是在六年前暴风城石工会建成的，当年为了抵抗兽人的入侵而建立的，它被建造得异常坚固。矮人们准备使用尽可能多的炸药炸掉它，但是
15、大主教本尼斯塔九世强烈反对这一愚蠢的做法，因为这样会使大教堂如世界末日来临一般的震动。侏儒们认为把砖一块一块地卸下来是个不错的方法，但是砖与砖之间连接得异常紧密。于是，如何拆掉它便成了一个棘手的问题。聪明的侏儒大工匠梅卡托克带领他的学徒工程师们彻底研究了这一堵墙，他们发现了这堵墙精妙的内部结构。墙内每块砖与其相邻的砖之间由奥术能量连接了起来，连接砖与砖之间的奥术能量是有极性的，发射方向总是从正极指向负极。墙的内部存在着若干个奥术能量环流。所谓奥术能量环流，就是指在由多块砖组成的一个系统中，从每一块砖沿着奥术极性能量的发射方向出发，在该系统中进行若干次传递以后，都能够回到这块砖来。他们发现拆砖的
16、时候，只有把所有的奥术能量环流都破坏掉，才能取下砖。例如：下面图样，这是大工匠梅卡托克带回实验室进行进一步研究的一个模型。NOIP2009全国信息学奥林匹克联赛模拟试题（第三阶段集训） 2009 年 X月 XX日- 6 -在这个模型中，有 24=8块砖，相邻的砖之间已经用箭头标出了奥术极性能量的方向，由正极指向负极。经过分析不难发现，这个结构中存在着1，2，5，6，3，4两个极大奥术能量环流（再也加不进去另外一块砖使其仍为奥术能量环流） 。当然1，5也是一个奥术能量环流，但是它不是极大的，因为它是环流1，2，5，6的一个子环流。暴风城的贵族们采纳了梅卡托克的方案，尽管如此，实际执行工作的矮人们
17、还是无法理解。他们请你来帮助编写一个程序，在动工前算出这堵墙中存在的极大奥术能量环流的个数。【输入格式】输入文件中的第一行为两个整数 N，M（1=N，M=100） ，表示这堵墙由 N行，M 列块砖组合起来。第二行至第 N+1行，其中：第 i行中为 M个整数，第 j个整数 Pij表示这块砖的状态。P ij为一个小于 16的非负整数，把它转化为二进制以后，每个二进制位表示这块砖是否向一个方向发出极性奥术能量。二进制数从左到右第 1位为上，第 2为下，第 3位为左，第 4位为右，1 表示发射，0 表示没有。状态转换如下表。状态 0 1 2 3 4 5 6 7二进制表示 0000 0001 0010 0011 0100 0101 0110 0111状态 8 9 10 11 12 13 14 15二进制表示 1000 1001 1010 1011 1100 1101 1110 1111【输出格式】输出文件中仅一行为一个整数，即极大奥术能量环流的个数。【输入输出样例】输入：2 45 5 1 28 2 3 0输出：2样例说明：样例如题中所给出的图所示。有1，2，5，6，3，4两个极大奥术能量环流。
