Carrot Distribution I

Chris has \(N\) bags labeled from 1 to \(N\) arranged from left to right. Each bag has some carrots in it. The villagers queue up to collect Chris' bags of carrots. Whenever a villager asks for carrots, Chris must give the bag with the lowest label. However, a villager can receive more than one bags; each villager will ask for carrots until he receives at least the same number as the previous villlager. The first villager will receive exactly one bag of carrots.

This file enlist the number of carrots in 1000 bags labelled from 1 to 1000, in that order. What is the maximum number of villagers can Chris satisfy?

Sample Input

1
2
3
4
1 2 3
1 2 1 2
2 2 2 2
2 1 3

Sample Output

1
2
3
4
3
3
4
2

Explanation

For the first input, the first villager takes the first bag, the second villager takes the second and the third villager takes the third bag.

For the second input, the first villager takes the first bag, and the second villager takes​ the second bag. The third villager takes the third bag, but it's not enough (he only got one carrot, while the previous villager got two), so he also takes the fourth bag.


Try the next version.

×

Problem Loading...

Note Loading...

Set Loading...