DMPG '18 B6 - House of Cards

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 64M

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

Mimi is building a house of cards! However, being the strange person that she is, she has N premade layers of cards, with width w_i.

Mimi proceeds to build a house of cards by stacking the layers of cards, one on top of another. However, she realizes that people will become suspicious if the layers are too similar in width, or if the stack grows wider as it gets taller. Thus if layer A is stack on top of layer B, the width of layer A must be at least K less than B.

Given these constraints, what is the tallest house of cards Mimi can make?


Subtask 1 [20%]

1 \le N \le 8
1 \le K \le 10^9
1 \le w_i \le 10^9

Subtask 2 [80%]

1 \le N \le 2\,000
1 \le K \le 10^9
1 \le w_i \le 10^9

Input Specification

The first line will have two space separated integers, N and K.
The next line will have N space separated integers, w_1, w_2, w_3, \ldots, w_N, the widths of the card layers.

Output Specification

A single integer, the number of layers in the tallest house of cards Mimi can make.

Sample Input

5 4
7 2 20 9 12

Sample Output



  • 1
    Ninjaclasher  commented on May 31, 2020, 1:20 p.m.

    The constraints for this problem have been updated to reflect the test data. In particular, K, w_i \le 10^6 has been changed to K, w_i \le 10^9.

  • 1
    echofox  commented on April 25, 2018, 9:37 p.m.

    nice meme