← 返回题目列表

Codeforces · 1692/F

F. 三数之和

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

给定一个长度为 $$$n$$$ 的正整数数组 $$$a$$$,确定是否存在三个不同的索引 $$$i$$$、$$$j$$$、$$$k$$$ 使得 $$$a_i + a_j + a_k$$$ 以数字 $$$3$$$ 结尾。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \leq n \leq 2 \cdot 10^5$$$) — 数组的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — 数组的元素。

所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

输出 $$$t$$$ 行,每行包含相应测试用例的答案。如果存在满足语句中约束的三个不同索引$$$i$$$、$$$j$$$、$$$k$$$,则输出“YES”,否则输出“NO”。

您可以在任何情况下输出答案(例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定答案)。

示例

输入 #1

6
4
20 22 19 84
4
1 11 1 2022
4
1100 1100 1100 1111
5
12 34 56 78 90
4
1 9 8 4
6
16 38 94 25 18 99

输出 #1

YES
YES
NO
NO
YES
YES

注意

在第一个测试用例中,您可以选择 $$$i=1$$$、$$$j=4$$$、$$$k=3$$$。那么 $$$a_1 + a_4 + a_3 = 20 + 84 + 19 = 123$$$,以数字 $$$3$$$ 结尾。

在第二个测试用例中,您可以选择 $$$i=1$$$、$$$j=2$$$、$$$k=3$$$。那么 $$$a_1 + a_2 + a_3 = 1 + 11 + 1 = 13$$$,以数字 $$$3$$$ 结尾。

在第三个测试用例中,可以证明$$$i$$$、$$$j$$$、$$$k$$$不存在。请注意,$$$i=4$$$、$$$j=4$$$、$$$k=4$$$ 不是有效的解决方案,因为尽管 $$$a_4 + a_4 + a_4 = 1111 + 1111 + 1111 = 3333$$$ 以数字 $$$3$$$ 结尾,但索引需要不同。

在第四个测试用例中,可以证明$$$i$$$、$$$j$$$、$$$k$$$不存在。

在第五个测试用例中,您可以选择$$$i=4$$$、$$$j=3$$$、$$$k=1$$$。那么 $$$a_4 + a_3 + a_1 = 4 + 8 + 1 = 13$$$,以数字 $$$3$$$ 结尾。

在第六个测试用例中,您可以选择$$$i=1$$$、$$$j=2$$$、$$$k=6$$$。那么 $$$a_1 + a_2 + a_6 = 16 + 38 + 99 = 153$$$,以数字 $$$3$$$ 结尾。