Using your Head is Permitted

Now, however, new legislation has come into effect in order to simplify voting in Prepostria. Under the new legislation, in a general election that takes place once every four years, each citizen nominates a delegate that will be representing him, and for the subsequent period of four years until the next general election all votes are taken by the delegates, and each delegate is given as many ballots as the percent of the population that nominated him, rounded down to the nearest percentile.

Not losing the spirit of the old system of government, Prepostria still has no political parties, and delegates are not required to announce themselves in any way in order to join the running for election: any citizen can name any other citizen (or even himself) at general election time.

To support the new legislation, you are asked to write a computer program (or, more specifically, to present an algorithm for a computer program) in order to calculate the number of ballots each citizen receives, in his capacity as a delegate, following a general election. The program receives as input a tape containing all nominations. Each nomination is a single number, being the ID of the citizen who was nominated. (Voting in Prepostria is by a secret ballot, so the nomination contains no indication regarding who nominated whom. Only the nominee is given.) The program can process the tape more than once, but each time the tape is input it must be read sequentially, start to finish.

The reason that Prepostria moved from the old system of government to the new one is that the number of citizens has increased to a point in which the old system was logistically difficult. In order to avoid a recurrence of this problem, your instructions regarding forward-compatible up-scaling capabilities are quite strict:

1. You are only allowed to process the tape the minimal necessary number of times.
2. The tape is a read-only tape.
3. Your program can store whatever variables it wants to store in internal memory, but it must use no more than O(1) cells of memory altogether, throughout its execution. (In the present context, "O(1)" means "a number bounded by a value independent of N".)
4. Each memory cell used is guaranteed only that it can store integers between zero and N.
5. After a preprocessing stage, the program must be able to answer regarding each citizen how many ballots he received in his capacity as a delegate. At query time, the tape with the nominations is no longer available to the program.

Can you devise an algorithm that satisfies the conditions set by the people of Prepostria? To be considered a solver you need to provide an algorithm that performs the ballot count in the minimal possible number of passes on the tape, and to present a proof that no ballot-counting algorithm can work in less passes.

To avoid confusion, we use the term "nominations" to denote the votes given to a delegate by the citizens in a general election, and "ballots" to denote the voting strength of a delegate in the following four years until the next general elections.

Note: The words "he" and "his" are used in the description of the present riddle both for linguistic convenience and because all citizens of Prepostria are male.

List of solvers: