USACO 2021 - Open - Silver - Do You Know Your ABCs?

View as PDF

Submit solution

Points: 0.10 (partial)
Time limit: 0.5s
Memory limit: 256M
Input: stdin
Output: stdout

Suggester:
Problem source:
http://www.usaco.org/index.php?page=viewproblem2&cpid=1135
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Những chú bò trong trang trại của bác nông dân John gặp mặt nhau hàng ngày thông qua nền tảng hội họp trực tuyến "mooZ". Chúng đã tạo ra một trò chơi về số cơ bản để chơi trong cuộc gặp mặt với mục đích giải trí.

Elsie có 3 số nguyên dương ~A~, ~B~, và ~C~ ~(1 \le A \le B \le C)~. Những số này được giữ bí mật, nên bạn ấy sẽ không tiết lộ cho em của mình là Bessie. Thay vào đó, Elsie nói cho Bessie ~N~ ~(4 \le N \le 7)~ số nguyên dương phân biệt đôi một ~x_1, x_2, \ldots, x_N~ ~(1 \le x_i \le 10^9)~, đảm bảo rằng mỗi ~x_i~ là một trong các số ~A,~ ~B,~ ~C,~ ~A + B,~ ~B + C,~ ~C + A~ hoặc ~A + B + C~. Tuy nhiên, Elsie cũng có thể nói dối, các số nguyên ~x_i~ có thể không tương ứng với bất kì bộ 3 số nguyên ~(A,~ ~B,~ ~C)~ nào cả.

Bessie không thể giải được bài toán này, vậy nên bạn hãy giúp Bessie tìm số lượng bộ ba ~(A,~ ~B,~ ~C)~ thỏa mãn các số ~x_i~ mà Elsie đã đưa ra.

Input

Dòng thứ nhất chứa số nguyên dương ~T~ là số lượng test.

Mỗi test bắt đầu bằng một dòng chứa số nguyên dương ~N~.

Dòng thứ hai của mỗi test chứa ~N~ số nguyên dương phân biệt đôi một ~x_1, x_2, \ldots, x_N~.

Output

Với mỗi test hãy in ra số bộ ba ~(A,~ ~B,~ ~C)~ thỏa mãn các số mà Elsie đã đưa ra.

Sample Input

10
7
1 2 3 4 5 6 7
4
4 5 7 8
4
4 5 7 9
4
4 5 7 10
4
4 5 7 11
4
4 5 7 12
4
4 5 7 13
4
4 5 7 14
4
4 5 7 15
4
4 5 7 16

Sample Output

1
3
5
1
4
3
0
0
0
1

Giải thích

Tại test 3, với ~x=\{4,5,7,9\}~, có 5 bộ ba thỏa mãn là: ~(2,2,5),(2,3,4),(2,4,5),(3,4,5),(4,5,7)~.

Ràng buộc

  • Các test 1-4 có ~x_i \le 50~.
  • Các test 5-6 có ~N = 7~.
  • Các test 7-15 không có thêm ràng buộc nào.

Comments

Please read the guidelines before commenting.


There are no comments at the moment.