코스튬 파티 #6159

문제

한 농부가 할로윈 파티에 그의 소들을 데려가려고한다. 아쉽게도 농부에게는 코스튬이 한벌밖에 없다. 그 코스튬에는 정확하게 사이즈는 S(1 <= S <= 1,000,000)이며, 최대 소 두마리가 들어간다. 농부는 N(2 <= N <= 20,000)마리의 소가 있으며(소의 이름은 편의상 소1.. 소N으로한다), 소i의 사이즈는 (1 <= L_i <= 1,000,000)이다. 만약 소 두마리의 크기 합이 코스튬의 크기 이하인 경우 둘이 코스튬에 들어갈 수 있다. 농부가 코스튬에 얼마나 많은 서로 다른 소의 짝이 들어가는지 구할수있도록 도와주자.

입력

첫째 줄에는 정수 N(소의 수)과 S(코스튬의 크기)가 주어진다.

둘째 줄부터는 각 줄에 소들의 크기가 주어진다.

출력

첫째 줄에 얼마나 많은 짝이 가능한지 출력한다.

예제 입력 1 복사

4 6
3
5
2
1

예제 출력 1 복사

4

힌트

위의 문제에서 4개의 짝은 아래와 같다.

• 소1-소3 (사이즈 합:5)
• 소1-소4 (사이즈 합:4)
• 소2-소4 (사이즈 합:6)
• 소3-소4 (사이즈 합:3)

출처

Olympiad > USA Computing Olympiad > 2007-2008 Season > USACO January 2008 Contest > Bronze 1번

• 문제를 번역한 사람: josephwon0310
• 잘못된 번역을 찾은 사람: jwvg0425

알고리즘 분류

• 브루트포스 알고리즘
• 정렬
• 두 포인터

---

# https://www.acmicpc.net/problem/6159

'''
1. 아이디어 :
    1) 이중 포문을 돌면서 모든 경우의 수를 구한다
    2) 두 포인터로 lp=0, rp=n-1로 지정하고, while문안에 lp와 rp가 같아질때까지, [lp]+[rp]가 target보다 작거나 같아질때까지 반복한 후, lp와 rp 사이의 숫자들 +1을 ans에 더해준다.
2. 시간복잡도 :
    1) O(n^2)
    - 이중 포문
    2) O(logn) * O(n) = O(nlogn)
    - 정렬 + while문
3. 자료구조 :
    1) 배열
    2) 배열
'''

import sys

input = sys.stdin.readline
n, target = map(int, input().split())
cows = sorted([int(input()) for _ in range(n)])
ans = 0
lp = 0
rp = n - 1
while 1:
    if lp==rp:
        break
    if cows[lp] + cows[rp] > target:
        rp -= 1
    elif cows[lp] + cows[rp] <= target:
        ans += rp - lp
        lp += 1
print(ans)
#===============================================================================
input = sys.stdin.readline
n, target = map(int, input().split())
cows = [int(input()) for _ in range(n)]
ans = 0
for i in range(n-1):
    for j in range(i+1, n):
        if cows[i]+cows[j] <= target:
            ans+=1
        else:
            break
print(ans)