北京大学ACM国际大学生程序设计竞赛课件3(精品).ppt

《北京大学ACM国际大学生程序设计竞赛课件3(精品).ppt》由会员分享，可在线阅读，更多相关《北京大学ACM国际大学生程序设计竞赛课件3(精品).ppt（62页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、问题求解与程序设计第三讲 称重问题李文新2004.2 2004.6 内容提要作业总结-1008作业总结-1013何林冬令营报告 称球问题自学及讨论 征服者作业作业总结-1008题意Haab 19个月 前18个月每月20天 第19个月5天0-19 月名 0-5 月名Tzolkin 13个月 天数为20个轮转 1mix 2-3-问题将Haab日期转换成Tzolkin日期源程序 1008 源程序作业总结-1013题意12枚硬币，其中一枚是假币，可能轻也可能重称三次，每次左右硬币数目相等，结果：轻重平问题求出假币，并给出其轻重源程序1013源程序一类称球问题的解法长沙雅礼中学 何林问题的提出给定N个球

2、有个比标准球重的次品混入其中你有一架天平，用最少的次数找出这个次品。N=312312是次品12是次品12是次品N=3时称1次就可以找出次品N=9123456789ABCAB次品在A中次品在B中AB 通过一次称量，可以把次品可能存在的范围从9个，缩小到3个 N=3的时候一次就能称出次品N=9时称2次次品在C中AB更一般的情况N=3k12k12k12kABC更一般的情况ABABAB次品在A中次品在B中次品在C中范围缩小到原来的1/3更一般的情况 n=3k+1,n=3k+2和n=3k类似，也是均分成三堆每次称量把范围大致缩小到原来的1/3因此：从n个球中找次品至多要称log3n次。（统一表示取上整）

3、判定树log3n无疑是可行解。最优性为什么三分？因为天平只有三种可能：左偏、右偏、平衡判定树称(1,2)=13=79=46=log3nlog3n是最优解小结引进了有力工具：判定树。将主观的直觉严谨化。三分法是解决这类问题的根本着眼点。三分时必须充分的均匀ProblemConquerors batalionTable of ContentsThe problemSolutionThe problemCENTRAL EUROPEAN OLYMPIAD IN INFORMATICS30 June 6 July 2002Day 1:conquer Conquerors battalionTime li

4、mit:1 sMemory limit:16 MBThe problemIn the whole history of mankind one can find several curious battles,like the following one in France,in 1747.The problemThere was a fortress in Bassignac-le-Haut,a small village lying on the left bankof river Dordogne,just over the Chastangdam.From the dam up to

5、the fortressthere was a wide staircase made out ofred marble.The problemOne day in the morning,the guardspotted a large battalionApproaching the fortress,with adreaded leader The Conqueror.The problemWhen The Conqueror reached the fortress,he was already awaited by itscommandant.The commandantpropos

6、ed:“I see that you have manysoldiers behind you,standing on thestairs.We can play a small game:The problemIn each round,you will divide your soldiers into two groups in an arbitraryway.Then I will decide which one ofthem stays and which one goes home.Each soldier that stays will then moveup one stai

7、r.The problemIf at least one of your soldiers reachesthe uppermost stair,you will be thewinner,in the other case,you will be theloser.The problemThe Conqueror immediately likedthis game,so he agreed and startedto conquer.The problemTaskYour role is The Conquerors now.There are N stairs to the fortre

8、ss(2=N=2000)and you have at most 1 000 000 000soldiers.The problemFor each stair,you are given the numberof soldiers standing on it,with number 1being the uppermost stair and N thebottom one.None of your soldiersstands on stair 1 at the beginning.The problemFor each starting position given to your p

9、rogram,if the position is winning(i.e.thereis a strategy that enables you to win thegame regardless of your opponents moves),Your program should win.Otherwise itshould just play the game(and lose)correctly.The problemThis is an interactive problem;you will play against a library as specified below.I

10、neach round,your program will describe agroup of soldiers to our library.The libraryreturns 1 or 2 specifying which group ofsoldiers should stay(1 means the group youdescribed,2 means the rest of the soldiers).The problemIn case the game ends(either becauseyou won or there are no more soldiersin the

11、 game),the library will terminateyour program correctly.Your programmay not terminate in any other way.The problemLibrary interfaceThe library libconq provides two routines:start returns the number N and fills an array stairs with numbers of soldiersstanding on the stairs(i.e.there are stairsi soldi

12、ers standing on stair i)The problem step takes an array subset(with at least N1 elements),describing thegroup of soldiers you chose,andreturns 1 or 2 as described above;thegroup of soldiers is specified bynumbers of soldiers on each stair,as inthe start functionThe problemIf you fail to specify a va

13、lid group of soldiers,the game will be terminatedand your program will score zero pointsfor the particular test case.Please notethat also in C/C+the stairs are numbered starting from 1.The problemFollowing are the declarations of these routines in FreePascal and C/C+:procedure start(var N:longint;va

14、r stairs:array of longint);function step(subset:array of longint):longint;void start(int*N,int*stairs);int step(int*subset);The problemBelow you can find examples of libraryusage in both FreePascal and C/C+;bothfragments do the same start the game andthen play one round,with the chosen groupcontaini

15、ng all soldiers on randomly chosenstairs.Your real program will probably playthe rounds in an infinite loop.The problemYou are strongly encouraged to define the arrays stairs and subset in the sameway as they are defined in the examplebelow.The problemFreePascal example:uses libconq;var stairs:array

16、1.2000 of longint;subset:array1.2000 of longint;i,N,result:longint;.start(N,stairs);.for i:=1 to N doif random(2)=0 then subseti:=0else subseti:=stairsi;result:=step(subset);.The problemC/C+example:#include libconq.hint stairs2001;int subset2001;int i,N,result;.start(&N,stairs);.for(i=1;i=N;i+)if(ra

17、nd()%2=0)subseti=0;else subseti=stairsi;result=step(subset);.The problemYou have to link the library to yourprogram by uses libconq;inFreePascal and by#include libconq.h“in C/C+,where you have to compileyour program by adding libconq.c to thecompiler arguments.The problemAn example of the gameYou:Li

18、brary:start(N,stairs)N=8,stairs=(0,1,1,0,3,3,4,0)step(0,1,0,0,1,0,1,0)returns 2(0,0,1,0,2,3,3,0,0)step(0,1,0,0,0,1,0,0)returns 2(0,0,0,2,3,2,0,0,0)step(0,0,0,3,2,0,0,0)returns 1(0,0,0,3,2,0,0,0,0)step(0,0,2,0,0,0,0,0)returns 2(0,0,1,2,0,0,0,0,0)step(0,1,0,0,0,0,0,0)returns 2(0,0,2,0,0,0,0,0,0)step(0

19、,1,0,0,0,0,0,0)no return:you wonThe problemThe file libconq.dat for the exampleabovewould look like this:80 1 1 0 3 3 4 0SolutionLets try to tell somehow how good a position is.If we have two soldiers on the same stair(and no other soldiers),in the next round we will have at most only one soldier bu

20、t one stair higher.In this way,one soldier on the stair S is equivalent to two soldiers on the stairs S+1.SolutionFrom now on a soldier on the stair S will have the value 2N-S.The value of a position will be the sum of the values of all the soldiers.Note that all positions,where the Conqueror has wo

21、n,have the value at least 2N-1 because there is a soldier on the stair number 1.Solution1245312481625-12*25-24*25-38*25-416*25-5A soldier on stair Shas value 2N-SSolution12453n1n2n3n1*25-2n2*25-3n3*25-4A positions value=sum(all soldiers)SolutionLosing positionsIf the value of the position is less th

22、an 2N-1 and the commandant plays optimally,the Conqueror will lose.SolutionProofIf the value is less than 2N-1,the Conqueror didnt win yet.Lets take a look at one round of the game.The Conqueror divides his soldiers in some way.The commandant will choose this group to stay and the other to leave.Sol

23、utionWhen any soldier moves up one stair,his value doubles.Therefore the value of the new position will be less than 2*2N-2=2N-1 and the number of the soldier will decrease.There is a finite number of soldiers,and so the game ends in a finite number of moves.The value of a position will always be le

24、ss than 2N-1,also at the end there will be no soldiers and the Conqueror will lose.SolutionLosing position2N-1=a1=aM,M=2)be powers of two with sum(ai,1=i=2N-2.Then for some K holds sum(ai,1=i=23=23=22=22 (M=4,N=6)23+23+22+22 24Then K=2,23+23=24SolutionProof Induction on M.For M=2 the lemma holds.2N-

25、2=a1=a2 a1+a2=2N-2 Either a1=2N-2(k=1)or(a1=a2=2N-3 and a1+a2=2N-2(k=2)SolutionNow let M2 and sum(ai,1=i 2N-2Because ais are multiple of 2,sum(ai,1=i=M)=k1aM 2N-2=k2aMTherefore sum(ai,1=i=2N-2+aMThen sum(ai,1=i=2N-2We may apply the induction assumption.SolutionFrom the lemma we get that if the sum o

26、f the soldiers values is at least 2N-1,we may select the first(eg.Closet to the top of the staircase)few of them so that the sum of their values will be exactly 2N-2.The Conqueror may also divide his soldiers into these two groups.Solution32N-342N-442N-452N-52N-2SolutionIf we are in a losing position,we choose an empty set and loose instantly.If we are in a winning position,we find the place where to split the soldiers by adding the values of soldiers on stairs 1,2,until the value reaches 2N-2.本节课小结作业总结-1008作业总结-1013何林冬令营报告 称球问题自学及讨论 征服者作业作业10161048