北京大学ACM国际大学生程序设计竞赛课件3

问题求解与程序设计第三讲称重问题李文新2004.2–2004.6内容提要作业总结-1008作业总结-1013何林冬令营报告–称球问题自学及讨论–征服者作业作业总结-1008题意•Haab19个月前18个月每月20天第19个月5天0-19月名0-5月名•Tzolkin13个月天数为20个轮转1mix2---3---…问题•将Haab日期转换成Tzolkin日期源程序1008源程序作业总结-1013题意•12枚硬币，其中一枚是假币，可能轻也可能重•称三次，每次左右硬币数目相等，结果：轻重平问题•求出假币，并给出其轻重源程序•1013源程序一类称球问题的解法长沙雅礼中学何林问题的提出给定N个球有个比标准球重的次品混入其中你有一架天平，用最少的次数找出这个次品。N=312312①是次品12②是次品12③是次品N=3时称1次就可以找出次品N=9123456789ABCAB次品在A中次品在B中AB•通过一次称量，可以把次品可能存在的范围从9个，缩小到3个•N=3的时候一次就能称出次品N=9时称2次次品在C中AB更一般的情况N=3k12k……12k……12k……ABC更一般的情况ABABAB次品在A中次品在B中次品在C中范围缩小到原来的1/3更一般的情况n=3k+1,n=3k+2和n=3k类似，也是均分成三堆每次称量把范围大致缩小到原来的1/3因此：从n个球中找次品至多要称[log3n]次。（[]统一表示取上整）判定树[log3n]无疑是可行解。最优性为什么三分？因为天平只有三种可能：左偏、右偏、平衡判定树称(1,2)=132叶子代表结果非叶子代表一次称量每个非叶子节点都有三个孩子，表示天平左偏、右偏、平衡判定树比较(1,2,3)与(4,5,6)=比较(1)与(2)13=2比较(7)与(8)79=8比较(4)与(5)46=5判定树的深度就是称量次数一个有意义的判定树至少n个叶子节点判定树N个叶子的三叉树的深度h=[log3n][log3n]是最优解小结引进了有力工具：判定树。将主观的直觉严谨化。三分法是解决这类问题的根本着眼点。三分时必须充分的均匀ProblemConqueror’sbatalionTableofContentsTheproblemSolutionTheproblemCENTRALEUROPEANOLYMPIADININFORMATICS30June–6July2002Day1:conquerConqueror’sbattalionTimelimit:1sMemorylimit:16MBTheproblemInthewholehistoryofmankindonecanfindseveralcuriousbattles,likethefollowingoneinFrance,in1747...TheproblemTherewasafortressinBassignac-le-Haut,asmallvillagelyingontheleftbankofriverDordogne,justovertheChastangdam.Fromthedamuptothefortresstherewasawidestaircasemadeoutofredmarble.TheproblemOnedayinthemorning,theguardspottedalargebattalionApproachingthefortress,withadreadedleader–TheConqueror.TheproblemWhenTheConquerorreachedthefortress,hewasalreadyawaitedbyitscommandant.Thecommandantproposed:“Iseethatyouhavemanysoldiersbehindyou,standingonthestairs.Wecanplayasmall‘game’:TheproblemIneachround,youwilldivideyoursoldiersintotwogroupsinanarbitraryway.ThenIwilldecidewhichoneofthemstaysandwhichonegoeshome.Eachsoldierthatstayswillthenmoveuponestair.TheproblemIfatleastoneofyoursoldiersreachestheuppermoststair,youwillbethewinner,intheothercase,youwillbetheloser.TheproblemTheConquerorimmediatelylikedthisgame,soheagreedandstartedto‘conquer’.TheproblemTaskYourroleisTheConqueror’snow.ThereareNstairstothefortress(2=N=2000)andyouhaveatmost1000000000soldiers.TheproblemForeachstair,youaregiventhenumberofsoldiersstandingonit,withnumber1beingtheuppermoststairandNthebottomone.Noneofyoursoldiersstandsonstair1atthebeginning.TheproblemForeachstartingpositiongiventoyourprogram,ifthepositioniswinning(i.e.thereisastrategythatenablesyoutowinthegameregardlessofyouropponent’smoves),Yourprogramshouldwin.Otherwiseitshouldjustplaythegame(andlose)correctly.TheproblemThisisaninteractiveproblem;youwillplayagainstalibraryasspecifiedbelow.Ineachround,yourprogramwilldescribeagroupofsoldierstoourlibrary.Thelibraryreturns1or2specifyingwhichgroupofsoldiersshouldstay(1meansthegroupyoudescribed,2meanstherestofthesoldiers).TheproblemIncasethegameends(eitherbecauseyouwonortherearenomoresoldiersinthegame),thelibrarywillterminateyourprogramcorrectly.Yourprogrammaynotterminateinanyotherway.TheproblemLibraryinterfaceThelibrarylibconqprovidestworoutines:•start–returnsthenumberNandfillsanarraystairswithnumbersofsoldiersstandingonthestairs(i.e.therearestairs[i]soldiersstandingonstairi)Theproblem•step–takesanarraysubset(withatleastN1elements),describingthegroupofsoldiersyouchose,andreturns1or2asdescribedabove;thegroupofsoldiersisspecifiedbynumbersofsoldiersoneachstair,asinthestartfunctionTheproblemIfyoufailtospecifyavalidgroupofsoldiers,thegamewillbeterminatedandyourprogramwillscorezeropointsfortheparticulartestcase.PleasenotethatalsoinC/C++thestairsarenumberedstartingfrom1.TheproblemFollowingarethedeclarationsoftheseroutinesinFreePascalandC/C++:procedurestart(varN:longint;varstairs:arrayoflongint);functionstep(subset:arrayoflongint):longint;voidstart(int*N,int*stairs);intstep(int*subset);TheproblemBelowyoucanfindexamplesoflibraryusageinbothFreePascalandC/C++;bothfragmentsdothesame–startthegameandthenplayoneround,withthechosengroupcontainingallsoldiersonrandomlychosenstairs.Yourrealprogramwillprobablyplaytheroundsinaninfiniteloop.TheproblemYouarestronglyencouragedtodefinethearraysstairsandsubsetinthesamewayastheyaredefinedintheexamplebelow.TheproblemFreePascalexample:useslibconq;varstairs:array[1..2000]oflongint;subset:array[1..2000]oflongint;i,N,result:longint;...start(N,stairs);......fori:=1toNdoifrandom(2)=0thensubset[i]:=0elsesubset[i]:=stairs[i];result:=step(subset);...TheproblemC/C++example:#includelibconq.hintstairs[2001];intsubset[2001];inti,N,result;...start(&N,stairs);...for(i=1;i=N;i++)if(rand()%2==0)subset[i]=0;elsesubset[i]=stairs[i];result=step(subset);...TheproblemYouhavetolinkthelibrarytoyourprogram–byuseslibconq;inFreePascalandby#includelibconq.h“inC/C++,whereyouhavetocompileyourprogrambyaddinglibconq.ctothecompilerarguments.TheproblemAnexampleofthegameYou:Library:start(N,stairs)N=8,stairs=(0,1,1,0,3,3,4,0)step((0,1,0,0,1,0,1,0))returns2(0,0,1,0,2,3,3,0,0)step((0,1,0,0,0,1,0,0))returns2(0,0,0,2,3,2,0,0,0)step((0,0,0,3,2,0,0,0))returns1(0,