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