解題報告第一賽problem

Theonestoremain

TimeLimit:1000ms,SpecialTimeLimit:2500ms,MemoryLimit:32768KBProblem11135:Nospecialjudgement

Problemdescription

ThereareNsoldiersstandinginoneline.Theyaremarkedfrom1toN,fromrighttoleft.Andtheyaregivenanumberm.Thenthesoldiersnumberedoff,straightfromtheright-handman.Theonewhoreportedanumberthatisthemultipleofmwaskeptintheline.Othershavetoleavetheline.Theycontinuedoingthistillthenumberofpeopleinthelineislessthanm.Forexample,ifthereare10soldiers,andm=3.Forthefirsttimethesoldierswhoaremarked3,6,9remainintheline.Forthesecondtimethesoldierwhoismarked9remainsintheline.Becausethenumberofsoldiersinthelineislessthanm,sothesoldiermarked9wastheonlyonetoremainintheline.

Nowwewanttoknowwhowillbetheonestoremain,canyoutellus?

Input

Thereareseveraltestcasesintheinput.Eachtestcasesisonlyoneline,containstwointegersnandm.(3<=n<=109,2<=m<=n).Theinputendswhenn=0andm=0.

Output

Foreachtestcase,outputtwolines.Thefirstlinecontainsoneintegerx,thenumberofsoldierstoremain.Thesecondlinecontainsxintegers,thenumbersmarkedonthesoldierswhoremainintheline.Youshouldoutputtheminincreasingorder.

SampleInput

103

83

00

SampleOutput

1

9

2

36

NumberGuessing

TimeLimit:1000ms,SpecialTimeLimit:2500ms,MemoryLimit:32768KBProblem11146:Nospecialjudgement

Problemdescription

NumberGuessingisacomputergame.First,thecomputerchoosesfourdifferentdigits,youneedtoguessthesefourdigitsinthefewesttimes，foreachguess,thecomputerwillshowajudgementintheformof"#A#B","#"isanumber0~4."#A"showshowmanydigitsyouguessedwithbothcorrectvalueandposition."#B"showshowmanydigitsyouguessedwithcorrectvalue.Forexample,thecomputerchose1234,andyouguessed6139,thecomputerwillshow"1A2B"foryouhavenumber"1"correctvaluebutwrongpositionandnumber"3"correctvaluewithcorrectposition.Thusthecomputergivesyouthejudgementof"1A2B"

Nowyouhavememorizedthedigitsyouguessedandthejudgementsyougot,youfeellikeyoucanfigureoutthecorrectanswer.Lifeisfilledwithwisdom,isn'tit?

Input

Thereareseveraltestcases.Foreachtestcase,thefirstlinecontainsasinglepositiveintegerNindicatesthetimesyoucanguess，thefollowingNlinesistherecordoftheguess,intheform:

#####A#B

Thefirstfournumbersisthenumbersguessed,thenthejudgementsforyourguess.TheinputterminatedwhenNisnotpostiveinteger,andnotneedtoproceed.

Output

Foreachtestcase,outputasinglelinecontainsexactlyfourdigitsthatthecomputerhaschosen.Youmayassumethateachtestcasegivesyouenoughinformation,soyoucanfigureoutthecorrectanswer.

SampleInput

2

12342A4B

12430A4B

3

07323A3B

15260A0B

45670A2B

-1

SampleOutput

2134

0734

ChineseChess

BothXnbyandHekuilikeplayingChineseChess.Therearetwosides:blackandred

(inthefiguresbelow,redisthepieceswithwhitecharacters)inChineseChess.Eachsidetakemovesinturns.Oneday,theymadeacomposition(Now,it’sred'sturn):

Bytheway,eachsidecanonlymovethe”Cannon”

and

the”Pawn”

.Thecannoncanmoveinstraightlinesatany

distance(fromonecrosstoanother)ifnootherchesspiecesblock

itsway.Andthepawncanonlymoveforward,oneunitperturn.(Forthered,top-bottomisforward,andfortheblack,bottom-top).

Afterthediscussion，theyallagreethatonlywhenoneside,forexample,theblackcannonisforcedtotakeahorizonalmovewhich

makestheredcannoncangettothehemlineoftheblack,thentheredwins(Seethefollowingfigure).

So,theymakeafewrules:

Thecannoncanonlymoveforward.Ifonesidehastomovethe“cannon”toleftorright,heloses.Noticethatitdoesn'tchangesituationifacannonmovesbackward,becausetheoppositesidecanmoveitscannonforwardforthesamedistance.

Onlythepawnswhichhaven'tcrossedtherivercanmove.Andthedistancebetweeneachpairofpawns(onered,oneblack)mustexceed1.

Thewinneronlydependsonthedistancemandn(betweenthepairofcannonsinthesameverticallinecountingfromtheleftside),S1,S2,S3(betweenthepairofpawns”whichnotcrosstheriverinthesameverticallinecountingfromtheleftside).

XnbyandHekuiwanttoknow:whichsideisthewinnerwheneachofthemmovesinthebeststrategy.Tomakeitmoreinteresting,

m,n,S1,S2,S3arenotlimitedbyChineseChessboard,inotherwords,Chessboardofthisgameislargeenough.

輸入

Thereareseveraltestcases,eachcaseinasinglelinewhichcontains5integersseparatedbyablank:m,n,S1,S2,S3,0≤m,n≤1000000,1≤S1,S2,S3≤1000。Theinputterminateswhenonelinecontainsasinglenegativeinteger,whichneedn'ttobeprocessed.

輸出

Foreachtestcase,outputthewinner(RedorBlack)

樣例輸入

41221

00111

-1

樣例輸出

RedBlack

PageReplacement

Pagereplacementalgorithmswereahottopicofresearchanddebateinthe1960sand1970s.ThatmostlyendedwiththedevelopmentofsophisticatedLRUapproximationsandworkingsetalgorithms.Sincethen,somebasicassumptionsmadebythetraditionalpagereplacementalgorithmswereinvalidated,resultinginarevivalofresearch.Inparticular,thefollowingtrendsinthebehaviorofunderlyinghardwareanduser-levelsoftwarehasaffectedtheperformanceofpagereplacementalgorithms:

Sizeofprimarystoragehasincreasedbymultipleordersofmagnitude.Withseveralgigabytesofprimarymemory,algorithmsthatrequireaperiodiccheckofeachandeverymemoryframearebecominglessandlesspractical.Memoryhierarchieshavegrowntaller.ThecostofaCPUcachemissisfarmoreexpensive.Thisexacerbatesthepreviousproblem.

Localityofreferenceofusersoftwarehasweakened.Thisismostlyattributedtothespreadofobject-orientedprogrammingtechniquesthatfavorlargenumbersofsmallfunctions,useofsophisticateddatastructuresliketreesandhashtablesthattendtoresultinchaoticmemoryreferencepatterns,andtheadventofgarbagecollectionthatdrasticallychangedmemoryaccessbehaviorofapplications.

Requirementsforpagereplacementalgorithmshavechangedduetodifferencesinoperatingsystemkernelarchitectures.Inparticular,mostmodernOSkernelshaveunifiedvirtualmemoryandfilesystemcaches,requiringthepagereplacementalgorithmtoselectapagefromamongthepagesofbothuserprogramvirtualaddressspacesandcachedfiles.Thelatterpageshavespecificproperties.Forexample,theycanbelocked,orcanhavewriteorderingrequirementsimposedbyjournaling.

Moreover,asthegoalofpagereplacementistominimizetotaltimewaitingformemory,ithastotakeintoaccountmemoryrequirementsimposedbyotherkernelsub-systemsthatallocatememory.Asaresult,pagereplacementinmodernkernels(Linux,FreeBSD,andSolaris)tendstoworkatthelevelofageneralpurposekernelmemoryallocator,ratherthanatthehigherlevelofavirtualmemorysubsystem.

Therearemanypagereplacementalgorithms,oneofthemisLRU:

Theleastrecentlyusedpage(LRU)replacementalgorithm,thoughsimilarinnametoNRU(Notrecentlyused),differsinthefactthatLRUkeepstrackofpageusageoverashortperiodoftime,whileNRUjustlooksattheusageinthelastclockinterval.LRUworksontheideathatpagesthathavebeenmostheavilyusedinthepastfewinstructionsaremostlikelytobeusedheavilyinthenextfewinstructionstoo.WhileLRUcanprovidenear-optimalperformanceintheory(almostasgoodasAdaptiveReplacementCache),itisratherexpensivetoimplementinpractice.Thereareafewimplementationmethodsforthisalgorithmthattrytoreducethecostyetkeepasmuchoftheperformanceaspossible.

OneimportantadvantageofLRUalgorithmisthatitisamenabletofullstatisticalanalysis.Ithasbeenproved,forexample,thatLRUcanneverresultinmorethanN-

7012

string

0304230321201701reference

7772 2 4440 1 11

000 0 0033 3 00 page

framesinpool

11 3 3222 2 27

Foragivenreferencestring,youneedtocalculatethenumberofpagefaults.

輸入

Thefirstlinecontainsaninteger,thenumberoftestcases.Eachtestcasecontainstwolines,thefirstlineisthecapacityofthemanagementpoolm(0<m≤10000),andthelengthofreferencestringn(0<n≤100000).Thenextlinecontainsexactlynintegers,whichindicatethereferencesequenceofpageframes(pagenumberrangedfrom0ton).

輸出

Foreachtestcase,theoutputshouldcontainsthenumberofpagefaultsthatoccurred.

樣例輸入

3

35

12345

35

12123

320

70120304230321201701

樣例輸出

5

3

12

STTask

YougetaSTtask,thatis:givenastickoneendofwhoismooredontheground,youareaskedtoturnoverthestickbyholdingtheotherend.Whenitreachesthegroundagain,thetaskisfinished.Itistruethatontheprocess,thestickisalwaysonthesameplaneverticaltheground.Andonthisplane,thereislightfromuptodown,sothatwecanseeonthegroundalineofshadow.Lookatthepicture:

Inordertoexpresstheshadowpartandtheun-shadow(lightspace)part,tosimpletheproblemwejustneedtoexpressthelengththat2timesofthelengthofthestickwheretheshadowmayoccur.

Now,givetheproblem:thestickonthebeginningisontheleftofthemooredpoint,andweturnitoncertainangularspeed,usinga‘S’todenoteoneunitofthelightspaceanda‘T’foroneunitoftheshadowline.Besidethat,arealnumberisneededtotellthescalebetweentheshadowlineandthefulllinewhereshadowmaybe.

輸入

Thereisonlyonecase.TwointegersL(0<L≤25)andV(0<V≤90)isgiven.Listhelengthofthestick;Vistheangularspeedoftheturningtask,inanglepersecond

輸出

Foreverysecondduringthetask,youareaskedtotelltheshapeoftheshadowontheground.Seethesample:‘S’forthelightspaceand‘T’fortheshadow.

樣例輸入

2515

樣例輸出

TTTTTTTTTTTTTTTTTTTTTTTTTSSSSSSSSSSSSSSSSSSSSSSSSS 0.50000

STTTTTTTTTTTTTTTTTTTTTTTTSSSSSSSSSSSSSSSSSSSSSSSSS 0.48296

SSSTTTTTTTTTTTTTTTTTTTTTTSSSSSSSSSSSSSSSSSSSSSSSSS 0.43301

SSSSSSSTTTTTTTTTTTTTTTTTTSSSSSSSSSSSSSSSSSSSSSSSSS 0.35355

SSSSSSSSSSSSTTTTTTTTTTTTTSSSSSSSSSSSSSSSSSSSSSSSSS 0.25000

SSSSSSSSSSSSSSSSSSSTTTTTTSSSSSSSSSSSSSSSSSSSSSSSSS 0.12941

SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS 0.00000

SSSSSSSSSSSSSSSSSSSSSSSSSTTTTTTSSSSSSSSSSSSSSSSSSS 0.12941

SSSSSSSSSSSSSSSSSSSSSSSSSTTTTTTTTTTTTTSSSSSSSSSSSS 0.25000

SSSSSSSSSSSSSSSSSSSSSSSSSTTTTTTTTTTTTTTTTTTSSSSSSS 0.35355

SSSSSSSSSSSSSSSSSSSSSSSSSTTTTTTTTTTTTTTTTTTTTTTSSS 0.43301

SSSSSSSSSSSSSSSSSSSSSSSSSTTTTTTTTTTTTTTTTTTTTTTTTS 0.48296

SSSSSSSSSSSSSSSSSSSSSSSSSTTTTTTTTTTTTTTTTTTTTTTTTT 0.50000

提示

Ifthestickis3inlength,andtheshadowlineis1.49,wehavetheanswerthismoment:SSTSSS0.24833Ifthestickis3inlength,andtheshadowlineis1.51,wehavetheanswerthismoment:STTSSS0.25167Thatis,thenumberof‘T’alwaysisthenearestintegerofthelengthofshadow.

8numbersproblem

Ithinkalmosteveryacmerwillknowthe8numbersproblemwhichisaveryfamousproblem.Thegamebeginfromtheinitialstateofa3*3matrixwhichmakesupof8numbers(1-8)andablankblock(0).movetheblankblockwithitsadjacentblockuntilreachtheobjectivestate.Itisobviousthattheblankblockhasfourdirectionswhichitcanmovetowhenitisatthemiddleposition,i.e.up,down,left,right.Also,ithastwodirectionswhenitisatthecornerofthematrixandthreedirectionsatotherposintion.Formexample,theinitialstateofthematrix:

803

214

765

theobjectivestate:

123

804

765

andwegiveavalidmovingpath:

8

0

3

8

1

3

8

1

3

0

1

3

1

0

3

1

2

3

2

1

4

>2

0

4

>0

2

4

>8

2

4

>8

2

4

>8

0

4

7

6

5

7

6

5

7

6

5

7

6

5

7

6

5

7

6

5

Moreover,thepathwithleaststepsiscalledtheshortestpath.Andthe8numbersischeckwhethertherearethepathfromtheinitialstatetotheobjectivestateandifitexists,givetheshortestpath.

Andweallknowhuicpc229isnotverygoodatsearch,sohehasn'tsolvedthisproblemnow.Buthehassolvedanothereasyproblem.Theproblemisdescribedasfollow:

Giveaninitialstateofthematrix,andgiveasequenceofmoving.Foreverymoving,iftheblankblockcanmovetothedirectionasthemoving,moveit,otherwiseignorethismoving.Andwewanttoknowthefinalstateofthematrix.

輸入

Thefirstlineoftheinputisoneintegert,thenumberoftestcase.Foreachtestcase:

Threelinesrespondtotheinitialstateofthematrix,andtherewillbethreenumbersoneachofthethreelines.

Followbyanintergermcorrespondingtothenumberofmoving.

Thenextmline,everylinecontainonlyonecharacter:

U:movetheblankblockupforoneblock.D:movetheblankblockdownforoneblock.L:movetheblankblockleftforoneblock.

R:movetheblankblockrightforoneblock.

輸出

Foreachtestcaseoutputthefinalstateofthematrixforthreelinesasabove.Andtherewillbeablankspacebetweeneverytwonumbersonthesameline.Andyoushouldoutputoneblanklineaftereachtestcase.

樣例輸入

1

803

214

765

2

DR

樣例輸出

813

240

765

TheQianJinTeachingBuilding

時間限制(普通/Java):10000MS/100000MS 運行內存限制:65536KByte

Whenyoutrytosolvethisproblem,Ithinkthereisonlyatmostonemonthleftforourfootmen(FM2008)stayingatourAlmaMater.Ithinkthesefouryearsisthehappiestandmostimportanttimeinallmylife.IlearnedtostudyandmetsomanysincerefriendsinourschoolespeciallyinourACMteam.Itistoosimplethatjustsay“THX”toexpressmysincerethank,butImustsay“Thankyou“foryouall.IsendmyparticularthanktoDoctorWuforyouhelpandcaretomeandthewholeACMteam.Huicpc3-15,myteammateatfootmen,isthemostimportantbosomfriendinmylife.WeareclassmatesintheMathematicsandAppliedMathematics05-

1.WetookpartintheMathematicalModelingContesttogether,andparticipatedinACMContestasteammates.Wesurmountedthedifficulties,sufferedthedefeatandenjoyedthegladofsuccesstogether.Togetherwetastedthejoysandsorrowsoflife.Butitisalwaystruethatpleasanthoursflypast,anditistimetopart.Ican’thelptorunbacktothetimewhenwestudiedintheQianjingteachingbuildingforourexaminationsandlearnedtheknowledgeaboutalgorithmandprogramming.

Asweallknowthenumbersofseatsintheclassroomsarenotalwayssame.Whentheexaminationweekcomes,therewillbethesecasesthatitistoolargeforaclassbutthereisnosmallclassroomwhichisenoughforthem.Somanyseatsareleftunusedbutwecan’tuse.SoeverytimewewenttotheQianjinteachingbuildingtostudy,itisahardtimetofindafreeclassroom.Ireallylikeifth