第三屆ACM程序設(shè)計(jì)大賽試題new

計(jì)算機(jī)工程學(xué)院第三屆ACM程序設(shè)計(jì)大賽試題ProblemABridgeDescriptionnpeoplewishtocrossabridgeatnight.Agroupofatmosttwopeoplemaycrossatanytime,andeachgroupmusthaveaflashlight.Onlyoneflashlightisavailableamongthenpeople,sosomesortofshuttlearrangementmustbearrangedinordertoreturntheflashlightsothatmorepeoplemaycross.Eachpersonhasadifferentcrossingspeed;thespeedofagroupisdeterminedbythespeedoftheslowermember.Yourjobistodetermineastrategythatgetsallnpeopleacrossthebridgeintheminimumtime.InputThefirstlineofinputcontainsn,followedbynlinesgivingthecrossingtimesforeachofthepeople.Therearenotmorethan1000peopleandnobodytakesmorethan100secondstocrossthebridge.OutputThefirstlineofoutputmustcontainthetotalnumberofsecondsrequiredforallnpeopletocrossthebridge.Thefollowinglinesgiveastrategyforachievingthistime.Eachlinecontainseitheroneortwointegers,indicatingwhichpersonorpeopleformthenextgrouptocross.(Eachpersonisindicatedbythecrossingtimespecifiedintheinput.Althoughmanypeoplemayhavethesamecrossingtimetheambiguityisofnoconsequence.)Notethatthecrossingsalternatedirections,asitisnecessarytoreturntheflashlightsothatmoremaycross.Ifmorethanonestrategyyieldstheminimaltime,anyonewilldo.SampleInput（Inputfile:pa.txt ）412510SampleOutput1721012ProblemBLottoDescriptionIntheGermanLottoyouhavetoselect6numbersfromtheset{1,2,...,49}.ApopularstrategytoplayLotto-althoughitdoesn'tincreaseyourchanceofwinning-istoselectasubsetScontainingk(k>6)ofthese49numbers,andthenplayseveralgameswithchoosingnumbersonlyfromS.Forexample,fork=8andS={1,2,3,5,8,13,21,34}thereare28possiblegames:[1,2,3,5,8,13],[1,2,3,5,8,21],[1,2,3,5,8,34],[1,2,3,5,13,21],...[3,5,8,13,21,34].YourjobistowriteaprogramthatreadsinthenumberkandthesetSandthenprintsallpossiblegameschoosingnumbersonlyfromS.InputTheinputwillcontainoneormoretestcases.Eachtestcaseconsistsofonelinecontainingseveralintegersseparatedfromeachotherbyspaces.Thefirstintegeronthelinewillbethenumberk(6<k<13).Thenkintegers,specifyingthesetS,willfollowinascendingorder.Inputwillbeterminatedbyavalueofzero(0)fork.OutputForeachtestcase,printallpossiblegames,eachgameononeline.Thenumbersofeachgamehavetobesortedinascendingorderandseparatedfromeachotherbyexactlyonespace.Thegamesthemselveshavetobesortedlexicographically,thatmeanssortedbythelowestnumberfirst,thenbythesecondlowestandsoon,asdemonstratedinthesampleoutputbelow.Thetestcaseshavetobeseparatedfromeachotherbyexactlyoneblankline.Donotputablanklineafterthelasttestcase.SampleInput （Inputfile:pb.txt ）712345678123581321340SampleOutput123456123457123467123567124567134567234567123581312358211235834123513211235133412352134123813211238133412382134123132134125813211258133412582134125132134128132134135813211358133413582134135132134138132134158132134235813212358133423582134235132134238132134258132134358132134ProblemCEncryptChipandDalehavedevisedanencryptionmethodtohidetheir(written)textmessages.Theyfirstagreesecretlyontwonumbersthatwillbeusedasthenumberofrows(R)andcolumns(C)inamatrix.Thesenderencodesanintermediateformatusingthefollowingrules:Thetextisformedwithuppercaseletters[A-Z]and<space>.Eachtextcharacterwillberepresentedbydecimalvaluesasfollows:<space>=0,A=1,B=2,C=3,...,Y=25,Z=26Thesenderentersthe5digitbinaryrepresentationofthecharacters'valuesinaspiralpatternalongthematrixasshownbelow.Thematrixispaddedoutwithzeroes(0)tofillthematrixcompletely.Forexample,ifthetexttoencodeis:"ACM"andR=4andC=4,thematrixwouldbefilledinasfollows:0000110100101100A=00001,C=00011,M=01101(oneextra0)Thebitsinthematrixarethenconcatenatedtogetherinrowmajororderandsenttothereceiver.Theexampleabovewouldbeencodedas:0000110100101100InputThefirstlineofinputcontainsa singleintegerN,(1follow.EachdatasetconsistsofasinglelineofinputcontainingR(1

≤

N

≤

1000)whichisthenumberofdatasetsthat≤R ≤20),aspace,C(1space,andastringofbinarydigitsthatrepresentsthecontentsofthematrix(R*Cbinarydigits).Thebinarydigitsareinrowmajororder.OutputForeachdataset,youshouldgenerateonelineofoutputwiththefollowingvalues:Thedatasetnumberasadecimalinteger(startcountingatone),aspace,andthedecodedtextmessage.Youshouldthrowawayanytrailingspacesand/orpartialcharactersfoundwhiledecoding.SampleInput（Inputfile:pc.txt ）244ACM52HISampleOutput00001101001011000110000010ProblemDConnectionThereareNcitiesinthecountryandMbidirectionalroadsbetweenthecities.Thegovernmentwantstobuildsomenewroadssuchthatforanypairofcitiesthereisatleastonepathbetweenthem.Nowyouhavetofindouttheminimalamountofroadsthathavetobuild.InputTheinputmaycontainmultipletestcases.Foreachtestcase,thefirstlineistwointegersN(1<=N<=100)andM(1<=M<=N*N/2),indicatingthenumberofcitiesandthenumberofroads.ThenthenextMlineseachcontaintwointegersxandy(0<=x,y<n),meaningthatthereisaroadbetweencitiesxandcitiesy.N=M=0indicatestheendofinput.OutputForeachtestcase,printtheanswerinasingleline.SampleInput（Inputfile:pd.txt ）213SampleOutput2ProblemE GridlandBackgroundForyears,computerscientistshavebeentryingtofindefficientsolutionstodifferentcomputingproblems.Forsomeofthemefficientalgorithmsarealreadyavailable,thesearethe"easy"problemslikesorting,evaluatingapolynomialorfindingtheshortestpathinagraph.Forthe"hard"onesonlyexponential-timealgorithmsareknown.Thetraveling-salesmanproblembelongstothislattergroup.GivenasetofNtownsandroadsbetweenthesetowns,theproblemistocomputetheshortestpathallowingasalesmantovisiteachofthetownsonceandonlyonceandreturntothestartingpoint.ProblemThepresidentofGridlandhashiredyoutodesignaprogramthatcalculatesthelengthoftheshortesttraveling-salesmantourforthetownsinthecountry.InGridland,thereisonetownateachofthepointsofarectangulargrid.RoadsrunfromeverytowninthedirectionsNorth,Northwest,West,Southwest,South,Southeast,East,andNortheast,providedthatthereisaneighbouringtowninthatdirection.ThedistancebetweenneighbouringtownsindirectionsNorth?CSouthorEast?CWestis1unit.ThelengthoftheroadsismeasuredbytheEuclideandistance.Forexample,Figure7shows2??3-Gridland,i.e.,arectangulargridofdimensions2by3.In2??3-Gridland,theshortesttourhaslength6.Figure7:Atraveling-salesmantourin2 ??3-Gridland.InputThefirstlinecontainsthenumberofscenarios.Foreachscenario,thegriddimensionsmandnwillbegivenastwointegernumbersinasingleline,separatedbyasingleblank,satisfying1<m<50and1<n<50.OutputTheoutputforeachscenariobeginswithalinecontaining"Scenario#i:",whereiisthenumberofthescenariostartingat1.Inthenextline,printthelengthoftheshortesttraveling-salesmantourroundedtotwodecimaldigits.Theoutputforeveryscenarioendswithablankline.SampleInput（Inputfile:pe.txt ）223SampleOutputScenario#1:4.00Scenario#2:6.00ProblemFDigitalRootsBackgroundThedigitalrootofapositiveintegerisfoundbysummingthedigitsoftheinteger.Iftheresultingvalueisasingledigitthenthatdigitisthedigitalroot.Iftheresultingvaluecontainstwoormoredigits,thosedigitsaresummedandtheprocessisrepeated.Thisiscontinuedaslongasnecessarytoobtainasingledigit.Forexample,considerthepositiveinteger24.Addingthe2andthe4yieldsavalueof6.Since6isasingledigit,6isthedigitalrootof24.Nowconsiderthepositiveinteger39.Addingthe3andthe9yields12.Since12isnotasingledigit,theprocessmustberepeated.Addingthe1andthe2yeilds3,asingledigitandalsothedigitalrootof39.InputTheinputfilewillcontainalistofpositiveintegers,oneperline.Theendoftheinputwillbeindicatedbyanintegervalueofzero.OutputForeachintegerintheinput,outputitsdigitalrootonaseparatelineoftheoutput.Sampleinput（Inputfile:pf.txt ）24390SampleOutput63ProblemGCountingNumbersStartingfromapositiveintegern(1<=n<=2001).Ontheleftoftheintegern,youcanplaceanotherintegermtoformanewintegermn,wheremmustbelessthenorequaltohalfoftheintegern,Ifthereisanintegerklessthenorequaltohalfofm,youcanplaceintegerkontheleftofmn,toformanewintegerkmn,,andsoon.ForExamole,youcanplace12ontheleftof30toFormaninteger1230,andyoucanplace6totheleftof1230toformaninteger61230,,andsoonForexample,startfromn=8.youcanplaceinteger1,2,3and4totheleftof8togettheintegers18,28,38,48.Fornumber18,youcannotformanewintegerusingtheproceduredescribedasabove.Fornumber28and38,youcanformnewintegers128and138.Fornumber48,youcanplace1and2ontheleftof48togetnewintegers148and248.Fornumber248,youcanplace1ontheleftofittogetanewinteger1248.Intotal,youcanhavethefollowing10integers(includeingtheintegeryoustartwith)8182838481281381482481248Giveanintegern,findthenumberofintegersyoucangetusingtheproceduredescribedabove.InputAnintegernOutputAnintegerwitchrepresentsthenumberofintegeryoucanget.Sampleinput: （Inputfile:pg.txt ）8SampleOutput:10ProblemHBuyLow,BuyLowerTheadviceto"buylow"ishalftheformulatosuccessinthestockmarket.Buttobeconsideredagreatinvestoryoumustalsofollowthisproblems'advice:"Buylow,buylower"Thatis,eachtimeyoubuyastock,youmustpurchasemoreatalowerpricethantheprevioustimeyouboughtit.Themoretimesyoubuyatalowerpricethanbefore,thebetter!Yourgoalistoseehowmanytimesyoucancontinuepurchasingateverlowerprices.Youwillbegiventhedailysellingpricesofastockoveraperiodoftime.Youcanchoosetobuystockonanyofthedays.Eachtimeyouchoosetobuy,thepricemustbelowerthantheprevioustimeyouboughtstock.Writeaprogramwhichidentifieswhichdaysyoushouldbuystockinordertomaximizethenumberoftimesyoubuy.Bywayofexample,supposeonsuccessivedaysstockissellinglikethis:Day12345