USACO 2008 Jan Bronze 1- 코스튬 파티(Costume Party) > 문제은행 : 정보올림피아드&알고리즘




1385 : 코스튬 파티(Costume Party)

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
25 회   
시도횟수
46 회   

문제

농부 창호는 자신이 기르는 소들을 데리고 미국에 오게 되었다. 

마침 미국의 큰 명절 중 하나인 Halloween day가 있었고 창호는 소들을 데리고 Halloween day를 맞이하여 열리게 된 코스튬 파티에 가게 되었다. 

하지만 미국으로 오는데 돈을 다 써버린 창호는 돈이 없었기 때문에 하나의 의상만을 가지고 있다.

 

의상은 길이가 S(1≤S≤1,000,000)이며 2마리의 소를 동시에 입힐 수 있다. 

창호와 N마리의 소들(2≤N≤20,000 편의상 소들은 1번부터 N번까지의 소로 부르도록 한다)이 있으며 i번째 소의 길이는 Li(1≤Li≤1,000,000)라고 하자.

 

두 마리의 소의 길이를 합쳐서 S를 넘어서지 않을 경우 두 마리의 소가 이 의상을 입을 수 있다.

 

창호는 2마리를 골라서 의상을 입힐 수 있는 조합의 경우가 몇 가지인지 알고 싶어한다.

이를 알아볼 수 있는 프로그램을 작성하라.


입력형식

첫 번째 줄에는 N과 S가 입력이 되며 그 다음 줄부터 N+1개의 줄에는 Li가 순서대로 입력된다.


출력형식

창호가 고를 수 있는 조합의 개수를 출력한다. 고르는 소들의 순서는 고려치 않는다. 다시 말해서 1번 소 2번 소 조합과 2번 소와 1번 소의 조합은 같은 것이다.


입력 예

4 6 
3 
5 
2 
1

출력 예

4

Hint!

다음과 같은 4개의 조합이 가능하다, 1번 소와 3번 소, 1번 소와 4번 소, 2번 소와 4번 소, 3번 소와 4번 소




경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP