![解题报告第一赛problem_第1页](http://file4.renrendoc.com/view/ecee8f4f33ae200cd47e9573098e4f95/ecee8f4f33ae200cd47e9573098e4f951.gif)
![解题报告第一赛problem_第2页](http://file4.renrendoc.com/view/ecee8f4f33ae200cd47e9573098e4f95/ecee8f4f33ae200cd47e9573098e4f952.gif)
![解题报告第一赛problem_第3页](http://file4.renrendoc.com/view/ecee8f4f33ae200cd47e9573098e4f95/ecee8f4f33ae200cd47e9573098e4f953.gif)
![解题报告第一赛problem_第4页](http://file4.renrendoc.com/view/ecee8f4f33ae200cd47e9573098e4f95/ecee8f4f33ae200cd47e9573098e4f954.gif)
![解题报告第一赛problem_第5页](http://file4.renrendoc.com/view/ecee8f4f33ae200cd47e9573098e4f95/ecee8f4f33ae200cd47e9573098e4f955.gif)
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
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
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 美联储-收入冲击及其向消费的传导(英)
- 教科版科学四年级下册第三单元《岩石与土壤》测试卷【必刷】
- 西师大版三年级下册数学第五单元-小数的初步认识-测试卷带答案ab卷
- 2024学年初中校园安全警钟长鸣人人知晓班会教学设计
- 《习作:插上科学的翅膀飞》(教学设计)2023-2024学年统编版语文六年级下册
- 2024学年中职生千万条安全措施安全知识必须学好班会教学设计
- 六年级下册道德与法治第二单元-爱护地球-共同责任-测试卷含答案【b卷】
- 人教版六年级下册数学-期中测试卷带答案
- 三 第6课时 手拉手2023-2024学年四年级下册数学同步教案(北师大版)
- 六年级下学期数学新初一分班考真题模拟卷带答案(模拟题)
- 2024年上海市普通高中学业水平等级性考试地理试卷(含答案解析)
- 酿酒工厂设计概论智慧树知到期末考试答案章节答案2024年齐鲁工业大学
- 2024年度保密教育线上培训考试题库及答案
- 中高端酒店销售方案(2篇)
- 物理与文化智慧树知到期末考试答案章节答案2024年山东大学
- 2024年江苏省南通张謇文化旅游景区招聘3人历年公开引进高层次人才和急需紧缺人才笔试参考题库(共500题)答案详解版
- 4.1 走向生态文明(教学设计)高二地理同步备课系列(人教版2019选择性必修3)
- 湖南省长沙市宁乡市2022-2023学年五年级下学期期末素养检测英语试卷
- 【公文基础】公文写作培训公文写作格式以及要点
- 幼小衔接教研活动方案及流程
- 2023年天津市中考地理真题卷(含答案与解析)
评论
0/150
提交评论