Want to try solving this problem? You can submit your code online if you log in or register.

The hippopotami of North Yorkshire are busy creatures indeed. They wake at dawn for some light aerobics, followed by a quick galumph to the shops where they scare the tourists, dance ballet and wallow contentedly in the area's famous natural mud pits. Of course, all of this is quite strenuous work and by the end of the day they are hungry, hungry hippos.

At dinner time these majestic native animals begin their trek back home. Each evening, the respectful locals place dishes of food along the main road. Different dishes weigh different amounts: for example, a plate of cabbage might weigh just one kilogram, a pot of fish soup might weigh ten, while a colossal wedding cake may weigh upwards of nine thousand.

The hippos are not very good with knives and forks, so they must eat these food dishes whole. This makes it difficult for them to share their food evenly. Instead, they have devised the following system:

- When the hippos reach the first dish on the road, the eldest
hippo will eat it and be satisfied;
- The next-eldest hippo will eat every dish he passes until he has
eaten at least as much as the previous hippo, at which point he is
satisfied;
- This pattern continues, with each hippo in turn eating everything
they pass until they have eaten at least as much as the hippo before
them, at which point they are satisfied.

The first line of the input file will contain a single integer, N, the number of dishes on the road ( 1 <= N <= 100000). The following N lines describe the dishes in the order the hippos pass them. Each of these lines contain a single integer representing the weight of the corresponding dish. All weights will be between 1 and 1000, inclusive.

The output file should consist of a single line containing a single integer: the number of hippos who are satisfied.

8 5 2 3 1 3 4 2 5

3

This example consists of eight dishes. The first hippo eats the first dish, with total weight 5 kg. The second hippo eats the next two dishes, with total weight 2 + 3 = 5 kg. As this is as much as the previous hippo, he stops. The third hippo eats the next three dishes, with total weight 1 + 3 + 4 = 8 kg. As this is more than the previous hippo, she stops. (Note that she could not have just eaten 1 + 3 = 4 kg of food, as this would be less than the previous hippo). The final two dishes total 2 + 5 = 7 kg, so none of the remaining hippos can eat enough to be satisfied. Only three hippos are satisfied.

6 4 1 2 3 6 6

4

This example consists of six dishes. The first hippo eats the first dish, with total weight 4 kg. The second hippo eats the next three dishes, with total weight 1 + 2 + 3 = 6 kg. The third and fourth hippo each eat one dish weighing 6 kg. At this point, all the dishes have been eaten, so none of the remaining hippos can eat enough. Only four hippos are satisfied.

The score for each input scenario will be 100% if the correct answer is written to the output file, and 0% otherwise.

Privacy
statement

© Australian Mathematics Trust 2001-2021

Page generated: 1 December 2021, 11:21am AEDT