AIOC Banner

Problem: Nomnomnom

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


Nomnomnom

Input File: nomin.txt
Output File: nomout.txt
Time Limit: 1 second

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:

However, there is never enough food to feed all the hippos. Eventually one of the hippos will find that there is not enough food left for them to be satisfied. Your task is to write a program that reads in a list of dishes and calculates the number of hippos who are satisfied.

Input

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.

Output

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

Sample Input 1

8
5
2
3
1
3
4
2
5

Sample Output 1

3

Explanation

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.

Sample Input 2

6
4
1
2
3
6
6

Sample Output 2

4

Explanation

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.

Scoring

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-2019

Contact: training@orac.amt.edu.au
Page generated: 26 August 2019,  4:56am AEST