ACM0922测试题Word下载.docx

ACM0922测试题Word下载.docx

《ACM0922测试题Word下载.docx》由会员分享，可在线阅读，更多相关《ACM0922测试题Word下载.docx（12页珍藏版）》请在冰点文库上搜索。

999

SampleOutput

2.05

18.20

-10.25

EndofOutput

ProblemB:

图的“基”

Wewillusethefollowing（standard）definitionsfromgraphtheory.LetVbeanonemptyandfiniteset,itselementsbeingcalledvertices（ornodes）.LetEbeasubsetoftheCartesianproductV×

V,itselementsbeingcallededges.ThenG=（V,E）iscalledadirectedgraph.

Letnbeapositiveinteger,andletp=（e1,...,en）beasequenceoflengthnofedgesei∈Esuchthatei=（vi,vi+1）forasequenceofvertices（v1,...,vn+1）.Thenpiscalledapathfromvertexv1tovertexvn+1inGandwesaythatvn+1isreachablefromv1,writing（v1→vn+1）.

Herearesomenewdefinitions.AnodevinagraphG=（V,E）iscalledasink,ifforeverynodewinGthatisreachablefromv,visalsoreachablefromw.Thebottomofagraphisthesubsetofallnodesthataresinks,i.e.,bottom（G）={v∈V|∀w∈V:

（v→w）⇒（w→v）}.Youhavetocalculatethebottomofcertaingraphs.

Theinputcontainsseveraltestcases,eachofwhichcorrespondstoadirectedgraphG.Eachtestcasestartswithanintegernumberv,denotingthenumberofverticesofG=（V,E）,wheretheverticeswillbeidentifiedbytheintegernumbersinthesetV={1,...,v}.Youmayassumethat1<

=v<

=5000.Thatisfollowedbyanon-negativeintegereand,thereafter,epairsofvertexidentifiersv1,w1,...,ve,wewiththemeaningthat（vi,wi）∈E.Therearenoedgesotherthanspecifiedbythesepairs.Thelasttestcaseisfollowedbyazero.

Foreachtestcaseoutputthebottomofthespecifiedgraphonasingleline.Tothisend,printthenumbersofallnodesthataresinksinsortedorderseparatedbyasinglespacecharacter.Ifthebottomisempty,printanemptyline.

ProblemC:

固定分区竞赛管理

Atechniqueusedinearlyprogrammingconteststrategiesinvolvedpartitioningtheavailableintellectualcapacityofateamintoanumberofmemberswitheachmemberhavingafixedamountofintelligence,differentmemberspotentiallyhavingdifferentamounts.Thesumofthebrightnessofallmembersequalsthetotalintellectualcapacityoftheteam.Givenasetofproblems,itwasthetaskoftheteamtoassigntheproblemstodifferentteammembers,sothattheycouldbesolvedconcurrently.Thiswasmadedifficultduetothefactthatthesolutiontimeofaproblemmightdependontheamountofintelligenceavailabletoit.Everyproblemhasaminimumintelligencerequirement,butifassignedtoabrightermemberitssolutiontimemightincreaseordecrease.

有一种技术应用于早期的程序设计竞赛策略，该技术是将一个团队可用的智力值分成不同的小组，每个小组有一个固定数量的智力值，不同的小组可能数量不同。

所有成员的智力值的总和等于整个团队总的智力值。

给定一组的问题，由于是一个团队任务，因此需要把这些任务分配给不同的小组并使得他们可以同时完成。

但要做到这一点将是一个非常困难的事情，以为解决一个问题所耗费的时间，可能取决于提供给它的智力值。

每个问题都有一个最低的智力值要求，但是如果完成该问题的小组增加了一个智力值更高的成员，其完成时间可能会增加或减少。

Inthistask,youhavetodetermineoptimalassignmentsofproblemstoteammembers.Yourprogramisgiventheintellectualcapacitiesoftheteammembersavailableforthesolutionofproblems,andforeachproblemadescriptionofhowitssolutiontimedependsontheamountofintelligenceavailabletoit.Yourprogramhastofindthesolutionscheduleoftheproblemsthatminimizestheaveragesolutiontimefortheproblems.Asolutionscheduleisanassignmentofproblemstoteammembersandtimes,suchthatnotwoproblemsusethesamememberatthesametime,andnoproblemisassignedtoateammemberwithlessbrightnessthanitsminimumrequirement.Thesolutiontimeoftheproblemisthedifferencebetweenthetimewhentheproblemwassubmittedtobesolved（whichisthestartofthecontestattimezeroforallproblemsinthistask）,andthetimethattheproblemissolved.

在这个题目中，你必须找到将问题分配给团队成员的最佳方案。

你的程序必须能够给出整个团队完成这一组问题所需要的总的智力值，以及对于每一个问题其完成时间和所需智力值之间的描述。

你的程序还需要能够找出使得这组问题的平均解决时间最小的解决方案。

一个正确的解决方案是将这些如何问题分配给不同的小组成员和问题解决时间的安排表，并且该解决方案应该满足以下条件：

1、保证没有两个问题在同一时刻使用同一个成员；

2、不能把问题分配给不能满足问题最低智力值要求的成员。

问题解决时间是问题完成时间和提交时间（在任务中所有问题的提交时间就是比赛开始的时候--0）的差值。

Theinputdatawillcontainmultipletestcases.Eachtestcasebeginswithalinecontainingapairofintegersmandn.Thenumbermspecifiesthenumberofteammembers（1<

=m<

=3）,andnspecifiesthenumberofproblemstobesolved（1<

=n<

=10）.

输入数据包含几组测试用例。

每组测试用例以一行包含一对整数m和n开始，m表示小组的成员数（1<

=m<

=3）,m表示需要解决的问题数（1<

=n<

=10）.

Thenextlinecontainsmpositiveintegersgivingtheintelligenceamountsofthemteammembers.Followingthisarenlines,describingthetime-brightnesstradeoffsforeachofthenproblems.Eachlinestartswithapositiveintegerk（k<

=10）,followedbykpairsofpositiveintegerss1,t1,s2,t2,...,sk,tkthatsatisfysi<

si+1for1<

=i<

k.Theminimumintelligencerequirementoftheproblemiss1,i.e.itcannotbesolvedbyamemberwithlessintellectualcapacitythanthisnumber.Iftheproblemissolvedbyateammemberwithbrightnesss,wheresi<

=s<

si+1forsomei,thenitssolutiontimewillbeti.Finally,iftheproblemissolvedbyateammemberwithintellectualcapacityskormore,thenitsexecutiontimewillbetk.

接下来一行包含m个正整数，表示m个不同成员的智力值。

接下来n行，描述了n个问题时间和智力权值。

每行以一个正整数k（k<

=10）开始，接下来有k对正整数s1,t1,s2,t2,...,sk,tk满足在1<

=i<

k的情况下si<

si+1。

一个问题的最低智力值要求是s1，也就是说，这个问题不能被智力值低于该值的成员解决。

如果一个问题被一个智力值为s的成员解决，当si<

=s<

si+1时，这时，该问题的解决时间就是ti。

如果这个问题被一个智力大于或者等于sk的人解决，那么该问题的执行时间就是tk。

Apairofzeroeswillfollowtheinputforthelasttestcase.

输入以一对零（00）结束。

Youmayassumethateachproblemwillbesolvedinexactlythetimespecifiedforthegivenbrightness,regardlessofthenumberofotherproblemsbeingsolvedbyotherteammembersatthesametime.Noproblemwillhaveanintelligencerequirementlargerthanthatofthebrightestteammember.

不管同时其他成员已经解决问题的数目有多少，你都可以假设每个问题都将在给定智力值对应的准确时间时得到解决。

没有任何一个问题解决所需的智力值会大于所有成员智力值的最大值。

Foreachtestcase,firstdisplaythecasenumber（startingwith1andincreasingsequentially）.Thenprinttheminimumaveragesolutiontimeforthesetofproblemswithtwodigitstotherightofthedecimalpoint.Followthisbythedescriptionofasolutionschedulethatachievesthisaveragesolutiontime.Displayonelineforeachproblem,intheordertheyweregivenintheinput,thatidentifiestheproblemnumber,thememberusedtosolveit（numberedintheordergivenintheinput）,thetimewhenthememberstartedtosolvetheproblem,andthetimewhentheproblemwassolved.Followtheformatshowninthesampleoutput,andprintablanklineaftereachtestcase.

对于每一个测试用例，首先显示Casenumber（从1开始，依次增加）。

接着打印这组问题的最的平均完成时间，保留两位小数点。

接下来是一个达到这个平均完成时间的解决方案安排表。

按照这些问题在输入中给出的顺序一个问题显示在一行，依次是problemnumber、解决问题的成员（按照输入的顺序编号）、成员开始解决问题的时间和问题完成的时间。

按照样例输出的格式，在每一个测试用例的后面输出一个空白行。

24

4060

1354

1203

14010

1607

35

102030

210501230

2101002025

12519

11941

210183042

00

Case1

Averagesolutiontime=7.75

Problem1issolvedbymember2from0to4

Problem2issolvedbymember1from0to3、

Problem3issolvedbymember1from3to13

Problem4issolvedbymember2from4to11

Case2

Averagesolutiontime=35.40

Problem1issolvedbymember3from19to49

Problem2issolvedbymember2from0to25

Problem3issolvedbymember3from0to19

Problem4issolvedbymember2from25to66

Problem5issolvedbymember1from0to18

ProblemD:

冰饮料

好饮料关键在于冰。

那就是说冰的数量让饮料有所区分。

如果冰太多，则饮料会足够的清凉。

另一方面，如果冰太少，饮料不能冷却那是不能接受的。

请你帮助调饮料的师傅，计算这些饮料混合后的结果。

为了使事情变简单，我们假设纯净水和冰在一个封闭的系统中混合，也就是说没有热量损失等其他因素干扰。

因此一段时间过后，混合系统可会达到平衡（没有温度的进一步变化也没有融解或冰冻）。

你的任务是计算这混合系统达到平衡后的最终温度，以及在平衡状态下冰和水的数量。

从物理学可知，让1g水升温1K需要4.19J热量。

如果让1g冰升温1K则需要2.09J。

定义如下：

cw=4.19J/（g*K）a和ci=2.09J/（g*K）.融化1g冰需要335J,且融化后温度停留在0度.定义常量em=335J/g.实验前后冰和水的总热量保持不变。

下图表示了相对于零下30摄氏度时测量得到的1克（冰、冰水混合物、水）的能量.0度表示冰正在融解于水。

获得的能量与融化了的冰的数量成正比。

输入包含几组测试用例，每组测试用例占一行有4个实数：

mw,mi,tw,ti.（mw,mi分别表示水和冰的质量,都是非负数，单位为克且mw+mi>

0。

tw,ti分别表示水和冰的温度,单位是摄氏度,-30<

ti<

=0<

=tw<

100.）结尾4个0表示输入结束

对于每组测试用例，输出混合后冰和水的质量（单位克）及混合后的温度（摄氏度）。

所有数据四舍五入保留1位小数。

输出格式参见样例输出。