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

Your friends are the type of people who do not like banks. Instead, they lend money to each other. When you or one of your friends needs money, he or she asks around looking for someone who has money which they are willing to lend. Having a bit of a knack for finances, over time you have assumed the position of the financial facilitator, which means you keep track of all the group debts (including your own).

The time has come, however, when you and all your friends must go their separate ways. You have organised a final get-together at the local Chinese restaurant. Everyone is seated around a Lazy Susan (a circular rotating table), as shown below. Your friends are very much creatures of habit and refuse to sit anywhere but their regular seats. To ensure that everyone will be able to settle all their debts easily, you want to make sure that you arrive well prepared.

First, you have calculated every person's total debt, total credit
and net position. Their *total debt* is the sum of all their
debts, i.e., what they owe to friends from whom
they've borrowed money. Their *total credit* is the sum of all
their loans to their friends, i.e., what they have lent to
friends who have borrowed money from them. Each person's *net
position* is equal to their total credit minus their total debt. Thus someone's
net position will be negative if they owe more money than they are
owed in return, and positive if they are owed more than they owe
others.

In light of this information, you have devised a simple and hopefully painless method to get the debts settled as quickly as possible. The process works as follows:

- Someone whose net position is negative will begin by putting precisely enough money onto the Lazy Susan to bring their net position to zero, thus settling all their debts with the group. They will then spin the Lazy Susan to the next person in a clockwise direction.
- If the next person's net position is positive, they will take enough money from the Lazy Susan to bring their net position to zero. If, however, their net position is negative, they will add their amount to the Lazy Susan.
- This process will continue around the table, finishing only when everyone has had their turn.

The outcome of this process, if successful, will be that everyone's net position is reduced to zero and all the debts are settled.

It is, of course, possible to settle everyone's debts exactly, as all the people who owe money or are owed money are present at the dinner. However, there is one important matter which needs to be resolved so that this method will work without a hitch. If the person to start is not chosen wisely, at some point the Lazy Susan may spin to a person whose net position is positive, but there will not yet be enough money on the table to pay them back.

For example, the following diagram represents a possible group of six friends, including yourself, with various net positions.

In this scenario, if you go first, things will not go smoothly:

- You will place $4 onto the table.
- Bertie will take $3 off, leaving $1.
- Boko will add $2, leaving $3.
- Aunt Agatha will add a further $4, leaving $7.
- Jeeves will then want $10 from the table, but there will not be enough on the table!

However, if Madeline goes first, by the time you get around to Jeeves there will be $3 more on the table, which will be exactly the right amount of money and all will go to plan.

Your task is to decide who should go first so as to ensure that at every step there will always be sufficient funds on the table to satisfy each person's debts. You don't have long as the dinner is scheduled for this evening!

The first line of the input file will contain a single integer N, the number of people in your group of friends ( 2 <= N <= 1000000). For convenience, the members of the group are labeled 1,2,...,N clockwise around the table. Of course, you are included in this list as member number 1.

Following this will be N lines of input. The ith of these lines will contain a single integer p_i, representing the net position of the ith group member ( -4000 <= p_i <= 4000).

Your output file should contain a single integer, being the label of the person who should start the process. If there is more than one correct answer, any will be accepted.

6 -4 3 -2 -4 10 -3

6

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

Privacy
statement

© Australian Mathematics Trust 2001-2022

Page generated: 22 May 2022, 11:42am AEST