问题2836--黑曜石

2836: 黑曜石

时间限制: 1 Sec  内存限制: 256 MB
提交: 734  解决: 290
[状态] [讨论版] [提交] [命题人:]
题目描述

小凯在玩一个叫 Nimecraft(简称 NC)的游戏。

在这个物理模型极其逼真的游戏中,有四种方块类型:水、岩浆、黑曜石、空气。水、岩浆、黑曜石都是非空气方块。为了简化问题,假设所有方块没有 X 轴、Z 轴的区别,只有高度 (Y 轴) 不同。每个高度(整数)都有且仅有一个类型的方块。

游戏的运行机制如下:

  1. 水的流动规则:如果前一秒高度 h 的位置是水,高度 h - 1 的位置是空气,那么后一秒高度为 h - 1 的位置会变成水。
  2. 岩浆流动规则:如果前一秒高度 h 的位置是岩浆,高度 h - 1 的位置是空气,那么后一秒高度为 h - 1 的位置会变成岩浆。
  3. 黑曜石生成规则:如果前一秒高度 h 和高度 h - 1 的位置分别为水和岩浆(或岩浆和水),那么后一秒高度为 h - 1 的位置会变成黑曜石。
  4. 如果前一秒高度 h 和 h - 1 的位置不满足上面任一规则,则后一秒 h - 1 的位置保持原状。

给定所有非空气方块的类型和高度(所以其他位置都是空气),小凯想知道 1145141919810 秒后会有多少个黑曜石。

输入

第一行是 1 个整数 T,表示数据组数。

对于每组数据,第一行是 1 个整数 n,表示非空气方块的总数。

接下来的 n 行,第 i 行有 2 个整数 ci,hi,分别表示该非空气方块的类型和高度。其中 ci=1 表示类型为水,ci=2 表示类型为岩浆,ci=3 表示类型为黑曜石。

1T50,1n105,1ci3,109hi109,保证 n>100 的数据只出现 1 个。保证 hi 互不相同。不保证 hi 是升序 / 降序的。

输出
每组数据输出一行,包含一个整数,表示 1145141919810 秒后黑曜石的个数。
样例输入 Copy
3
2
1 2
2 1
3
1 4
3 2
2 1
6
1 6
1 5
2 4
1 3
2 2
1 1
样例输出 Copy
1
1
4
提示

对于第一个数据,第 0 秒从高到低:水、岩浆、空气、……;第 1 秒从高到低:水、黑曜石、岩浆、空气、……;第 2 秒及之后都不会生成新的黑曜石,因此输出 1。

对于第二个数据,不会生成新的黑曜石,因此答案为 1(一开始的 1 个)。

对于第三个数据,第 0 秒从高到低:水、水、岩浆、水、岩浆、水、空气、……;第 1 秒从高到低:水、水、黑曜石、黑曜石、黑曜石、黑曜石、水、空气、……;因此输出 4。

来源/分类