信息学集训队作业0040-jump

1、题目 0040 Jump（跳跃）题目来源：Poi97者：一、英文原文JumpsJumps is a board game played on an infinite tof squares. Thhas neither left nor right limit.On the squares there is fini y many pie(moren onece on a square is allowed). We amet the most left, non-empty square is numbered 0. Squares on the right are denoted by c

2、onsecutivenatural numbers 1, 2, 3, ., squares on the left - by negative numbers: -1, -2, -3,The configurationof pieon thcan be describedhe following way: for every square occupied byeast onepiece we give the number of the square and the number of piestanding on this square. There are twokinds of mov

3、est can change the configuration: jump right and jump left. Jump right consists ofremovino piefrom th: one from a square p and the other from the square p+1, andplacing onece on the square p+2. Jump left consists of removing a piece from a square p+2 andplacino pieon th: one on the square p+1 and th

4、e other on the square p. We sayt aconfiguration is final if each pair of neighbouring squares contains at most onece. For everyconfiguration there is exactly one final configuration(jumps).t can be reached after finite number of movesTaskWrite a programt:reads a description of an initial configurati

5、on from the text file SKO.IN,finds the final configurationt can be reached from the given initial configuration andwrites the result to the text file SKO.OUT.Inputheline of the file SKO.here is oneitiveeger n, 1 = n = 10000, which equals thenumber of non-empty squares of the given initial configurat

6、ion. In each of the following n lines there isa description of one non-empty square of the initial configuration. Such a description consists of twoegers.is the number of the square, second - the number of piestanding on this square. Thedescriptions are given in increasing order with respect to numb

7、ers of squares. The biggest number of asquare is not greater100000000.n 10000 and the number of pieon a single square is not greaternOutputheline of the file SKO.OUT there should be written the final configurationt can be reachedfrom the given initial configuration. More precisely the line should co

8、ntahe numbers of non-emptysquares (in increasing order) of the final configuration. The numbers should be separated by singlespa.ExleFor the text file SKO.IN 20 53 3the correct solution is the file SKO.OUT-4 -1 1 3 5二、中文翻译跳跃“跳跃”是一个棋盘，在一个无限大的带状方格上进行。棋盘既没有左边界也没有右边界。在棋盘上放着有限的棋子（一格上可以有多个棋子）。假定最左非空的方格被标号

9、为 0。右边的方格被表示成连续的自然数 1, 2, 3, .，左边的方格被表示成负整数：-1, -2, -3, .。棋盘上棋子的放置方式被描述为以下方式：给出每一个至少有一个棋子的方格的标号以及方格上棋子的个数。有两种移动方式可以改变棋子的放置方式：右跳与左跳。右跳有以下步骤，从棋盘上移走两个棋子：一个从方格 p，另一个从方格 p+1，并且在方格 p+2 上放上一个棋子。左跳有以下步骤，从方格 p+2 移走一个棋子，并且在棋盘上放置两个棋子：一个放在方格 p+1 上，另一个放在方格 p 上。一个最终状态定义为：两个相邻方格至多只有一个棋子。对于每一个棋盘放置方式可以通过有限步来达到一种最终状态

10、，并且只有一种最终状态。任务写一个程序：从输入文件 SKO.IN 中读入棋盘初始状态的描述找出所给初始状态可以达到的最终状态，并且将最终状态的描述输出到输出文件 SKO.OUT。输入在输入文件 SKO.IN 的第一行有一个正整数 n，1 = n 0) and (numI-1 0) then begin /执行号操作，实际上是 k 步右移K ( min( numI-1, numI ) + 1 ) div 2从 I-1 号格子和 I 号格子分别里取走 k 个棋子在 I+1 号格子里放上 k 个棋子endelse if (numI 1) then begin/执行号操作，实际上是 k 步k (num

11、i + 1) div 2从 I 号格子里取走 k 个棋子在 I-1,I-2 号格子里放上 k 个棋子endenduntil 本次循环内未能进行一次操作时间不长，第 11 个点为 0.55s，其余均不超过 0.4 秒昆试图找出一种方案，使得无论怎样变换，总权值都不变。容易发现，f(i)=f(i-1)+f(i-2)，这就是 Fibonacci 数列的递推式。所以可以一遍扫描算出总权值，在通过从大到小的一次扫描确定出目标状态中哪些位置要放棋子。可以证明，每个总权值都存在分解方案，且分解方案唯一。可以推出一个则：0,0,2,0=1,0,0,1，再与右跳规则结合起来，由于棋子没有增长的趋势，所以可以经过

12、一系列步骤达到目标。先考虑只有一个格有棋子，且棋子数为 2k 的情况，作为预处理，把最终结局记下。以后如果碰到格子有多于 1 的棋子(设为 P)，则可在 O(logP)时间内把它分散。分散后数目都会变得很小，再结合右跳规则就可在很短时间内达到目标。时间复杂度为 O(LlogP)，L 为棋盘长度。绕向荣可以通过 Fibonacci 数列来做，如果给每个格子赋予 s 一个值的话，从最左到最右分别为 0，1，1，2，3那么每个棋子所在的格子的数值和加起来是不会变的，而题目要求每个位置上的棋子数不大于 1，就相当于将总数分为若干个不同的 Fibonnaci 数相加，而这样分的方案只有一种，那么就是最终

13、状态只有一种，而且次尽大的取 Fibonnaci 数，直到达到所需的值。可以算出应怎样分这个数，就是每这道题如果想到 Fibonacci 数列就容易解决了：如果给第 i 个位置打上一个分数 Fi，并规定 Fi=Fi1+Fi2（为了方便，可以设 F1=F0=1）那么无论怎样移动棋子，所有棋子所在位置分之和为一定值。这也就证明了目标状态是唯一确定的：因为把任意一个正数表示成 Fibonacci 数列的若干不相邻项和有且仅有一种表示方法（若有不妨也证一证，这里从略了）。而题目不需要求移动方法，只需求目标状态也就是 Fibonacci 数列的和的表示方法，就大可不必用构造算法构造方案，只要简单的输出结

14、果就行了，具体方法为：先求出所有棋子的“位置分”之和 S（需要高精度），再从大（F10100足以）到小（F0）的选择 Fibonacci 数：若 SFi，则输出 i，SSFi林希德一个无奈的算法，所有数据均 0.22s 内出解，但复杂度无法估算。定义：Min 和 Max 分别是当前存在棋子的最小和最大方格规定：操作 A：0 1 1 0 0 1操作 B：0 0 2 0 1 0 0 1主程序：RepeatFor i = Min Max do尝试操作 A；尝试操作 B；（操作同时动态修改 Min 和 Max 的值）End forUntil 本次迭代没有进行任何操作；。由于初始时,不为零的堆只可能为

15、0 至 10000,则最后结果,也不可能扩展到-100,及 10100以外(为了保证正确性,可扩大一些范围),由已知的两种操作,若遇到相邻两堆都大于零,则通过右操作将其中一堆清空,且可以设计出一组操作,可循环执行,最终通过有限次循环后,可使符合条件,且循环次数 k 不可能很大。下面为我实践出的操作方法：1.若发现有相邻两个方格 i 和 i+1，有 Ai0，Ai+10，则可以仅使用右跳使得：AiAi minAi,Ai+1,Ai+1Ai+1 minAi,Ai+1,Ai+2Ai+2 + minAi,Ai+1本步操作主要目的是使总子数尽可能的减少（并且可以使得任意两个非空方格不相邻）。然后出现如下状态

16、，分别2.Ai = 3(1)左操作： (2)右操作： (3)右操作：Ai-2Ai-2 + 1Ai-1Ai-1 1AiAi 1Ai-1Ai-1 + 1AiAi 1Ai+1Ai+1 1AiAi 1Ai+1Ai+1 + 1Ai+2Ai+2 1(4)若 Ai=3 则回到 1,否则结束总的结果为Ai-2Ai-2 + Ai/3 Ai=2AiAi 3*Ai/3Ai+2 Ai+2 + Ai/33.左操作：右操作：Ai-2Ai-2 + 1Ai-1Ai-1 1Ai-1Ai-1 + 1AiAi 1Ai Ai 1Ai+1Ai+1 + 1移动规则可归纳成：对于任意连续三格子，执行-1 1 +1 或者+1 +1 1。考虑如下两种规则：-1-1+1-1-1+1+1+1-1+10-30+1即：一个格子若有 3 个以上的棋子，就可以这样移动+1 0 3 0 +1。-11+1+1+1-1+10-2+1即：一个格子有 2 个棋子，可以这样移动+1 0 2 +1。按照这样的规则反复移动即可，所有的数据运行速度都很快。但时间复杂度我不知道如何估计。还有一个考虑的角度。比如样例，给每个位置一个权值：位置：-44-3-2-10123棋子数： 553权值：1552358132134给一个这样