Programming Fundamentals

You are in charge of planning a route for an electric car across a long road.

Your electric car takes exactly one unit of charge to travel one kilometer. It has infinite battery capacity, but starts off empty

Conveniently, every kilometer along this road, there is a charging station, where you can stop to charge your car. These charging stations may have a limited of supply of charge you can use to charge your car. A charging station may have no charge available

Your job is to determine if it is possible to drive your car to the last charging station on the road, and if so, what the minimum number of stops is to get your car there

Input Format

You should write a C program, going_electric.c

This program will be provided a series of numbers. Each number represents the charge available from a given charging station. The first number given is the charge of the first station (where your car begins its journey). The second number given is the charge at the second station, and so on

Output Format

Your program should print a single integer, the minimum number of charging stops required to cross the road. This should include the initial charging stop

If it is not possible to drive all the way along the road, you should print the integer 0.

Examples

dcc going_electric.c -o going_electric
./going_electric
2 0 0

1

In the above example, the car had to charge at the first station. It then had 2 units of charge, which let it reach the final station. Note that even though that final charging station had no charge to give, the car successfully reached it (just), so this journey is possible.

./going_electric
2 0 0 3 0

0

In the above example, the car could not make it to the last charging station -- the two units of charge at the first station aren't enough to drive to the next charging station with more charge.

./going_electric
1 1 1 1 0

4

In the above example, the car charges at each of the four stations it can. In this way, it just makes it to the final charging station.

./going_electric
3 3 2 1 0

2

In the above example, the car must charge twice, but there are three possible ways it could do so -- it must charge at the first station, but then it could charge at any of the others (excluding the last).

Assumptions/Restrictions/Clarifications