#P2912. [Poi1997]Jump

    ID: 2033 传统题 1000ms 512MiB 尝试: 43 已通过: 9 难度: 8 上传者: 标签>CF2400提高+/省选-不变量分析Zeckendorf 表示高精度加法高精度乘法高精度减法

[Poi1997]Jump

题目描述

在一个无限长的棋盘上玩一种跳棋游戏,其中棋盘被划分成许多区域,每一个区域中可以放置多个的棋子。把初始棋局中最左边有棋子的区域编号定为 00,在它开始往左边连续的区域编号为 −1,−2,−3,…-1,-2,-3,\dots,在它的右边连续区域编号为 1,2,3,…1,2,3,\dots,若区域 pp 有棋子,那么棋子有两种跳法:

向左跳:则方格 p−1p-1 和 p−2p-2 中应增加一枚棋子,方格 pp 中应减少一枚棋子。

向右跳:则方格 pp 和 p+1p+1 中应减少一枚棋子,方格 p+2p+2 中应增加一枚棋子。

对于给定的初始棋局,经过若干步跳棋后,总可以找到一种目标,就是任意两个相邻区域中的棋子总数不超过 11。

对每个初始棋局,都能通过有限次操作到达唯一的目标棋局。请输出该目标棋局。

输入格式

  • 第一行为一个正整数 nn,表示棋盘中放置棋子的状态数。
  • 下面的 nn 行描述了每个状态,由两个用空格分隔的整数组成,第一个整数表示该区域的编号(0≤p≤1040\le p\le10^4),第二个整数表示该区域放置的棋子数目(1≤c≤1081\le c\le10^8)。这 nn 行按区域编号严格递增给出,第一行的区域编号为 00。

输出格式

  • 写出最终的棋局,这一行包含若干个整数,其中每一个整数为有棋子的区域编号,所有的区域按从小到大排列。
2
0 5
3 3
-4 -1 1 3 5

数据规模与约定

对于 100%100\% 的数据,1≤n≤1041 \le n \le 10^4。

题目来源