《北京大学ACM国际大学生程序设计竞赛.ppt》由会员分享，可在线阅读，更多相关《北京大学ACM国际大学生程序设计竞赛.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源程序一类称球问题的解法长沙雅礼中学 何林
2、问题的提出给定N个球有个比标准球重的次品混入其中你有一架天平，用最少的次数找出这个次品。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个
3、球中找次品至多要称log3n次。（统一表示取上整）判定树log3n无疑是可行解。最优性为什么三分？因为天平只有三种可能：左偏、右偏、平衡判定树称(1, 2)=13=79=46= log3nlog3n是最优解小结引进了有力工具：判定树。将主观的直觉严谨化。三分法是解决这类问题的根本着眼点。三分时必须充分的均匀ProblemConquerors batalionTable of ContentsThe problemSolutionThe problemCENTRAL EUROPEAN OLYMPIAD IN INFORMATICS30 June 6 July 2002Day 1: conquer
4、 Conquerors battalionTime limit: 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 ov
5、er the Chastangdam. From the dam up to 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 aw
6、aited by itscommandant. The commandantproposed: “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
7、.Each soldier that stays will then moveup one stair. 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 rol
8、e is The Conquerors now. There are N stairs to the fortress (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
9、the beginning.The problemFor each starting position given to your program, 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
10、interactive problem; you will play against a library as specified below. Ineach 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 problem
11、In case the game ends (either becauseyou won or there are no more soldiersin the 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 arra
12、y stairs with numbers of soldiersstanding on the stairs (i.e. there are stairsi soldiers 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 bynumber
13、s of soldiers on each stair, as inthe start functionThe problemIf you fail to specify a valid 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 a
14、re the declarations of these routines in FreePascal and C/C+:procedure start(var N: longint; var 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 an
15、d C/C+; bothfragments do the same start the game andthen play one round, with the chosen groupcontaining 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 same
16、way as they are defined in the examplebelow.The problemFreePascal example:uses libconq;var stairs: array1.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+ exa
17、mple:#include libconq.hint stairs2001;int subset2001;int i,N,result;.start(&N, stairs);.for (i=1;i=N;i+)if (rand()%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 yo
18、u have to compileyour program by adding libconq.c to thecompiler arguments.The problemAn example of the gameYou: Library: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,
19、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,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
20、. 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 but 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
21、 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 won, 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-SSolu
22、tion12453n1n2n3n1*25-2n2*25-3n3*25-4A positions value = sum (all soldiers)SolutionLosing positionsIf the value of the position is less than 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
23、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. SolutionWhen 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 sol
24、dier 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 less 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(a
25、i,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-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-2Bec
26、ause 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 of the soldiers values is at least 2N-1, we may select the first (eg. Closet to the top of the staircase) f
27、ew 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
