CF1546A.AquaMoon and Two Arrays

入门

通过率:0%

时间限制:1.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

AquaMoon and Cirno are playing an interesting game with arrays. Cirno has prepared two arrays aa and bb, both consist of nn non-negative integers. AquaMoon can perform the following operation an arbitrary number of times (possibly zero):

  • She chooses two indices ii and jj (1≤i,j≤n1 \le i, j \le n), then decreases the ii-th element of array aa by 11, and increases the jj-th element of array aa by 11. The resulting values at ii-th and jj-th index of array aa are ai−1a_i - 1 and aj+1a_j + 1, respectively. Each element of array aa must be non-negative after each operation. If i=ji = j this operation doesn't change the array aa.

AquaMoon wants to make some operations to make arrays aa and bb equal. Two arrays aa and bb are considered equal if and only if ai=bia_i = b_i for all 1≤i≤n1 \leq i \leq n.

Help AquaMoon to find a sequence of operations that will solve her problem or find, that it is impossible to make arrays aa and bb equal.

Please note, that you don't have to minimize the number of operations.

AquaMoon 和 Cirno 正在玩一个关于数组的有趣游戏。Cirno 准备了两个数组 aa 和 bb,它们均包含 nn 个非负整数。AquaMoon 可以执行以下操作任意多次(也可以不执行):

  • 她选择两个下标 ii 和 jj(满足 1≤i,j≤n1 \le i, j \le n),然后将数组 aa 的第 ii 个元素减 11,并将数组 aa 的第 jj 个元素加 11。操作后,数组 aa 在第 ii 个和第 jj 个位置上的值分别为 ai−1a_i - 1 和 aj+1a_j + 1。每次操作后,数组 aa 的每个元素都必须保持为非负数。若 i=ji = j,该操作不会改变数组 aa。

AquaMoon 希望通过若干次操作使得数组 aa 和 bb 相等。当且仅当对所有 1≤i≤n1 \leq i \leq n 均有 ai=bia_i = b_i 时,称两个数组 aa 和 bb 相等。

请帮助 AquaMoon 找出一组能实现目标的操作序列;若无法使数组 aa 和 bb 相等,则判定其不可能。

请注意:你无需最小化操作次数。

输入格式

The input consists of multiple test cases. The first line contains a single integer tt (1≤t≤1001 \leq t \leq 100) — the number of test cases.

The first line of each test case contains a single integer nn (1≤n≤1001 \leq n \leq 100).

The second line of each test case contains nn integers a1,a2,…,ana_1, a_2, \dots, a_n (0≤ai≤1000 \leq a_i \leq 100). The sum of all aia_i does not exceed 100100.

The third line of each test case contains nn integers b1,b2,…,bnb_1, b_2, \dots, b_n (0≤bi≤1000 \leq b_i \leq 100). The sum of all bib_i does not exceed 100100.

输入包含多个测试用例。第一行包含一个整数 tt(1≤t≤1001 \leq t \leq 100),表示测试用例的数量。

每个测试用例的第一行包含一个整数 nn(1≤n≤1001 \leq n \leq 100)。

每个测试用例的第二行包含 nn 个整数 a1,a2,…,ana_1, a_2, \dots, a_n(0≤ai≤1000 \leq a_i \leq 100)。所有 aia_i 的总和不超过 100100。

每个测试用例的第三行包含 nn 个整数 b1,b2,…,bnb_1, b_2, \dots, b_n(0≤bi≤1000 \leq b_i \leq 100)。所有 bib_i 的总和不超过 100100。

输出格式

For each test case print "-1" on the only line if it is impossible to make two arrays equal with some sequence of operations.

Otherwise, print an integer mm (0≤m≤1000 \leq m \leq 100) in the first line — the number of operations. Then print mm lines, each line consists of two integers ii and jj — the indices you choose for the operation.

It can be proven that if it is possible to make two arrays equal with some sequence of operations, there exists a sequence with m≤100m \leq 100.

If there are multiple possible solutions, you can print any.

对于每个测试用例,如果无法通过若干次操作使两个数组相等,则在唯一的一行中输出 -1。

否则,在第一行输出一个整数 mm(0≤m≤1000 \leq m \leq 100)—— 表示操作次数。随后输出 mm 行,每行包含两个整数 ii 和 jj —— 表示该次操作所选择的下标。

可以证明:若存在某种操作序列能使两个数组相等,则必存在一个满足 m≤100m \leq 100 的操作序列。

若存在多种可行解,输出任意一种即可。

输入输出样例

  • 输入#1

    4
    4
    1 2 3 4
    3 1 2 4
    2
    1 3
    2 1
    1
    0
    0
    5
    4 3 2 1 0
    0 1 2 3 4

    输出#1

    2
    2 1
    3 1
    -1
    0
    6
    1 4
    1 4
    1 5
    1 5
    2 5
    2 5

说明/提示

In the first example, we do the following operations:

  • i=2i = 2, j=1j = 1: [1,2,3,4]→[2,1,3,4][1, 2, 3, 4] \rightarrow [2, 1, 3, 4];
  • i=3i = 3, j=1j = 1: [2,1,3,4]→[3,1,2,4][2, 1, 3, 4] \rightarrow [3, 1, 2, 4];

In the second example, it's impossible to make two arrays equal.

在第一个例子中,我们执行以下操作:

  • i=2i = 2,j=1j = 1:[1,2,3,4]→[2,1,3,4][1, 2, 3, 4] \rightarrow [2, 1, 3, 4];
  • i=3i = 3,j=1j = 1:[2,1,3,4]→[3,1,2,4][2, 1, 3, 4] \rightarrow [3, 1, 2, 4];

在第二个例子中,无法使两个数组相等。

输入解题思路,AI测评打分。不知道怎么写?

首页