08年acm浙江省题目Word文档下载推荐.docx
《08年acm浙江省题目Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《08年acm浙江省题目Word文档下载推荐.docx（24页珍藏版）》请在冰点文库上搜索。
7'
（e.g.7,17,27,...）,heshallsay"
insteadofthenumberitself.
Forexample,4studentsplaythisgame.Atsometime,thefirstonesays25,thenthesecondshouldsay26.Thethirdshouldsay"
because27containsthedigit'
.Thefourthoneshouldsay"
too,because28isamultipleof7.Thenthefirstonesays29,andthegamegoeson.Whensomeonemakesamistake,thegameends.
Duringagame,youmayhearaconsecutiveofp"
s.Sowhatistheminimumnumberthatcanmakethissituationhappen?
Forexamplep=2,thatmeansthereareaconsecutiveof2"
s.Thissituationhappensin27-28asstatedabove.27isthentheminimumnumbertomakethissituationhappen.
Input
Standardinputwillcontainmultipletestcases.ThefirstlineoftheinputisasingleintegerT（1<
=T<
=100）whichisthenumberoftestcases.AnditwillbefollowedbyTconsecutivetestcases.
Thereisonlyonelineforeachcase.Thelinecontainsonlyoneintegerp（1<
=p<
=99）.
Output
Resultsshouldbedirectedtostandardoutput.Theoutputofeachtestcaseshouldbeasingleintegerinoneline,whichistheminimumpossiblenumberforthefirstofthep"
sstandsfor.
SampleInput
2
3
SampleOutput
27
70
二、BuildTheElectricSystem
198
75
Inlastwinter,therewasabigsnowstorminSouthChina.Theelectricsystemwasdamagedseriously.Lotsofpowerlineswerebrokenandlotsofvillageslostcontactwiththemainpowergrid.Thegovernmentwantstoreconstructtheelectricsystemassoonaspossible.So,asaprofessionalprogrammer,youareaskedtowriteaprogramtocalculatetheminimumcosttoreconstructthepowerlinestomakesurethere'
satleastonewaybetweeneverytwovillages.
Input
=50）whichisthenumberoftestcases.AnditwillbefollowedbyTconsecutivetestcases.
Ineachtestcase,thefirstlinecontainstwopositiveintegersNandE（2<
=N<
=500,N<
=E<
=N*（N-1）/2）,representingthenumberofthevillagesandthenumberoftheoriginalpowerlinesbetweenvillages.TherefollowElines,andeachofthemcontainsthreeintegers,A,B,K（0<
=A,B<
N,0<
=K<
1000）.AandBrespectivelymeanstheindexofthestartingvillageandendingvillageofthepowerline.IfKis0,itmeansthislinestillworksfineafterthesnowstorm.IfKisapositiveinteger,itmeansthislinewillcostKtoreconstruct.Therewillbeatmostonelinebetweenanytwovillages,andtherewillnotbeanylinefromonevillagetoitself.
Output
Foreachtestcaseintheinput,there'
sonlyonelinethatcontainstheminimumcosttorecovertheelectricsystemtomakesurethatthere'
SampleInput
1
33
015
020
129
SampleOutput
5
三、ColorfulRainbows
5
1
Evelynlikesdrawingverymuch.Today,shedrawslotsofrainbowsonwhitepaperofinfinitesize,eachusingadifferentcolor.Sincethere'
retoomanyrainbowsnow,shewonders,howmanyofthemcanbeseen?
Forsimplicity,eachrainbowLiisrepresentedasanon-verticallinespecifiedbytheequation:
y=aix+bi.ArainbowLicanbeseenifthereexistssomex-coordinatex0atwhich,itsy-coordinateisstrictlygreaterthany-coordinatesofanyotherrainbows:
aix0+bi>
ajx0+bjforallj!
=i.
Now,yourtaskis,giventhesetofrainbowsdrawn,figureoutthenumberofrainbowsthatcanbeseen.
=60）whichisthenumberoftestcases.AnditwillbefollowedbyTconsecutivetestcases.
There'
sablanklinebeforeeverycase.Ineachtestcase,therewillfirstbeanintegern（1<
=n<
=5000）,whichisthenumberofrainbows.Thennconsecutiverealnumberpairsfollow.Eachpaircontainstworealnumbers,aiandbi,representingrainbowLi:
y=aix+bi.Notworainbowswillbethesame,thatistosay,havethesameaandb.
Resultsshouldbedirectedtostandardoutput.Theoutputofeachtestcaseshouldbeasingleinteger,whichisthenumberofrainbowsthatcanbeseen.
11
10
20
30
四、DifferenceGame
0
Nowyouaregoingtoplayaninterestinggame.Inthisgame,youaregiventwogroupsofdistinctintegersandCcoins.Thetwogroups,namedGaandGbrespectively,arenotemptyandcontainthesamenumberofintegersatfirst.Eachtimeyoucanmoveoneintegerinonegrouptotheothergroup.Butamovethatmakesagroupemptyisconsideredasinvalid.Eachmovewillcostyoupcoins,andpequalsthedifferenceofthesizebetweenthetwogroup（taketheabsolutevalue.e.g.movinganumberfromthegroupofsize4tothegroupofsize6willcostyou|4-6|=2coins,andmovinganumberbetweentwogroupwithsamesizewillnotcostanycoins）.Youcandoasmanymovesasyouwish,solongasthetotalcostdoesnotexceedC.
LetMbetheminimumintegerinGa,andNbethemaximumintegerinGb.Thepurposeofthisgameistoproduceamaximum（M-N）.
EachcasebeginwithtwointegersS（1<
=S<
=20000,indicatingthesizeofGaandGbatfirst）andC（0<
=C<
=1000000）.TwolinesofSintegersfollow,representingthenumbersinGaandGbrespectively.Alltheseintegersaredistinctandarebetween1and50000,bothinclusive.
Resultsshouldbedirectedtostandardoutput.Theoutputofeachtestcaseshouldbeasingleintegerinoneline,whichisthemaximumpossiblevalueforM-Naftersomemoves.
110
10
12
210
12
34
-2
Hint
ForSample1,twogroupsareofsize1,sonomovescanbedonebecauseanymovingwillmakeGaorGbempty,whichisnotvalid.SoM=10,N=12,M-N=-2.
ForSample2,onevalidstepsofmovesis:
Move1inGatoGb,cost0coins.
Move3inGbtoGa,cost2coins.
Move4inGbtoGa,cost0coins.
ThenGacontains234,Gbcontains1,M=2,N=1,M-N=1.Thisisthemaximumpossiblevalue.
五、EasyTask
213
126
Calculatingthederivationofapolynomialisaneasytask.Givenafunctionf（x）,weuse（f（x））'
todenoteitsderivation.Weusex^ntodenotexn.Tocalculatethederivationofapolynomial,youshouldknow3rules:
（1）（C）'
=0whereCisaconstant.
（2）（Cx^n）'
=C*n*x^（n-1）wheren>
=1andCisaconstant.
（3）（f1（x）+f2（x））'
=（f1（x））'
+（f2（x））'
.
Itiseasytoprovethatthederivationapolynomialisalsoapolynomial.
Herecomestheproblem,givenapolynomialf（x）withnon-negativecoefficients,canyouwriteaprogramtocalculatethederivationofit?
=1000）whichisthenumberoftestcases.AnditwillbefollowedbyTconsecutivetestcases.
Thereareexactly2linesineachtestcase.ThefirstlineofeachtestcaseisasinglelinecontaininganintegerN（0<
=100）.ThesecondlinecontainsN+1non-negativeintegers,CN,CN-1,...,C1,C0,（0<
=Ci<
=1000）,whicharethecoefficientsoff（x）.Ciisthecoefficientofthetermwithdegreeiinf（x）.（CN!
=0）
Foreachtestcasecalculatetheresultpolynomialg（x）alsoinasingleline.
（1）Ifg（x）=0justoutputinteger0.otherwise
（2）supposeg（x）=Cmx^m+Cm-1x^（m-1）+...+C0（Cm!
=0）,thenoutputtheintegersCm,Cm-1,...C0.
（3）Thereisasinglespacebetweentwointegersbutnospacesafterthelastinteger.
321
10012
62
3001
六、Faster,Higher,Stronger
205
145
Intheyear2008,the29thOlympicGameswillbeheldinBeijing.ThiswillsignifytheprosperityofChinaandBeijingOlympicsistobeafestivalforpeopleallovertheworldaswell.
ThemottoofOlympicGamesis"
Citius,Altius,Fortius"
whichmeans"
Faster,Higher,Stronger"
.
Inthisproblem,therearesomerecordsintheOlympicGames.Yourtaskistofindoutwhichoneisfaster,whichoneishigherandwhichoneisstronger.
Eachtestcasehas3lines.Thefirstlineisthetypeoftherecords,whichcanonlybe"
Faster"
"
Higher"
or"
Stronger"
.ThesecondlineisapositiveintegerNmeaningthenumberoftherecordsinthistestcase.ThethirdlinehasNpositiveintegers,i.e.therecordsdata.Alltheintegersinthisproblemaresmallerthan2008.
Resultsshouldbedirectedtosta
升级会员 