DMPG '15 B5 - Lux-urious S'mores

View as PDF

Submit solution

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

Author:
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

After beating his friends at their card game, Bob decides to make a few s'mores before retiring for the night. Bob loves s'mores, so he decides to build N campfires arranged neatly in a circle to roast his s'mores quickly. Unfortunately, he does not know how efficient each of the fires are, and it is here that he requires your help.

Each campfire x burns with a certain intensity I_x. The variance of a campfire V_x is the larger of the absolute values of the difference in intensity between itself and either of the two adjacent fires, calculated as \max(|I_x - I_{x - 1}|,\ |I_{x + 1} - I_x|).

Little does he know that campfires must fulfill exactly one of two conditions to be able to cook s'mores as efficiently as possible.

  • I_x \ge K — its intensity should be at least K degrees, otherwise the s'mores will not melt fast enough.
  • V_x \le L — its variance should be at most L degrees, since similar fires will cook the s'mores evenly.

Input Specification

The input begins with three space-separated integers on one line N (3 \le N \le 500); K, L (0 \le K, L \le 500), representing the number of campfires Bob absentmindedly built, the minimum recommended intensity, and the maximum recommended variance respectively.

The next N lines will each contain a single integer I_i (1 \le I_i \le 500), denoting the intensity of the i^{th} campfire, in the order in which Bob has arranged them.

Output Specification

Output a single integer, denoting the number of campfires Bob has built that can be used to cook s'mores efficiently.

Sample Input

3 2 1
1
2
1

Sample Output

2

Comments

There are no comments at the moment.