무게 합 쌍 세기
실버 II의견: 0
상자 \(N\)개에 각각 정수 무게 \(A_1, \dots, A_N\)이 적혀 있다.
서로 다른 두 상자 \((i, j)\) (\(i < j\))를 고르는데, 두 무게의 합 \(A_i + A_j\)가 \(L\) 이상 \(R\) 이하가 되는 쌍의 개수를 구하여라.
같은 무게가 여러 상자에 있더라도 서로 다른 상자이면 다른 쌍으로 센다.
- \(2 \le N \le 100\,000\)
- \(1 \le A_i \le 10^9\)
- \(2 \le L \le R \le 2 \times 10^9\)
첫 줄에 세 정수 \(N\), \(L\), \(R\)이 주어진다.
둘째 줄에 \(N\)개의 정수 \(A_1, \dots, A_N\)이 공백으로 주어진다.
합이 \([L, R]\) 범위에 드는 쌍의 개수를 출력한다.
5 5 8
1 2 3 4 5
7합이 5 이상 8 이하인 쌍은 \((1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)\)로… 실제로는 무게 기준 \(\{1+4,1+5,2+3,2+4,2+5,3+4,3+5\}\) 등 조건을 만족하는 쌍을 모두 센다. 정답은 출력값과 같다.
3 100 200
1 1 1
0어떤 두 상자를 골라도 합은 2뿐이라 \([100,200]\) 범위에 들지 않는다. 답은 0이다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
무게 합 쌍 세기
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
무게 합 쌍 세기