1、題目來源：POI97 Problem2者：情況：可以通過構(gòu)造法來解決問題。理由：由于題目的數(shù)據(jù)量很大，一看即知不可能用搜索解決，且無法套用任何現(xiàn)成的算法，只能通過巧妙的構(gòu)造來解決，因此為大家留下了很大的發(fā)揮空間，各人可以設(shè)計(jì)出各種不同的構(gòu)造方法，因此希望和大家。JumpsJumps is a board game played on an infinite tof squares. Th has neither left nor right limit. On the squares there is finiy many t thepie(moren onece on a square is

2、 allowed). We amemost left, non-empty square is numbered 0. Squares on the right are denoted by consecutive natural numbers 1, 2, 3, ., squares on the left - by negative numbers: -1, -2, -3, . . The configuration of pie on theboard by piecan be describedhe following way: for every square occupiedeas

3、t onece we give the number of the square and the number ofstanding on this square. There are two kinds of movest canchange the configuration: jump right and jump left. Jump right consistsof removino piefrom th: one from a square p and the other ece on the square p+2. Jump leftfrom the square p+1, an

4、d placing onconsists of removing a piece from a square p+2 and placino pieonth: one on the square p+1 and the other on the square p. We sayt a configuration contains at most on final configuration (jumps).is final if each pair of neighbouring squares ece. For every configuration there is exactly one

5、 t can be reached after finite number of movesTaskWritea programt:reads a description of an initial configuration 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.her

6、e is oneitiveeger n, 1= n = 10000, which equals the number of non-empty squares of the given initial configuration. In each of the following n lines there is adescription of one non-empty a description consists of two second - the number of piesquare of the initial configuration. Suchegers.is the nu

7、mber of the square,standing on this square. The descriptionsare given in increasing order with respect biggest number of a square is not greaterto numbers of squares. The n 10000 and the number of n 100000000.pieon a single square is not greaterOutputheline of the file SKO.OUT thereshould be written

8、 the finalconfiguration More precisely (in increasingt can be reached from the given initial configuration.the line should contahe numbers of non-empty squaresorder) of the final configuration. The numbers should beseparated by single spa.ExleFor the text file SKO.IN20 53 3the correct solution is th

9、e file SKO.OUT-4 -1 1 3 5POI97Problem2跳躍“跳躍”是一個(gè)棋盤，在一個(gè)無限大的帶狀方格上進(jìn)行。棋盤既沒有左邊界也沒有右邊界。在棋盤上放著有限的棋子（一格上可以有多個(gè)棋子）。假定最左非空的方格被標(biāo)號為 0。右邊的方格被表示成連續(xù)的自然數(shù) 1, 2, 3, .，左邊的方格被表示成負(fù)整數(shù)：-1, -2, -3, .。棋盤上棋子的放置方式被描述為以下方式：給出每一個(gè)至少有一個(gè)棋子的方格的標(biāo)號以及方格上棋子的個(gè)數(shù)。有兩種移動(dòng)方式可以改變棋子的放置方式：右跳與左跳。右跳有以下步驟，從棋盤上移走兩個(gè)棋子：一個(gè)從方格p，另一個(gè)從方格p+1，并且在方格p+2 上放上一個(gè)棋子。

10、左跳有以下步驟，從方格p+2 移走一個(gè)棋子，并且在棋盤上放置兩個(gè)棋子：一個(gè)放在方格p+1 上，另一個(gè)放在方格 p 上。一個(gè)最終狀態(tài)定義為：兩個(gè)相鄰方格至多只有一個(gè)棋子。對于每一個(gè)棋盤放置方式可以通過有限步來達(dá)到一種最終狀態(tài)，并且只有一種最終狀態(tài)。任務(wù)寫一個(gè)程序：從輸入文件SKO.IN 中讀入棋盤初始狀態(tài)的描述找出所給初始狀態(tài)可以達(dá)到的最終狀態(tài)，并且將最終狀態(tài)的描述輸出到輸出文件SKO.OUT。輸入在輸入文件SKO.IN 的第一行有一個(gè)正整數(shù)n，1 = n = 10000，表示非空方格的數(shù)目。在接下來的每一行中有兩個(gè)整數(shù)。第一個(gè)是方格的標(biāo)號，第二個(gè)是方格上棋子數(shù)目。描述以方格標(biāo)號的升序順序給出。其中最大的方