08年acm浙江省题目.docx

08年acm浙江省题目.docx

《08年acm浙江省题目.docx》由会员分享，可在线阅读，更多相关《08年acm浙江省题目.docx（24页珍藏版）》请在冰点文库上搜索。

08年acm浙江省题目

一、AccuratelySay"CocaCola"!

Timelimit:

1Seconds  Memorylimit:

32768K  

TotalSubmit:

226  AcceptedSubmit:

132  

InapartyheldbyCocaColacompany,severalstudentsstandinacircleandplayagame.

Oneofthemisselectedasthefirst,andshouldsaythenumber1.Thentheycontinuetocountnumberfrom1onebyone（clockwise）.Thegameisinterestinginthat,oncesomeonecountsanumberwhichisamultipleof7（e.g.7,14,28,...）orcontainsthedigit'7'（e.g.7,17,27,...）,heshallsay"CocaCola"insteadofthenumberitself.

Forexample,4studentsplaythisgame.Atsometime,thefirstonesays25,thenthesecondshouldsay26.Thethirdshouldsay"CocaCola"because27containsthedigit'7'.Thefourthoneshouldsay"CocaCola"too,because28isamultipleof7.Thenthefirstonesays29,andthegamegoeson.Whensomeonemakesamistake,thegameends.

Duringagame,youmayhearaconsecutiveofp"CocaCola"s.Sowhatistheminimumnumberthatcanmakethissituationhappen?

Forexamplep=2,thatmeansthereareaconsecutiveof2"CocaCola"s.Thissituationhappensin27-28asstatedabove.27isthentheminimumnumbertomakethissituationhappen.

Input

Standardinputwillcontainmultipletestcases.ThefirstlineoftheinputisasingleintegerT（1<=T<=100）whichisthenumberoftestcases.AnditwillbefollowedbyTconsecutivetestcases.

Thereisonlyonelineforeachcase.Thelinecontainsonlyoneintegerp（1<=p<=99）.

Output

Resultsshouldbedirectedtostandardoutput.Theoutputofeachtestcaseshouldbeasingleintegerinoneline,whichistheminimumpossiblenumberforthefirstofthep"CocaCola"sstandsfor.

SampleInput

2

2

3

SampleOutput

27

70

二、BuildTheElectricSystem

Timelimit:

1Seconds  Memorylimit:

32768K  

TotalSubmit:

198  AcceptedSubmit:

75  

Inlastwinter,therewasabigsnowstorminSouthChina.Theelectricsystemwasdamagedseriously.Lotsofpowerlineswerebrokenandlotsofvillageslostcontactwiththemainpowergrid.Thegovernmentwantstoreconstructtheelectricsystemassoonaspossible.So,asaprofessionalprogrammer,youareaskedtowriteaprogramtocalculatetheminimumcosttoreconstructthepowerlinestomakesurethere'satleastonewaybetweeneverytwovillages.

Input

Standardinputwillcontainmultipletestcases.ThefirstlineoftheinputisasingleintegerT（1<=T<=50）whichisthenumberoftestcases.AnditwillbefollowedbyTconsecutivetestcases.

Ineachtestcase,thefirstlinecontainstwopositiveintegersNandE（2<=N<=500,N<=E<=N*（N-1）/2）,representingthenumberofthevillagesandthenumberoftheoriginalpowerlinesbetweenvillages.TherefollowElines,andeachofthemcontainsthreeintegers,A,B,K（0<=A,B

Output

Foreachtestcaseintheinput,there'sonlyonelinethatcontainstheminimumcosttorecovertheelectricsystemtomakesurethatthere'satleastonewaybetweeneverytwovillages.

SampleInput

1

33

015

020

129

SampleOutput

5

三、ColorfulRainbows

Timelimit:

1Seconds  Memorylimit:

32768K  

TotalSubmit:

5  AcceptedSubmit:

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.

Input

Standardinputwillcontainmultipletestcases.ThefirstlineoftheinputisasingleintegerT（1<=T<=60）whichisthenumberoftestcases.AnditwillbefollowedbyTconsecutivetestcases.

There'sablanklinebeforeeverycase.Ineachtestcase,therewillfirstbeanintegern（1<=n<=5000）,whichisthenumberofrainbows.Thennconsecutiverealnumberpairsfollow.Eachpaircontainstworealnumbers,aiandbi,representingrainbowLi:

y=aix+bi.Notworainbowswillbethesame,thatistosay,havethesameaandb.

Output

Resultsshouldbedirectedtostandardoutput.Theoutputofeachtestcaseshouldbeasingleinteger,whichisthenumberofrainbowsthatcanbeseen.

SampleInput

2

1

11

3

10

20

30

SampleOutput

1

2

四、DifferenceGame

Timelimit:

1Seconds  Memorylimit:

32768K  

TotalSubmit:

0  AcceptedSubmit:

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）.

Input

Standardinputwillcontainmultipletestcases.ThefirstlineoftheinputisasingleintegerT（1<=T<=60）whichisthenumberoftestcases.AnditwillbefollowedbyTconsecutivetestcases.

EachcasebeginwithtwointegersS（1<=S<=20000,indicatingthesizeofGaandGbatfirst）andC（0<=C<=1000000）.TwolinesofSintegersfollow,representingthenumbersinGaandGbrespectively.Alltheseintegersaredistinctandarebetween1and50000,bothinclusive.

Output

Resultsshouldbedirectedtostandardoutput.Theoutputofeachtestcaseshouldbeasingleintegerinoneline,whichisthemaximumpossiblevalueforM-Naftersomemoves.

SampleInput

2

110

10

12

210

12

34

SampleOutput

-2

1

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

Timelimit:

1Seconds  Memorylimit:

32768K  

TotalSubmit:

213  AcceptedSubmit:

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?

Input

Standardinputwillcontainmultipletestcases.ThefirstlineoftheinputisasingleintegerT（1<=T<=1000）whichisthenumberoftestcases.AnditwillbefollowedbyTconsecutivetestcases.

Thereareexactly2linesineachtestcase.ThefirstlineofeachtestcaseisasinglelinecontaininganintegerN（0<=N<=100）.ThesecondlinecontainsN+1non-negativeintegers,CN,CN-1,...,C1,C0,（0<=Ci<=1000）,whicharethecoefficientsoff（x）.Ciisthecoefficientofthetermwithdegreeiinf（x）.（CN!

=0）

Output

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.

SampleInput

3

0

10

2

321

3

10012

SampleOutput

0

62

3001

六、Faster,Higher,Stronger

Timelimit:

1Seconds  Memorylimit:

32768K  

TotalSubmit:

205  AcceptedSubmit:

145  

Intheyear2008,the29thOlympicGameswillbeheldinBeijing.ThiswillsignifytheprosperityofChinaandBeijingOlympicsistobeafestivalforpeopleallovertheworldaswell.

ThemottoofOlympicGamesis"Citius,Altius,Fortius",whichmeans"Faster,Higher,Stronger".

Inthisproblem,therearesomerecordsintheOlympicGames.Yourtaskistofindoutwhichoneisfaster,whichoneishigherandwhichoneisstronger.

Input

Standardinputwillcontainmultipletestcases.ThefirstlineoftheinputisasingleintegerT（1<=T<=50）whichisthenumberoftestcases.AnditwillbefollowedbyTconsecutivetestcases.

Eachtestcasehas3lines.Thefirstlineisthetypeoftherecords,whichcanonlybe"Faster""Higher"or"Stronger".ThesecondlineisapositiveintegerNmeaningthenumberoftherecordsinthistestcase.ThethirdlinehasNpositiveintegers,i.e.therecordsdata.Alltheintegersinthisproblemaresmallerthan2008.

Output

Resultsshouldbedirectedtosta