Carrot Distribution II

Computer Science Level pending

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?

Sample Input

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

Sample Output

1
2
3
4
3
3
4
3

Explanation

  • 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.

×

Problem Loading...

Note Loading...

Set Loading...