Tape
Tag(s):

## Easy-Medium, Greedy algorithm

Problem
Editorial
Analytics

You are a product engineer and would like to improve the quality of duct tapes that your company manufactures. An entire tape can be represented as a single row of N cells. Each cell has its Stickiness factor, which stands for its ability to stick to an object. We say that a tape is a good quality product, if and only if the total sum of Stickiness factors of grid cells in any of its subarray of size K is at least D.

To make a quality product, consider an augment operation in which you can choose any subarray of size at most K and a real number (say R), and multiply Stickiness factor of all its cells by R. For each augment operation, the subarray and the value of R can be chosen arbitrarily. However, the size of chosen subarray for augmentation can be at most K, as mentioned before.

Your task is to calculate the minimum number of augment operations needed to be performed in order to transform the given tape to a good quality product.

INPUT

The first line contains three space separated integers N, K and D, as described above. The next line contains N space separated integers, ith of which (denoted by Ai) denotes the Stickiness factor of ith cell.

OUTPUT

Output in single line, an integer, which denotes the minimum number of augment operations needed to be performed in order to transform the tape to a good quality product. In case, if it is impossible to achieve, print -1 instead.

CONSTRAINTS

1 ≤ N, D ≤ 105
1 ≤ K ≤ N
0 ≤ Ai ≤ 105

SAMPLE INPUT
3 2 4
1 1 1 
SAMPLE OUTPUT
1
Explanation

We can multiply the second element by 3. Now the tape becomes: 1 3 1.

Any subarray of size 2 has now sum = 4, which satisfies the required condition. We used 1 augment operation, hence the answer is 1.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

December Easy '15

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Sorting
• Algorithms > Graphs
• Algorithms > Graphs
• Algorithms > Greedy Algorithms