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:
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:
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
The score for each input scenario will be 100% if a correct answer is written to the output file, and 0% otherwise.
© Australian Mathematics Trust 2001-2023
Page generated: 24 March 2023, 8:18pm AEDT