ACM英文试题

ACMInternationalCollegiateProgrammingContest-1-ProblemOne:JoggingTrailsGordistrainingforamarathon.Behindhishouseisaparkwithalargenetworkofjoggingtrailsconnectingwaterstations.Gordwantstofindtheshortestjoggingroutethattravelsalongeverytrailatleastonce.InputInputconsistsofseveraltestcases.Thefirstlineofinputforeachcasecontainstwopositiveintegers:n=15,thenumberofwaterstations,andm1000,thenumberoftrails.Foreachtrail,thereisonesubsequentlineofinputcontainingthreepositiveintegers:thefirsttwo,between1andn,indicatingthewaterstationsattheendpointsofthetrail;thethirdindicatesthelengthofthetrail,incubits.Theremaybemorethanonetrailbetweenanytwostations;eachdifferenttrailisgivenonlyonceintheinput;eachtrailcanbetravelledineitherdirection.Itispossibletoreachanytrailfromanyothertrailbyvisitingasequenceofwaterstationsconnectedbytrails.Gord'sroutemaystartatanywaterstation,andmustendatthesamestation.Asinglelinecontaining0followsthelasttestcase.OutputForeachcase,thereshouldbeonelineofoutputgivingthelengthofGord'sjoggingroute.SampleInput45123234345141013120SampleOutput41ACMInternationalCollegiateProgrammingContest-2-ProblemTwo:AboveAverageItissaidthat90%offroshexpecttobeaboveaverageintheirclass.Youaretoprovidearealitycheck.InputThefirstlineofstandardinputcontainsanintegerC,thenumberoftestcases.Cdatasetsfollow.Eachdatasetbeginswithaninteger,N,thenumberofpeopleintheclass(1=N=1000).Nintegersfollow,separatedbyspacesornewlines,eachgivingthefinalgrade(anintegerbetween0and100)ofastudentintheclass.OutputForeachcaseyouaretooutputalinegivingthepercentageofstudentswhosegradeisaboveaverage,roundedto3decimalplaces.SampleInput555050708010071009590807060503709080370908191009998979695949391SampleOutput40.000%57.143%33.333%66.667%55.556%ACMInternationalCollegiateProgrammingContest-3-ProblemThree:MajorScalesInmusic,therangeofaudiblefrequenciesisdividedintooctaves,whereeachoctavespansfrequencieswithinfactorof2ofoneanother.Forexample,thenotecalledmiddleCcorrespondstoanaudiofrequencyof263Hz.TheoctavebelowmiddleCspansthefrequencyrangefrom131.5Hzto263HzwhiletheoctaveabovemiddleCspanstherangefrom263Hzto526Hz.Anoctavecontains13chromaticnoteswhosefrequenciesdifferbyacommonratio.Theseparationbetweentwoadjacentchromaticnotesiscalledahalf-steporsemi-tone.Notethatthereare12semi-tonesinanoctaveandthereforethefrequencyratiorepresentedbyasemi-toneis1.0593(since1.0593^12=2).Atoneistwosemi-tones.Whileitmightbeconvenienttousefrequenciestodescribemusicalnotes,historicaltraditiondemandsthatwenamethenotesofthechromaticscale,inorder:C,C#,D,D#,E,F,F#,G,G#,A,A#,B,C,andsoon,repeatingthesamenamesforeachnewoctave.Westernmusicrarelyusesallthenotesinthechromaticscale.Instead,8ofthe13chromaticnotesarecommonlyusedacomposition.Themostcommonsuchsetof8notesisthemajorscale.The8notesofamajorscale,inorder,areseparatedby:tone,tone,semi-tone,tone,tone,tone,semi-tone.Amajorscalecanbeginwithanyofthechromaticnotes;thisnotedefinesthekeyofthescale.Coincidentally,inthekeyofC,themajorscaleconsistsofthenotes:C,D,E,F,G,A,B,C.Ontheotherhand,inthekeyofF,themajorscaleis:F,G,A,A#,C,D,E,F.Thereareotherscales,notablytheminorscale,andmusiccomposedinaparticularscalesometimesusesnotesthatarenotwithinthescale,caledaccidentals.Weshallconcernourselvesonlywithmusiccomposedinamajorscalewithnoaccidentals.Yourjobistoreadasequenceofnotesandtoidentifyallthekeysthatthemusicmighthavebeencomposedin.Yourprogramneednothaveanymusicalear:reportaparticularkeyifandonlyifallthenotescomefromthemajorscaleinthatkey.InputInputcontainsseveraltestcases.Eachtestcaseconsistsofasinglelineofinput,containingasequenceofchromaticnotesseparatedbywhitespace.Noinputlineexceeds1000characters.ThelastlineofinputcontainsthewordEND.OutputForeachtestcase,outputalinegivingthepossiblekeys,intheordergivenabove.SampleInputCCDFEGAAFGBABCDEFGC#CCDFEGAAFGCCCCCENDSampleOutputCCFCC#D#FGG#A#ACMInternationalCollegiateProgrammingContest-4-ProblemFour:HardtoBelieve,butTrue!Thefightgoeson,whethertostorenumbersstartingwiththeirmostsignificantdigitortheirleastsignificantdigit.SometimesthisisalsocalledtheEndianWar.Thebattlegrounddatesfarbackintotheearlydaysofcomputerscience.JoeStoy,inhis(bythewayexcellent)bookDenotationalSemantics,tellsfollowingstory:Thedecisionwhichwayroundthedigitsrunis,ofcourse,mathematicallytrivial.Indeed,oneearlyBritishcomputerhadnumbersrunningfromrighttoleft(becausethespotonanoscilloscopetuberunsfromlefttoright,butinseriallogictheleastsignificantdigitsaredealtwithfirst).Turingusedtomystifyaudiencesatpubliclectureswhen,quitebyaccident,hewouldslipintothismodeevenfordecimalarithmetic,andwritethingslike73+42=16.Thenextversionofthemachinewasmademoreconventionalsimplybycrossingthex-deflectionwires:this,however,worriedtheengineers,whosewaveformswereallbackwards.Thatproblemwasinturnsolvedbyprovidingalittlewindowsothattheengineers(whotendedtobebehindthecomputeranyway)couldviewtheoscilloscopescreenfromtheback.[C.Strachey-privatecommunication.]YouwillplaytheroleoftheaudienceandjudgeonthetruthvalueofTuring'sequations.InputTheinputcontainssever