解题报告第一赛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