2018 ACIS REDIS - XXXII Colombian Programming Contest - ACM ICPC 3

B: Forming Better Groups Source file name: better.c, better.cpp, better.java, or better.py Author: Edwin Niño Prof. Smith is tired of the same old end of semester story: lazy students passing his course thanks to group assignments. Unfortunately, group assignments are an important part of the university policies and Prof. Smith cannot get ride of them. However, he has figured out a strategy that can limit the inclusion of lazy students as members of groups with hardworking students. He wants the lazy students to either work or fail his course. The crux of the idea is to define a threshold D so that the following condition limiting how students participate in groups of three members is satisfied: if G1, G2, and G3 are the grades obtained in the previous assignment by three students willing to form a group, then max (G1, G2, G3) − min (G1, G2, G3) ≤ D. Prof. Smith wants students to have many options to form groups and choose their teammates. Therefore, he would like to know in advance the number of ways his students could form groups of three members given threshold D and their grades in the previous assignment, while satisfying the condition above. Please write a program to help Prof. Smith. Input The input has several test cases. The first line of a test case consists of two blank-separated integers N (3 ≤ N ≤ 21) and D (0 ≤ D ≤ 500), representing the number of students and the threshold, respectively. You can assume that N is a multiple of 3. The second line consists of a blank-separated list of grades G1, G2, . . . , GN (0 ≤ Gi ≤ 500, for 1 ≤ i ≤ N) corresponding to the grades of the N students in the previous assignment. The input ends with a line containig two blank-separated zeroes. The input must be read from standard input. Output For each test case, output one line containing one integer: the number of ways the N students can form groups of three members given the threshold D and the grades G1, G2, . . . , GN in their previous assignment when the above-mentioned condition is enforced. The output must be written to standard output. Sample Input 63 163245 68 133365 92 1 2 3 4 5 6 7 8 10 00 Sample Output 2 10 0