← 返回题目列表

AtCoder · arc198_c

C. 错误交换

中文机器翻译题面 查看原题

分数: 700 点

问题陈述

给定两个长度的整数序列 N: A=(A_1,A_2,\dots,A_N) 和 B=(B_1,B_2,\dots,B_N).

您最多可以执行 31000 以下类型的操作:

  • 选择一对整数 (i,j) 与 1 \le i < j \le N,然后替换 A_i 与 A_j - 1 和 A_j 与 A_i + 1.

你的目标是 A = B。确定目标是否可以实现,如果可以,则输出实现该目标的一系列操作。

约束

  • 2 \le N \le 100
  • 1 \le A_i,B_i \le 100

输入

输入由标准输入按以下格式给出:

N
A_1\ A_2\ \dots\ A_N
B_1\ B_2\ \dots\ B_N

输出

如果可以的话 A = B,输出 Yes;否则,输出 No.

如果输出 Yes,还输出以下格式的操作序列:

M
i_1\ j_1
i_2\ j_2
\vdots
i_M\ j_M

M 是操作序列的长度,必须满足 0 \le M \le 31000. i_k, j_k 是索引 i, j 选择于 k第一次操作并且必须满足 1 \le i_k < j_k \le N.

如果存在多个解决方案,则其中任何一个都将被接受。


样本输入 1

4
2 2 1 4
3 2 2 2

示例输出 1

Yes
2
1 4
3 4

以下操作使 A = B:

  • 选择 (i,j) = (1,4)。然后 A = (3,2,1,3).
  • 选择 (i,j) = (3,4)。然后 A = (3,2,2,2).

由于不需要最小化操作数,因此也接受以下输出:

Yes
6
1 4
3 4
1 2
1 2
1 2
1 2

示例输入 2

6
5 4 4 3 4 2
5 1 2 3 4 1

示例输出 2

No

示例输入 3

7
2 4 2 4 3 2 5
5 4 3 2 5 1 2

示例输出 3

Yes
18
5 7
1 7
2 4
1 5
1 5
1 4
4 5
4 5
3 4
5 7
1 5
1 7
1 6
6 7
1 7
2 4
2 5
4 5