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

1、2021/3/101问题求解与程序设计第三讲 称重问题李文新2004.2 2004.6 2021/3/102内容提要 作业总结 - 1008 作业总结 - 1013 何林冬令营报告 称球问题 自学及讨论 征服者 作业2021/3/103作业总结 - 1008 题意 Haab 19个月 前18个月每月20天 第19个月5天0-19 月名 0-5 月名 Tzolkin 13个月 天数为20个轮转 1mix 2- 3- 问题 将Haab日期转换成Tzolkin日期 源程序 1008 源程序2021/3/104作业总结 - 1013 题意 12枚硬币，其中一枚是假币，可能轻也可能重 称三次，每次左右硬

2、币数目相等，结果：轻重平 问题 求出假币，并给出其轻重 源程序 1013源程序2021/3/105一类称球问题的解法长沙雅礼中学 何林2021/3/106问题的提出 给定N个球 有个比标准球重的次品混入其中 你有一架天平，用最少的次数找出这个次品。2021/3/107N = 312312是次品12是次品12是次品N=3时称1次就可以找出次品2021/3/108N = 9123456789ABCAB次品在A中次品在B中AB 通过一次称量，可以把次品可能存在的范围从9个，缩小到3个 N = 3的时候一次就能称出次品N = 9时称2次次品在C中AB2021/3/109更一般的情况N = 3k12k1

3、2k12kABC2021/3/1010更一般的情况ABABAB次品在A中次品在B中次品在C中范围缩小到原来的1/32021/3/1011更一般的情况 n = 3k+1, n = 3k+2和n=3k类似，也是均分成三堆 每次称量把范围大致缩小到原来的1/3 因此：从n个球中找次品至多要称log3n次。（统一表示取上整）2021/3/1012判定树log3n无疑是可行解。最优性为什么三分？因为天平只有三种可能：左偏、右偏、平衡2021/3/1013判定树称(1, 2)=13=79=46= log3nlog3n是最优解2021/3/1016小结 引进了有力工具：判定树。将主观的直觉严谨化。 三分法是

4、解决这类问题的根本着眼点。 三分时必须充分的均匀2021/3/1017ProblemConquerors batalion2021/3/1018Table of ContentsThe problemSolution2021/3/1019The problem CENTRAL EUROPEAN OLYMPIAD IN INFORMATICS 30 June 6 July 2002 Day 1: conquer Conquerors battalion Time limit: 1 s Memory limit: 16 MB2021/3/1020The problemIn the whole hi

5、story of mankind one can find several curious battles, like the following one in France, in 1747. . .2021/3/1021The 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 the fortressthere was a wide st

6、aircase made out ofred marble. 2021/3/1022The problemOne day in the morning, the guardspotted a large battalionApproaching the fortress, with adreaded leader The Conqueror.2021/3/1023The problemWhen The Conqueror reached the fortress, he was already awaited by itscommandant. The commandantproposed:

7、“I see that you have manysoldiers behind you, standing on thestairs. We can play a small game: 2021/3/1024The 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 mo

8、veup one stair. 2021/3/1025The problemIf at least one of your soldiers reachesthe uppermost stair, you will be thewinner, in the other case, you will be theloser. 2021/3/1026The problemThe Conqueror immediately likedthis game, so he agreed and startedto conquer.2021/3/1027The problem TaskYour role i

9、s The Conquerors now. There are N stairs to the fortress (2 = N = 2000) and you have at most 1 000 000 000soldiers. 2021/3/1028The 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 sta

10、ir 1 at the beginning.2021/3/1029The 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.202

11、1/3/1030The problemThis is an 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

12、 of the soldiers). 2021/3/1031The problemIn 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.2021/3/1032The problemLibrary interfaceThe library libconq provides two ro

13、utines: start returns the number N and fills an array stairs with numbers of soldiersstanding on the stairs (i.e. there are stairsi soldiers standing on stair i)2021/3/1033The problem step takes an array subset (with at least N1 elements), describing thegroup of soldiers you chose, andreturns 1 or 2

14、 as described above; thegroup of soldiers is specified bynumbers of soldiers on each stair, as inthe start function2021/3/1034The 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 a

15、lso in C/C+ the stairs are numbered starting from 1.2021/3/1035The problemFollowing are 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(

16、int *subset);2021/3/1036The 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 groupcontaining all soldiers on randomly chosenstairs. Your real program will probably playthe rounds in an inf

17、inite loop.2021/3/1037The problemYou are strongly encouraged to define the arrays stairs and subset in the sameway as they are defined in the examplebelow.2021/3/1038The problemFreePascal example:uses libconq;var stairs: array1.2000 of longint;subset: array1.2000 of longint;i,N,result: longint;.star

18、t(N,stairs);.for i:=1 to N doif random(2)=0 then subseti:=0else subseti:=stairsi;result:=step(subset);.2021/3/1039The problem C/C+ example: #include libconq.h int 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

19、=step(subset);.2021/3/1040The 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.2021/3/1041The problemAn example of the gameYou: Library:start(N,stairs

20、) 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,1,0,0,0,0,0,

21、0) no return: you won2021/3/1042The problemThe for the exampleabovewould look like this:80 1 1 0 3 3 4 02021/3/1043SolutionLets 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 but o

22、ne stair higher. In this way, one soldier on the stair S is equivalent to two soldiers on the stairs S+1. 2021/3/1044SolutionFrom 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 Co

23、nqueror has won, have the value at least 2N-1 because there is a soldier on the stair number 1.2021/3/1045Solution1245312481625-12*25-24*25-38*25-416*25-5A soldier on stair Shas value 2N-S2021/3/1046Solution12453n1n2n3n1*25-2n2*25-3n3*25-4A positions value = sum (all soldiers)2021/3/1047Solution Los

24、ing positionsIf the value of the position is less than 2N-1 and the commandant plays optimally, the Conqueror will lose.2021/3/1048Solution ProofIf 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. Th

25、e commandant will choose this group to stay and the other to leave. 2021/3/1049SolutionWhen 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

26、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.2021/3/1050Solution Losing 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=

27、23= 22=22 (M=4, N=6) 23 + 23 + 22 +22 24Then K=2, 23 + 23 = 242021/3/1056Solution Proof 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) 2021/3/1057Solution Now let M2 and sum(ai,1=i 2N-2 Because ais are multiple of 2, sum(ai