Carrot Distribution II
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 smallest labeled bag. The only condition is that a villager must receive at least as many carrots as the previous villager. But this doesn't mean Chris must stop after giving enough carrots; Chris may give more carrots than necessary.
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?
1 2 3 4
1 2 3 4
- For the first input, the distribution is (1) (2) (3).
- For the second input, the distribution is (1) (2) (1,2).
- For the third input, the distribution is (2) (2) (2) (2).
- For the last input, the distribution is (2,1) (3) (3).
Here is an easier version of this problem.