← 返回题目列表

Codeforces · 2144/A

A. 剪切阵列

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

给你一个 $$$n$$$ 非负整数数组 $$$[a_1, a_2, \dots, a_n]$$$。

你的任务是将其切成三个非空部分:前缀、中间部分和后缀。形式上,您需要选择两个整数 $$$l$$$ 和 $$$r$$$ 使得 $$$1 \le l \lt r \lt n$$$,并获得三个部分:

  • 索引 $$$l$$$ 处元素的前缀(即 $$$[a_1, a_2, \dots, a_l]$$$);
  • 从索引 $$$l+1$$$ 处的元素到索引 $$$r$$$ 处的元素(包括 $$$[a_{l+1}, a_{l+2}, \dots, a_r]$$$)的中心部分;
  • 从索引 $$$r+1$$$ 到 $$$n$$$ 处的元素的后缀(即 $$$[a_{r+1}, a_{r+2}, \dots, a_n]$$$)。

令 $$$s_1, s_2, s_3$$$ 为这些部分之和模 $$$3$$$ 的余数。换句话说:

  • $$$s_1 = (\sum\limits_{i=1}^{l} a_i) \bmod 3$$$;
  • $$$s_2 = (\sum\limits_{i=l+1}^{r} a_i) \bmod 3$$$;
  • $$$s_3 = (\sum\limits_{i=r+1}^{n} a_i) \bmod 3$$$。

你的任务是找到 $$$l$$$ 和 $$$r$$$ 的边界,使得所有数字 $$$s_1, s_2, s_3$$$ 都不同,或者所有数字 $$$s_1, s_2, s_3$$$ 都相同。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。

每个测试用例由两行组成:

  • 第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 40$$$);
  • 第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 40$$$)。

输出

对于每个测试用例,如果存在一对合适的整数 $$$l$$$ 和 $$$r$$$ ($$$1 \le l \lt r \lt n$$$),则输出这两个整数(如果有多个合适的对,则可以输出其中任何一个)。否则,输出两个等于$$$0$$$的整数。

示例

输入
复制

4
6
1 2 3 4 5 6
4
1 3 3 7
3
2 1 0
5
7 2 6 2 4

输出
复制

3 5
0 0
1 2
2 4

注意

考虑以下声明中的示例:

  • 在第一个示例中,数组被分割为 $$$[1, 2, 3]$$$, $$$[4, 5]$$$, $$$[6]$$$; $$$s_1 = s_2 = s_3 = 0$$$;
  • 在第二个示例中,没有合适的剪切;
  • 在第三个示例中,数组被分成 $$$[2]$$$、$$$[1]$$$、$$$[0]$$$ 部分; $$$s_1 = 2$$$, $$$s_2 = 1$$$, $$$s_3 = 0$$$;
  • 在第四个示例中,数组被分成 $$$[7, 2]$$$, $$$[6, 2]$$$, $$$[4]$$$ 部分; $$$s_1 = 0$$$,$$$s_2 = 2$$$,$$$s_3 = 1$$$。