Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

First Snow

By prantoran · Limits 1s, 512 MB

One day Tomato woke up late in the morning and realized that she had a long list of todos. Frantically, she wore her overcoat and ran outside with her bag. But, as she got out of the house and ran for the bus stop, she noticed that everything around her is snowy white. She can't figure out the foot path from the road. This is the first time she is seeing snow. ^.^

She forgot everything about her pending tasks and now she wants to make a snowman. She needs at least X amount of snow to make a snowman. Each day, she collects and piles snow fallen on that day. She can collect and store snow. However, the snow piles collected on each day melt away everyday at a fixed rate from each of the piles.

For example, she collected 10 on the 1st day and 20 on the second day, 30 on the 3rd day and the snow melts at rate 10. At the end of the 3rd day, the snow remaining on the 3 piles will be (10 - 210 = -10) = 0, (20 - 110) = 10 and (30 - 0*10) = 30. If a pile becomes <= 0, then it is discarded.

How many days will it require to make a snowman?

Note: You can assume that it's always possible to make the snowman in some day.

Input

First line contains 3 integers N, X and D where N is the number of snowy days, X is the amount of snow required to make a snowman and D is the fixed rate of melting of snow per day. Second line contains N integers Ai where the Ai integer denotes the total snow that was collected on ith day.

Limits:

1 <= N <= 100

1 <= Ai <= 1000

1 <= X <= 1000

0 <= D <= 10

sum(Ai) >= X

Output

A single integers denoting the number of days required to make a snowman.

Samples

InputOutput
1 10 0
10
1

At the end of 1st day, 10 was collected and 10 was required to make a snowman.

InputOutput
3 40 10
10 20 30
3

As described in the problem statement.

InputOutput
9 128 2
3 10 31 27 7 2 65 37 4
8

Discussion

Statistics


70% Solution Ratio

practiceboyEarliest, Apr '20

practiceboyFastest, 0.0s

practiceboyLightest, 0 B

Abdullah_1234Shortest, 167B

Submit

Login to submit

Editorial

For each new day, subtract D from all the previous stacks. Then take the sum of all the positive pil...

Toph uses cookies. By continuing you agree to our Cookie Policy.