레이팅 미적용농부 존의 소들은 화상 회의 플랫폼 "mooZ"에서 매일 온라인 모임을 열고 있다. 재미를 위해, 소들은 모임 중에 즐길 간단한 숫자 게임을 만들었다.
엘시는 세 양의 정수 \(A\), \(B\), \(C\) (\(1\le A\le B\le C\))를 가지고 있다. 이 정수들은 비밀이어야 하므로, 엘시는 언니 베시에게 직접 알려 주지 않는다. 대신 베시에게 서로 다른 정수 \(N\)개(\(4\le N\le 7\)) \(x_1,x_2,\ldots,x_N\) (\(1\le x_i\le 10^9\))를 말해 주며, 각 \(x_i\)가 \(A\), \(B\), \(C\), \(A+B\), \(B+C\), \(C+A\), \(A+B+C\) 중 하나라고 주장한다. 하지만 엘시는 거짓말을 하고 있을 수도 있다; 정수 \(x_i\)들이 어떤 유효한 세 쌍 \((A,B,C)\)에도 대응하지 않을 수 있다.
이것은 베시가 이해하기에 너무 어려우므로, 엘시가 제시한 수들과 모순이 없는 세 쌍 \((A,B,C)\)의 개수(0일 수도 있다)를 구하는 것은 여러분의 몫이다.
각 입력 파일에는 독립적으로 해결해야 하는 \(T\)개(\(1\le T\le 100\))의 테스트 케이스가 포함되어 있다.
문제 제공: Benjamin Qi
채점 방식
- 테스트 케이스 1-4에서는 모든 \(x_i\)가 \(50\) 이하이다.
- 테스트 케이스 5-6은 \(N=7\)을 만족한다.
- 테스트 케이스 7-15는 추가 제약이 없다.
문제 제공: Benjamin Qi
입력의 첫째 줄에 \(T\)가 주어진다.
각 테스트 케이스는 엘시가 베시에게 알려 주는 정수의 개수 \(N\)으로 시작한다.
각 테스트 케이스의 둘째 줄에 서로 다른 \(N\)개의 정수 \(x_1,x_2,\ldots,x_N\)이 주어진다.
각 테스트 케이스마다, 엘시가 제시한 수들과 모순이 없는 세 쌍 \((A,B,C)\)의 개수를 출력한다.
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 161
3
5
1
4
3
0
0
0
1For \(x=\{4,5,7,9\}\), the five possible triples are as follows:
$$ (2, 2, 5), (2, 3, 4), (2, 4, 5), (3, 4, 5), (4, 5, 7). $$
riseoj 작성
출처 올림피아드 > USACO > 2020-2021 > US Open > Silver