#P6899. 修电脑
修电脑
时间限制 10 秒,内存限制 512 MB。
题目背景
是谁惊艳了时光,然后埋没了年华。
题目描述
布莱克在 WC 考场上愉快的写代码的时候,脚一抖踢掉了电源线,于是他杯具了。
布莱克冷静的举手示意,结果被告知修电脑的人咕咕咕了,给他延长了十五分钟让他自行解决。
于是布莱克开始了操作,结果发现他的电脑电路好像非同一般。
一个完整的电路由 行 列的电路元件组成,可以用 代表第 行第 列的元件。每个元件都需要被赋予一定量的电流 才能够正常工作(当然电流不能是负的,否则这个元件就会 了)。
这么奇怪的电路,当然不可能这么简单就开始运作了。每一对横向相邻的元件在运作时的联系是非常紧密的,因此它们的电流之和不能过低或过高。为了保证这一点,电路中每一对横向相邻的元件之间连有一个接收器,连接 和 的接收器有两个属性 和 ,代表它所连接的两个元件电流之和不得低于 且不得高于 ,当不满足要求时接收器会自动将整个电路断电。
除此之外,每对纵向相邻的元件在运作时会有频繁的信息传输,因此理所当然的,两个元件的电流之差不能够太大,否则信息传输的代价会过于昂贵。所以电路中还在每一对纵向相邻的元件之间连接了一个限制器,连接 和 的限制器有一个属性 ,表示它所连接的两个元件电流之差的绝对值不得超过这个值,否则限制器也会将整个电路断电。
布莱克当然不希望他的电路会因为这些奇怪的原因无法运作,因此他想找出一种能够使电路运行起来的配置方案。然而他在研究的过程中发现接收器和限制器的参数有时会发生变化,为了维持电脑的工作,他决定将初始状态和每一次变化后的状态的配置方案求出,以拯救他的 WC。
输入格式
从 circuit.in 中读入数据。
输入有多组数据,第一行为一个整数 ,表示数据组数。对于每组数据:
第一行两个整数 ,代表这是一个 行 列的电路。
接下来 行,每行 个数,第 行第 列表示 。
接下来 行,每行 个数,第 行第 列表示 。
接下来 行,每行 个数,第 行第 列表示 。
接下来一行一个整数 ,代表变化次数。
接下来 行,每行四个整数 :
- 如果 ,代表 变为 。
- 如果 ,代表 变为 。
- 如果 ,代表 变为 。
原赛使用随题发放的生成器 dmk,以不同的随机种子生成测试数据。
输出格式
输出数据到 circuit.out 中。
本题使用特殊评测。
约定初始状态为时刻 ,第 次变化之后的状态为时刻 。
对于每组数据:
第一行一个整数 ,代表没有合法配置方案的时刻数目。
接下来一行 个严格递增的数,代表所有无解的时刻。如果 ,则这一行为空。
接下来共 行,其中第 行描述元件 。对于每一行:
第一个整数为 ,接下来是 对整数 。每一对表示在时刻 ,元件 的电流设置为 。
你需要保证你的所有输出都在 位带符号整数类型范围内。如果某个时刻是无解的,那么所有元件的答案无论为何值都是合法的。
样例
1
2 2
5
3
7
15
2 2
2
1 1 1 7
1 2 1 12
1
2
2 0 3 1 4
2 0 2 1 3
2 0 1 1 2
2 0 4 1 1
样例解释
输出样例给的时刻 的答案为:
输出样例给的时刻 的答案为:
时刻 要求第二行两元件的电流和至少为 。第一行的电流和至多为 ,两列各自的上下电流差至多为 ,所以第二行电流和至多为 ,无解。
数据规模与约定
| 数据编号 | 其他约定 | 编号 | |
|---|---|---|---|
| / | |||
| / | |||
| / | |||
| / |
:。
:保证存在一种解使所有元件的答案 。
对于所有数据,,,,,。