Chewing

Zonal Computing Olympiad 2013, 10 Nov 2012
Hobbes has challenged Calvin to display his chewing skills and chew two different types of Chewing Magazine's Diabolic Jawlockers chewing gum at the same time. Being a generous sort of tiger, Hobbes allows Calvin to pick the two types of gum he will chew.
Each type of chewing gum has a hardness quotient, given by a nonnegative integer. If Calvin chews two pieces of gum at the same time, the total hardness quotient is the sum of the individual hardness quotients of the two pieces of gum.
Calvin knows that he cannot chew any gum combination whose hardness quotient is K or more. He is given a list with the hardness quotient of each type of gum in the Diabolic Jawlockers collection. How many different pairs of chewing gum can Calvin choose from so that the total hardness quotient remains strictly below his hardness limit K?
For instance, suppose there are 7 types of chewing gum as
follows:
Chewing gum type  1  2  3  4  5  6  7 
Hardness quotient  10  1  3  1  5  5  0 
If Calvin's hardness limit is 4, there are 4 possible pairs he can choose: type 2 and 7 (1+0 < 4), type 3 and 7 (3+0 < 4), type 2 and 4 (1+1 < 4) and type 4 and 7 (1+0 < 4).
Input format
Line 1 : Two space separated integers N and K, where N is the number of different types of chewing gum and K is Calvin's hardness limit.
Line 2: N space separated nonnegative integers, which are the hardness quotients of each of the N types of chewing gum.
Output format
The output consists of a single nonnegative integer, the number of pairs of chewing gum with total hardness quotient strictly less than K.
Sample Input
7 4 10 1 3 1 5 5 0
Sample Output
4
Test data
In all subtasks, you may assume that all the hardness quotients as well as the hardness limit K are between 0 and 1,000,000, inclusive.
 Subtask 1 (30 marks) : 2 ≤ N ≤ 2,000.
 Subtask 2 (70 marks) : 2 ≤ N ≤ 100,000.
Live evaluation data
 Subtask 1: Testcases 0,1,2,3.
 Subtask 2: Testcases 4,5,6.
Note
The answer might not fit in a variable of type int. We recommend that type long long be used for computing the answer. If you use printf and scanf, you can use %lld for long long.
Author:  admin3 
Date Added:  2112015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, C99 strict, CPP 4.3.2, CPP 4.9.2, CPP14, JAVA, PYTH, PYTH 3.4 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions