算法艺术与信息学竞赛题目完全解析

两个特殊的结构:线段树和 动态规 Pku1038--BugsIntegrated, Pku1691--PaintingA Pku1661--Help Pku1161--Post 状态空 第2 数论基 Pku1811--Prime Pku2409--Letit Pku1286--Necklaceof Pku1037--Adecorative Pku1275--Cashier 程序=算法+数据结构枚 CastawayRobinsonCrusoeislivingaloneonaremoteisland.Onedayashipcarryingaroyallibraryhaswreckednearby.UsuallyRobinsonbringsanyusefulstufffromtheshipwrecktohisisland,andthistimehehasbroughtabigchestwithbooks.Robinsonhasdecidedtobuildabookcaseforthesebookstocreatehisownlibrary.Hecutarectangularnicheintherockforthatpurpose,hammeredinwoodenpegs,andcedwoodennksoneverypairofpegsthathavethesameheight,sothatallnksaresituatedhorizontallyandsuittoactasshelves.Unfortunay,Robinsonhasdiscoveredthatoneespeciallyoldandbigtomedoesnotfitinhisbookcase.Hemeasuredtheheightandwidthofthistomeandhasdecidedtoredesignhisbookcaseinsuchaway,astocompleyfitthetomeononeoftheshelves,takingintoaccountlocationsofothershelvesandthedimensionsoftheniche.Witheachshelfinthebookcase,oneofthefollowingoperationsshouldbemade:LeavetheshelfonitsoriginalMovetheshelftotheleftortotheShortentheshelfbycuttingoffapartofthenkandoptionallymoveittotheleftortotheright.Moveoneofthepegstoadifferentceatthesameheightandmovetheshelftotheleftortotheright.Shortentheshelfbycuttingoffapartofthenk,moveoneofthepegstoaceatthesameheight,andoptionallymovetheshortenedshelftotheleftortotheRemovetheshelffromthebookcasealongwithbothsupportingWesaythattheshelfisproperlysupportedbyitspegs,ifexactlytwodistinctpegssupporttheshelfandthecenteroftheshelfisbetweenitspegsorcoincideswithoneofthepegs.TheoriginaldesignofRobinson'slibraryhasalltheshelvesproperlysupportedbytheirpegsandlengthsofallshelvesareintegernumberofinches.TheRobinsonmayonlycutanintegernumberofinchesfromthenks,becausehehasnotoolsformoreprecisemeasurements.Allremainingshelvesaftertheredesignmustbeproperlysupportedbytheirpegs.YouaretofindthewaytoredesignRobinson'slibrarytofitthespecialoldtomewithoutchangingoriginaldesigntoomuch.Youhavetominimizethenumberofpegsthataretoberemovedfromtheiroriginalcesduringtheredesign(operations4and5removeonepeg,andoperation6removestwopegs).Iftherearedifferentwaystosolvetheproblem,thenyouaretofindtheonethatminimizesthetotallengthofnksthataretobecutoff(operations3and5involvecuttingsomethingfromthenks,andoperation6countsasifcuttingoffthewholenk).WidthofnksanddiameterofpegsshallbeconsideredThetomemaynotberotated.Thetomeshouldcomple y(toallitswidth)standononeoftheshelvesandmayonlytouchothershelves,theirpegsorniche'sedge.ThefirstlineoftheinputfilecontainsfourintegernumbersXN,YN,XT,andYT,separatedbyspaces.Theyare,correspondingly,widthandheightoftheniche,andwidthandheightoftheoldtomeininches(1<=XN,YN,XT,YT<=1000).ThesecondlineoftheinputfilecontainsasingleintegernumberN(1<=N<=100)thatrepresentsthenumberoftheshelves.ThenNlinesfollow.Eachlinerepresentsasingleshelfalongwithitstwosupportingpegs,andcontainsfiveintegernumbersyi,xi,li,x1i,x2i,separatedbyspaces,where:?yi(0<yi<YN)-theheightoftheithshelfabovethebottomofthenichein?xi(0<=xi<XN)-thedistancebetweentheleftendoftheithshelfandtheleftedgeofthenicheininches.?li(0<li<=XN-xi)-thelengthoftheithshelfin?x1i(0<=x1i<=li/2)-thedistancebetweentheleftendoftheithshelfanditsleftmostsupportingpegininches.?x2i(li/2<=x2i<=li;x1i<x2i)-thedistancebetweentheleftendoftheithshelfanditsrightmostsupportingpegininches.Allshelvesaresituatedondifferentheightsandareproperlysupportedbytheirpegs.Theproblemisguaranteedtohaveasolutionfortheinputdata.Theoutputfileshallcontaintwointegernumbersseparatedbyaspace.ThefirstonetheminimalnumberofpegsthataretoberemovedbyRobinsonfromtheiroriginallocationstocethetome.Thesecondoneistheminimaltotallengthofnksininchesthataretobecutoffduringtheredesignthatremovestheleastnumberofpegs.Sample118441632030Sample1#include<stdio.h>#include<iostream>#include<algorithm>usingnamespacestd;structshelf{intx,y,len,x1,x2;}a[101];intN,XN,YN,XT,YT;intoptPegs=20000,optCost= boolcmp(shelfa,shelfb){returna.y<b.y;}voidcheck(intk,intx,int&minPegs,int{intfor(i=k+1;i<N;if(a[i].y>=a[k].y+YT)if(a[i].x+a[i].len<=x||a[i].x>=x+XT);elseif(a[i].x2<=x){intif(x-a[i].x1<=a[i].x1)max=2*(x-a[i].x1);elsemax=x;if(max<a[i].len)minCost+=a[i].len-}elseif(a[i].x1>=x+XT){intmax;if(a[i].x2-(x+XT)<=XN-a[i].x2)max=2*(a[i].x2-(x+XT));elsemax=XN-(x+XT);if(max<a[i].len)minCost+=a[i].len-}elseif(a[i].x1<=x&&a[i].x2>x&&a[i].x2<x+if(x==0)minPegs+=2,minCost+=a[i].len;else{if(a[i].len>x)minCost+=a[i].len-}}elseif(a[i].x1>x&&a[i].x1<x+XT&&a[i].x2>=x+XT){if(x+XT==XN)minPegs+=2,minCost+=a[i].len;else{if(a[i].len>XN-(x+XT))minCost+=a[i].len-(XN-(x+}}elseif(a[i].x1<=x&&a[i].x2>=x+if(x==0&&XT==XN)minPegs+=2;elseminPegs++;intmax=x>XN-(x+XT)?x:XN-(x+XT);if(a[i].len>max)minCost+=a[i].len-max;}elseif(a[i].x1>x&&a[i].x2<x+XT){minPegs+=2;minCost+=a[i].len;}}}voidsolve(int{intfor(book_l=0;book_l+XT<=XN;book_l++){intminPegs=0,minCost=0;if(book_l+a[k].len<a[k].x1)continue;if(a[k].x2+a[k].len<book_l+XT)if(book_l+a[k].len<a[k].x1||a[k].x2+a[k].len<book_l+XT)if(2*(a[k].x1-book_l)>a[k].len||2*(book_l+XT-a[k].x2)>a[k].len)elseif(a[k].x2-book_l>a[k].len||(book_l+XT)-a[k].x1>a[k].len)minPegs++;check(k,book_l,minPegs,minCost);if(minPegs<optPegs||(minPegs==optPegs&&minCost<optCost))optPegs=minPegs, optCost=minCost;}}int{scanf("%d%d%d%d",&XN,&YN,&XT,inti;for(i=0;i<N;scanf("%d%d%d%d%d",&a[i].y,&a[i].x,&a[i].len,&a[i].x1,&a[i].x2);a[i].x1+=a[i].x;a[i].x2+=}sort(a,a+N,cmp);for(i=0;i<N;i++){if(a[i].y+YT>YN)break;if(a[i].len>=XT)solve }printf("%d%d",optPegs,}贪Pku1042--GoneJohnisgoingonafishingtrip.Hehashhoursavailable(1<=h<=16),andtherearenlakesinthearea(2<=n<=25)allreachablealongasingle,one-wayroad.Johnstartsatlake1,buthecanfinishatanylakehewants.Hecanonlytravelfromonelaketothenextone,buthedoesnothavetostopatanylakeunlesshewishesto.Foreachi=1,...,n-1,thenumberof5-minuteintervalsittakestotravelfromlakeitolakei+1isdenotedti(0<ti<=192).Forexample,t3=4meansthatittakes20minutestotravelfromlake3tolake4.Tohelpnhisfishingtrip,Johnhasgatheredsomeinformationaboutthelakes.Foreachlakei,thenumberoffishexpectedtobecaughtintheinitial5minutes,denotedfi(fi>=0),isknown.Each5minutesoffishingdecreasesthenumberoffishexpectedtobecaughtinthenext5-minuteintervalbyaconstantrateofdi(di>=0).Ifthenumberoffishexpectedtobecaughtinanintervalislessthanorequaltodi,therewillbenomorefishleftinthelakeinthenextinterval.Tosimplifythenning,Johnassumesthatnooneelsewillbefishingatthelakestoaffectthenumberoffishheexpectstocatch.WriteaprogramtohelpJohnnhisfishingtriptoizethenumberoffishexpectedtobecaught.Thenumberofminutesspentateachlakemustbeamultipleof5.Youwillbegivenanumberofcasesintheinput.Eachcasestartswithalinecontainingn.Thisisfollowedbyalinecontainingh.Next,thereisalineofnintegersspecifyingfi(1<=i<=n),thenalineofnintegersdi(1<=i<=n),andfinally,alineofn-1integersti(1<=i<=n-1).Inputisterminatedbyacaseinwhichn=Foreachtestcase,printthenumberofminutesspentateachlake,separatedbycommas,forthenachievingthe umnumberoffishexpectedtobecaught(youshouldprinttheentirenononelineevenifitexceeds80characters).Thisisfollowedbyalinecontainingthenumberoffishexpected.Ifmultiplensexist,choosetheonethatspendsaslongaspossibleatlake1,evenifnofishareexpectedtobecaughtinsomeintervals.Ifthereisstillatie,choosetheonethatspendsaslongaspossibleatlake2,andsoon.Insertablanklinebetweencases.Sample2110224424420Sample45,Numberoffishexpected:240,0,0,Numberoffishexpected:115,10,50,Numberoffishexpected:#includeusingnamespacestd;intmain(){intn,h;{if(n==0)intinti,j;intintans[26][26]={0};{intflag=0;while(time>0&&flag!=i){{}if(fs[j]<=0)}{if(j!=n)cout<<",}cout<<"Numberoffishexpected:"<<ans[k][0]<<endl;}return}Pku1700--CrossingAgroupofNpeoplewishestogoacrossariverwithonlyoneboat,whichcanatmostcarrytwo s.Thereforesomesortofshuttlearrangementmustbearrangedinordertorowtheboatbackandforthsothatallpeoplemaycross.Each hasadifferentrowingspeed;thespeedofacoupleisdeterminedbythespeedoftheslowerone.Yourjobistodetermineastrategythatminimizesthetimeforthesepeopletogetacross.ThefirstlineoftheinputcontainsasingleintegerT(1<=T<=20),thenumberoftestcases.ThenTcasesfollow.ThefirstlineofeachcasecontainsN,andthesecondlinecontainsNintegersgivingthetimeforeachpeopletocrosstheriver.Eachcaseisprecededbyablankline.Therewon'tbemorethan1000peopleandnobodytakesmorethan100secondstocross.Foreachtestcase,printalinecontainingthetotalnumberofsecondsrequiredforalltheNpeopletocrosstheriver.Sample14125Sampleusingnamespacestd;intmain(){inta,b,i,j,t,n,*s,sum,cas;cin>>cas;{cin>>n;s=newint[n];}

delete[]s;}return}递归与分治算法递Pku1090- andhadnotalwaysbeenademocraticcountry.Therewerealsoblackpagesinitsbookofhistory.OnelovelydaygeneralBy −commanderofthejuntawhichhadpoweroverBy and−−decidedtofinishthelong−lastingtimeofwarandreleasedimprisonedactivistsoftheopposition.However,hehadnointentiontolettheleader .Hedecidedtochainhimtothewallwiththebytishchain.Itconsistsofjoinedringsandthebarfixedtothewall.Althoughtheringsarenotjoinedwiththebar,itishardtotakethemoff.'General,whyhaveyouchainedmetotheprisonwallsanddidnotletrejoiceatdom!'criedBytesar.'ButBytesar,youarenotchainedatall,andIamcertainyouareabletotakeofftheringsfromthebarbyyourself.'perfidiouslyansweredgeneralBy ,andheadded'Butdealwiththatbeforeaclockstrikesthecyberhouranddonotmakeanoiseatnight,otherwiseIwillbe dtocallCivilCyber.'HelpBytesar!Numberthefollowingringsofthechainwithintegers1,2,...,n.Wemayputonandtakeofftheseringsaccordingtothefollowingrules:.onlyoneringcanbeputonortakenofffromthebarinone.theringnumber1canbealwaysputonortakenofffromthe.iftheringswiththenumbers1,...,k−1(for1<=k<n)aretakenofffromthebarandtheringnumberkisputon,wecanputonortakeofftheringnumberk+1.Wputesminimalnumberofmovesnecessarytotakeoffallringsofthebytishchainfromthebar,.writestheresulttostdInthefirstlineoftheinputthereiswrittenoneintegern,1<=n<=1000.Inthesecondlinetherearewrittennintegerso1,o2,...,on(eachofthemiseither0or1)separatedbysinglespaces.Ifoi=1,thenthei−thringisputonthebar,andifoi=0,thenthei−thringistakenoffthebar.Theoutputshouldcontainexactlyoneintegerequaltotheminimalnumberofmovesnecessarytotakeoffalltheringsofthebytishchainfromthebar.Sample4101Sample601S1n<1000）将S的第一个字符取反。S[1i1]=‘000…00’，S[i]‘1S[i取反。（1in–usingnamespacestd;voidplus(char*,char*,char*);//加法运算constintMAXLEN=330;//最大长度int{charchange[MAXLEN+1];//记录00To01[n]charAfterResult[2][MAXLEN+1];//每次运算后的结果inti,j,length;{change[MAXLEN-1]='1';//1位数时,00To011步{}else{/*a[1]=1s[1]To00=1s[1]To01=0a[1]=0s[1]To00=0sign[0]='1'则BeforeResult[1][MAXLEN-1]=1BeforeResult[0][MAXLEN-1]=0*/IfIf{{故} }} }}return}voidplus(char*num1,char*num2,char*result)//{{}}Pku2351--TimePriortothelatenineteenthcentury,timekeewasapurelylocalphenomenon.Eachtownwouldsettheirclockstonoonwhenthesunreacheditszenitheachday.Aclockmakerortownclockwouldbethe"official"timeandthecitizenswouldsetpocketwatchesandclockstothetimeofthetown-enterprisingcitizenswouldoffertheirservicesasclocksetters,carryingawatchwiththeaccuratetimetoadjusttheclocksincustomer'shomesonaweeklybasis.Travelbetweencitiesmeanthavingtochangeone'spocketwatchuponarrival.However,oncerailroadsbegantooperateandmovepeoplerapidlyacrossgreatdistances,timebecamemuchmorecritical.Intheearlyyearsoftherailroads,thescheduleswereveryconfusingbecauseeachstopwasbasedonadifferentlocaltime.Thestandardizationoftimewasessentialtoefficientoperationofrailroads.In1878,CanadianSirSanfordFlemingproposedthesystemofworldwidetimezonesthatweusetoday.He mendedthattheworldbedividedintotwenty-fourtimezones,eachspaced15degreesoflongitudeapart.Sincetheearthrotatesonceevery24hoursandthereare360degreesoflongitude,eachhourtheearthrotatesone-twenty-ofacircleor15°oflongitude.SirFleming'stimezoneswereheraldedasabrilliantsolutiontoachaoticproblemworldwide.UnitedStatesrailroadcompaniesbeganutilizingFleming'sstandardtimezonesonNovember18,1883.In1884anInternationalPrimeMeridianConferencewasheldinWashingtonD.C.tostandardizetimeandselectthePrimeMeridian.TheconferenceselectedthelongitudeofGreenwich,Englandaszerodegreeslongitudeandestablishedthe24timezonesbasedonthePrimeMeridian.Althoughthetimezoneshadbeenestablished,notallcountriesswitchedimmedia y.ThoughmostU.S.statesbegantoadheretothePacific,Mountain,Central,andEasterntimezonesby1895,Congressdidn'tmaketheuseofthesetimezonesmandatoryuntiltheStandardTimeActof1918.Today,manycountriesoperateonvariationsofthetimezonesproposedbySirFleming.Allof(whichshouldspanfivetimezones)usesasingletimezone-eighthoursaheadofCoordinatedUniversalTime(knownbytheabbreviationUTC-basedonthetimezonerunningthroughGreenwichat0°longitude).RussiaadherestoitsdesignatedtimezonesalthoughtheentirecountryisonpermanentDaylightSavingTimeandisanhouraheadoftheiractualzones.Australiausesthreetimezones-itscentraltimezoneisahalf-houraheadofitsdesignatedtimezone.SeveralcountriesintheMiddleEastandSouthAsiaalsoutilizehalf-hourtimezones.Sincetimezonesarebasedonsegmentsoflongitudeandlinesoflongitudenarrowatthepoles,scientistsworkingattheNorthandSouthPolessimplyuseUTCtime.Otherwise,Antarcticawouldbedividedinto24verythintimeTimezoneshaverecentlybeengivenstandardcapital-letterabbreviationsasfollows:UTCCoordinatedUniversalTimeGMTGreenwichMeanTime,definedasBSTBritishSummerTime,definedasUTC+1hourISTIrishSummerTime,definedasUTC+1hourWETWesternEuropeTime,definedasUTCWESTWesternEuropeSummerTime,definedasUTC+1hourCETCentralEuropeTime,definedasUTC+1CESTCentralEuropeSummerTime,definedasUTC+2EETEasternEuropeTime,definedasUTC+2EESTEasternEuropeSummerTime,definedasUTC+3MSKMoscowTime,definedasUTC+3MSDMoscowSummerTime,definedasUTC+4ASTAtlanticStandardTime,definedasUTC-4hoursADTAtlanticDaylightTime,definedasUTC-3NSTNewfoundlandStandardTime,definedasUTC-3.5hoursNDTNewfoundlandDaylightTime,definedasUTC-2.5hoursESTEasternStandardTime,definedasUTC-5hoursEDTEasternDaylightSavingTime,definedasUTC-4hoursCSTCentralStandardTime,definedasUTC-6hoursCDTCentralDaylightSavingTime,definedasUTC-5hoursMSTMountainStandardTime,definedasUTC-7hoursMDTMountainDaylightSavingTime,definedasUTC-6hoursPSTPacificStandardTime,definedasUTC-8hoursPDTPacificDaylightSavingTime,definedasUTC-7hoursHSTHawaiianStandardTime,definedasUTC-10hoursAKSTAlaskaStandardTime,definedasUTC-9hoursAKDTAlaskaStandardDaylightSavingTime,definedasUTC-8hoursAESTAustralianEasternStandardTime,definedasUTC+10hoursAEDTAustralianEasternDaylightTime,definedasUTC+11hoursACSTAustralianCentralStandardTime,definedasUTC+9.5hoursACDTAustralianCentralDaylightTime,definedasUTC+10.5hoursAWSTAustralianWesternStandardTime,definedasUTC+8hoursGiventhecurrenttimeinonetimezone,youaretocomputewhattimeitisinanothertimezone.ThefirstlineofinputcontainsN,thenumberoftestcases.Foreachcasealineisgivenwithatime,and2timezoneabbreviations.Timeisgiveninstandarda.m./p.m.formatwithmidnightdenoted"midnight"andnoondenoted"noon"(12:00a.m.and12:00p.m.areoxymorons).Foreachcase,assumingthegiventimeisthecurrenttimeinthefirsttimezone,givethecurrenttimeinthesecondtimezone.Sample4noonHST11:29a.m.EST6:01p.m.CST12:40p.m.ADTSample12:016:40#include<iostream>#include<string>#include<map>usingnamespacestd;intCount=0;stringp[10000];voidgetstring(char{inti=0;{charch;}}void{intn;inti=0;{charch[31];}inti_exam;{for(int{intsc;charch[31];}intfor(int{}}}int{return}数据结构（1）栈和队列ThereisafamousrailwaystationinPopPushCity.Countrythereisincrediblyhilly.Thestationwasbuiltinlastcentury.Unfortunay,fundswereextremelylimitedthattime.Itwaspossibletoestablishonlyasurfacetrack.Moreover,itturnedoutthatthestationcouldbeonlyadead-endone(seepicture)andduetolackofavailablespaceitcouldhaveonlyonetrack.ThelocaltraditionisthateverytrainarrivingfromthedirectionAcontinuesinthedirectionBwithcoachesreorganizedinsomeway.AssumethatthetrainarrivingfromthedirectionAhasN<=1000coachesnumberedinincreasingorder1,2,...,N.ThechieffortrainreorganizationsmustknowwhetheritispossibletomarshalcoachescontinuinginthedirectionBsothattheirorderwillbea1,a2,...,aN.Helphimandwriteaprogramthatdecideswhetheritispossibletogettherequiredorderofcoaches.YoucanassumethatsinglecoachescanbedisconnectedfromthetrainbeforetheyenterthestationandthattheycanmovethemselvesuntiltheyareonthetrackinthedirectionB.Youcanalsosupposethatatanytimetherecanbelocatedasmanycoachesasnecessaryinthestation.ButonceacoachhasenteredthestationitcannotreturntothetrackinthedirectionAandalsoonceithasleftthestationinthedirectionBitcannotreturnbacktothestation.Theinputconsistsofblocksoflines.Eachblockexceptthelastdescribesonetrainandpossiblymorerequirementsforitsreorganization.InthefirstlineoftheblockthereistheintegerNdescribedabove.Ineachofthenextlinesoftheblockthereisapermutationof1,2,...,N.Thelastlineoftheblockcontainsjust0.ThelastblockconsistsofjustonelinecontainingTheoutputcontainsthelinescorrespondingtothelineswithpermutationsintheinput.AlineoftheoutputcontainsYesifitispossibletomarshalthecoachesintheorderrequiredonthecorrespondinglineoftheinput.OtherwiseitcontainsNo.Inaddition,thereisoneemptylineafterthelinescorrespondingtooneblockoftheinput.Thereisnolineintheoutputcorrespondingtothelast``null''blockoftheinput.Sample51234554123066543200Sample#include<stdio.h>#defineN1005inta[N],b[N],c[N];intx,y,z;int{intn,while(scanf("%d",&n),n){for(i=1;i<n;i++)for(i=0;i<n;i++)a[i]=i+1;x=1;y=for(z=0;z<n;z++)while(c[z]!=b[y-1]&&x<{b[y]=a[x];}if(c[z]==b[y-{y--}elseif(x>={}}if(z<}

}return}Pku1879-TempusetmobiliusTimeandTempusestmensuramotusrerumTimeisthemeasureofmovement.--AuctoritatesAristo...andmovementhaslongbeenusedtomeasuretime.Forexample,theballclockisasimpledevicewhichkeepstrackofthepassingminutesbymovingball-bearings.Eachminute,arotatingarmremovesaballbearingfromthequeueatthebottom,raisesittothetopoftheclockanddepositsitonatrackleadingtoindicatorsdisyingminutes,five-minutesandhours.Theseindicatorsdisythetimebetween1:00and12:59,butwithout'a.m.'or'p.m.'indicators.Thus2ballsintheminuteindicator,6ballsinthefive-minuteindicatorand5ballsinthehourindicatordisysthetime5:32.Unfortunay,mostcommerciallyavailableballclocksdonotincorporateadateindication,althoughthiswouldbesimpletodowiththeadditionoffurthercarryandindicatortracks.However,allisnotlost!Astheballsmigratethroughthemechanismoftheclock,theychangetheirrelativeorderinginapredictableway.Carefulstudyoftheseorderingswillthereforeyieldthetimeelapsedsincetheclockhadsomespecificordering.Thelengthoftimewhichcanbemeasuredislimitedbecausetheorderingsoftheballseventuallybegintorepeat.Yourprogrammustcomputethetimebeforerepetition,whichvariesaccordingtothetotalnumberofballspresent.OperationoftheBallEveryminute,theleastrecentlyusedballisremovedfromthequeueofballsatthebottomoftheclock,elevated,thendepositedontheminuteindicatortrack,whichisabletoholdfourballs.Whenafifthballrollsontotheminuteindicatortrack,itsweightcausesthetracktotilt.Thefourballsalreadyonthetrackrunbackdowntojointhequeueofballswaitingatthebottominreverseorderoftheiroriginaladditiontotheminutestrack.Thefifthball,whichcausedthetilt,rollsondowntothefive-minuteindicatortrack.Thistrackholdselevenballs.Thetwelfthballcarriedoverfromtheminutescausesthefive-minutetracktotilt,returningtheelevenballstothequeue,againinreverseorderoftheiraddition.Thetwelfthballrollsdowntothehourindicator.Thehourindicatoralsoholdselevenballs,buthasoneextrafixedballwhichisalwayspresentsothatcountingtheballsinthehourindicatorwillyieldanhourintherangeonetotwelve.Thetwelfthballcarriedoverfromthefive-minuteindicatorcausesthehourindicatortotilt,returningtheelevenballstothequeue,inreverseorder,beforethetwelfthballitselfalsoreturnstothequeue.Theinputdefinesasuccessionofballclocks.Eachclockoperatesasdescribedabove.Theclocksdifferonlyinthenumberofballspresentinthequeueatoneo'clockwhenalltheclocksstart.Thisnumberisgivenforeachclock,oneperlineanddoesnotincludethefixedballonthehoursindicator.Validnumbersareintherange27to127.Azerosignifiestheendofinput.OutputForeachclockdescribedintheinput,yourprogramshouldreportthenumberofballsgivenintheinputandthenumberofdays(24-hourperiods)whichelapsebeforetheclockreturnstoitsinitialordering.Sample0Sample30ballscycleafter1545ballscycleafter378#include<iostream>#include<stack>#include<queue>int(intxx,int{if(yy!=returnxx;}{intwhile(cin>>n&&{queue<int>all_ball;stack<int>five,mini,hour;for(inti=1;i<=n;i++)intk=24*60;while(k--)intaa=all_ball.front();if(five.size()==4)for(inti=0;i<4;{);}if(mini.size()==11)for(inti=0;i<11;}if(hour.size()==11)for(inti=0;i<11;}}}}}intfor(inti=1;i<=n;{arr[i]= cout<<arr[i]<<endl;}intfor(inti=1;i<=n;i++)brr[i]=1;for(inti=1;i<=n;{intaa=arr[i];while(aa!=i)aa=}}intsum=for(inti=1;i<=n;i++)sum=sum*brr[i]/(sum,}cout<<n<<"ballscycleafter"<<sum<<"days."<<}return}串Pku1961-ForeachprefixofagivenstringSwithNcharacters(eachcharacterhasanASCIIcodebetween97and126,inclusive),wewanttoknowwhethertheprefixisaperiodicstring.Thatis,foreachi(2<=i<=N)wewanttoknowthelargestK>1(ifthereisone)suchthattheprefixofSwithlengthicanbewrittenasAK,thatisAconcatenatedKtimes,forsomestringA.Ofcourse,wealsowanttoknowtheperiodTheinputconsistsofseveraltestcases.Eachtestcaseconsistsoftwolines.ThefirstonecontainsN(2<=N<=1000000)–thesizeofthestringS.ThesecondlinecontainsthestringS.Theinputfileendswithaline,havingthenumberzeroonForeachtestcase,output"Testcase#"andtheconsecutivetestcasenumberonasingleline;then,foreachprefixwithlengthithathasaperiodK>1,outputtheprefixsizeiandtheperiodKseparatedbyasinglespace;theprefixsizesmustbeinincreasingorder.Printablanklineaftereachtestcase.Sample3SampleTestcase23Testcase26912#include<stdio.h>#defineNcharintnext[N],{inti,j;i=1;next[1]=j=while(i<=len)if(j==0||arr[i]==arr[j])next[i]=}elsej=}}return}intmain(void)intncas,k,ncas=while(scanf("%d",&len),len)printf("Testcase#%d\n",ncas++);scanf("%s",&arr[1]); for(k=1;k<=len;k++)printf("%d",next[k]);for(k=2;k<=len;k++)if(k%((k+1)-next[k+1])==0)if(count!=1)printf("%d%d\n",k,}}}return}Pku2406--PowerGiventwostringsaandbwedefinea*btobetheirconcatenation.Forexample,ifa="abc"andb="def"thena*b="abcdef".Ifwethinkofconcatenationasmultiplication,exponentiationbyanon-negativeintegerisdefinedinthenormalway:a^0=""(theemptystring)anda^(n+1)=a*(a^n).Eachtestcaseisalineofinputrepresentings,astringofprintablecharacters.Thelengthofswillbeatleast1andwillnotexceed1millioncharacters.Alinecontainingaperiodfollowsthelasttestcase.Foreachsyoushouldprintthelargestnsuchthats=a^nforsomestringSample.Sample143#include<stdio.h>#defineNcharintnext[N],len;{inti,j;i=1;next[1]=j=while(i<=len)if(j==0||arr[i]==arr[j])next[i]=}elsej=}}return}intmain(void)intk,while(scanf("%s",&arr[1]),arr[1]!={len=strlen(&arr[1]);if(len%((len+1)-next[len+1])==0)count=len/(len+1-next[len+count=printf("%d\n",}return}Pku2752--SeektheName,SeektheThelittlecatissofamous,thatmanycouplestrampoverhillanddaletoBy andaskedthelittlecattogivenamestotheirnewly-bornbabies.Theyseekthename,andatthesametimeseekthefame.Inordertoescapefromsuchboringjob,theinnovativelittlecatworksoutaneasybutfantasticalgorithm:Step1.Connectthefather'snameandthemother'sname,toanewstringStep2.Findaproperprefix-suffixstringofS(whichisnotonlytheprefix,butalsothesuffixofS).Example:Father='ala',Mother='la',wehaveS='ala'+'la'='alala'.prefix-suffixstringsofSare{'a','ala','alala'}.GiventhestringS,couldyouhelpthelittlecattowriteaprogramtocalculatethelengthofpossibleprefix-suffixstringsofS?(Hemightthankyoubygivingyourbabyaname:)Theinputcontainsanumberoftestcases.EachtestcaseoccupiesasinglelinethatcontainsthestringSdescribedabove.Restrictions:Onlylowercaselettersmayappearintheinput.1<=LengthofS<=Foreachtestcase,outputasinglelinewithintegernumbersinincreasingorder,denotingthepossiblelengthofthenewbaby'sname.SampleSample2491234#include<stdio.h>#defineN400005charT[N];intlen,result[N],next[N];voidget_next(){i=1;next[1]=j=while(i<=len)if(j==0||T[i]==next[i]=}elsej=}}return}intmain(void)intj,index,while(scanf