Markers Tower

View as PDF

Submit solution


Points: 100
Time limit: 0.2s
Memory limit: 256M

Authors:
Problem type

Markers Tower

Problem Statement

After a lengthy 6-minute session of working on math problems on the whiteboard just a few hours before the assignment's due date, Cros and Luke, armed with a collection of n markers of varying lengths, decide to have some fun by stacking two markers into a tower.

Thinking it would be cool to stack multiple towers at the same height, they realize the importance of planning ahead to help them choose the right height for their towers.

Curious, they want to determine the number of possible combinations to select two markers for building a tower of height k.

Input

The first line contains two integers, n and k, where n is the number of markers, and k is the target height of a marker tower made of two markers.

The second line contains n integers a_1, a_2, ... ,a_n, where a_i is the height of the i-th marker.

Output

The output consists of a single integer, the number of possible combinations to select two markers from n markers, such that the height of the tower when stacked on top of each other equals to k.

Constraints

  • 2 \leq n \leq 10^{3}
  • 2 \leq k \leq 10^{5}
  • 1 \leq a_i \leq 10^{5}

Sample Test Cases

Example 1
Input
3 5
2 3 7
Output
1
Explanation

The input contains three markers of height 2, 3 and 7. A visualization of the markers is seen at the left hand side of the illustration below, each marker are numbered below and their corresponding height indicated above.

Untitled

We can show there is 1 way to make a tower with height 5:

  • Stack marker 1 and 2 of height 2 and 3 respectively, which adds up to 5

Note that stacking same 2 markers in a different order (2 and 1) are treated as the same combination.

Example 2
Input
7 6
3 3 3 2 2 4 4
Output
7
Explanation

Untitled

We can show there are 7 ways to stack marker towers of height 6.

Notice that markers with the same height are different from each other, therefore even if two towers have markers with similar lengths, if at least one marker have a different numbering, it will be counted as a two combinations.

Example 3
Input
5 2
100000 99999 1 2 3
Output
0
Explanation

There are no combinations of two markers that makes a tower of height 2.

Python Template

n, k = map(int, input.split())
markers = list(map(int, input.split()))

Comments

There are no comments at the moment.