分数: 800 点
问题陈述
给定非负整数序列: A = (A_1, \ldots, A_N) 和 B=(B_1, \ldots, B_N).
判断是否可以 A 等于 B 通过在之间执行以下操作 0 和 N 次,含在内。
- 操作:选择整数 x,y 这样 0\leq x < y\leq 10^{18}。对于每一个 i,替换 A_i 与 (A_i+x)\bmod y.
如果可以 A 等于 B,打印一种方法。
约束
- 1\leq N\leq 1000
- 0\leq A_i\leq 10^9
- 0\leq B_i\leq 10^9
输入
输入由标准输入按以下格式给出:
N A_1 \ldots A_N B_1 \ldots B_N
输出
如果不能 A 等于 B 通过执行之间的操作 0 和 N 次,包含在内,打印 No.
No
如果可以的话,请按以下格式打印一种:
Yes K x_1 y_1 \vdots x_K y_K
在这里, K 是操作次数,并且 x_i, y_i 是整数 x, y 选择于 i第次操作。这些必须满足以下条件:
- 0\leq K\leq N
- 0\leq x_i < y_i \leq 10^{18}
如果有多种方法可以实现目标,您可以打印其中任何一种。
示例输入 1
4 7 2 4 5 3 3 5 0
示例输出 1
Yes 2 3 5 3 6
一个人可以做 A 等于 B 如下。
- 最初, 黑板上写着 A = (7,2,4,5).
- 操作 (x,y) = (3,5) 使 A = (0,0,2,3).
- 操作 (x,y) = (3,6) 使 A = (3,3,5,0).
示例输入 2
1 5 3
示例输出 2
Yes 1 2 4
示例输入 3
2 3 1 3 1
示例输出 3
Yes 0
示例输入 4
2 0 0 1 2
示例输出 4
No