JOI '16 P3 - Skyscraper

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
JOI Open Contest

The International Olympiad in Informatics will be held in Tsukuba City, Japan. In order to prepare for IOI, we are planning to construct skyscraper buildings in the main street of Tsukuba City. Since we want to create a newsight seeing spot, the buildings have to satisfy the following conditions.

We are planning to construct N buildings along a straight line in the main street. The heights of them are A_1, A_2, A_3,\ldots, A_N. They are different from each other. Since the order of N buildings are not yet decided, we can permute their heights if necessary. We will decorate them for IOI. Due to the constraints of materials used for decoration, the sum of the absolute values of the differences of the heights of two adjacent buildings must be less than or equal to L. In other words, if the heights of the buildings from one side of the main street are f_1, f_2, f_3, \ldots, f_N, we must have |f_1 - f_2| + |f_2 - f_3| + \cdots + |f_{N-1} - f_N| \leq L. Here, |x| is the absolute value of x.

How many permuations of buildings satisfy the above conditions?

Task

Given the number N of buildings, their heights, and the upper limit L of the sum of the absolute values of the differences of the heights of two adjacent buildings, write a program which calculates the number of permutations of buildings satisfying the condition. Since this number can be too big, output the remainder of division of it by 1\,000\,000\,007.

Input Specification

Read the following data from the standard input.

  • The first line contains two space separated integers, N, L. This means the number of buildings is N, and the upper limit of the sum of the absolute values of the differences of the heights of two adjacent buildings is L.
  • The second line contains N space separated integers A_1, A_2, A_3, \ldots, A_N. This means the height of the i-th building (1 \leq i \leq N) is A_i.

Output Specification

The output consists of one line. It contains an integer, the remainder of division of the number of permutations of buildings satisfying the condition by 1\,000\,000\,007.

Constraints

All input data satisfy the following conditions.

  • 1\leq N\leq 100.
  • 1\leq L\leq 1\,000.
  • 1\leq A_i\leq 1\,000.
  • A_i\neq A_j (1\leq i < j\leq N).

Subtasks

Subtask 1 [5 points]
  • N\leq 8.
Subtask 2 [15 points]

The following conditions are satisfied.

  • N\leq 14.
  • L\leq 100.
Subtask 3 [80 points]

There are no additional constraints.

Sample Input 1

4 10
3 6 2 9

Sample Output 1

6

Explanation for Sample Output 1

Ther are 24 permutations in total. Among them, there are 6 permutations for which the sums of the absolute values of the differences of the heights of two adjacent builds are less than or equal to 10.

  • If f_1 = 2, f_2 = 3, f_3 = 6, f_4 = 9, we have |2 - 3| + |3 - 6| + |6 - 9| = 7.
  • If f_1 = 2, f_3 = 3, f_3 = 9, f_4 = 6, we have |2 - 3| + |3 - 9| + |9 - 6| = 10.
  • If f_1 = 3, f_2 = 2, f_3 = 6, f_4 = 9, we have |3 - 2| + |2 - 6| + |6 - 9| = 8.
  • If f_1 = 6, f_2 = 9, f_3 = 3, f_4 = 2, we have |6 - 9| + |9 - 3| + |3 - 2| = 10.
  • If f_1 = 9, f_2 = 6, f_3 = 2, f_4 = 3, we have |9 - 6| + |6 - 2| + |2 - 3| = 8.
  • If f_1 = 9, f_2 = 6, f_3 = 3, f_4 = 2, we have |9 - 6| + |6 - 3| + |3 - 2| = 7.

Sample Input 2

8 35
3 7 1 5 10 2 11 6

Sample Output 2

31384

Comments

There are no comments at the moment.