Using your Head is Permitted
In the country of Prepostria there are N citizens, each owning a unique ID number between 1 and N. Up until recently, Prepostria was governed by a non-delegatory democracy. That is to say, regarding every matter a full public census was made and each citizen was given one vote on each decision.
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:
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.
http://www.brand.site.co.il/riddles/201101a.html
http://www.matrix67.com/blog/archives/4228
答案：最少需要读取两次磁带。
In the country of Prepostria there are N citizens, each owning a unique ID number between 1 and N. Up until recently, Prepostria was governed by a non-delegatory democracy. That is to say, regarding every matter a full public census was made and each citizen was given one vote on each decision.
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:
- You are only allowed to process the tape the minimal necessary number of times.
- The tape is a read-only tape.
- 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".)
- Each memory cell used is guaranteed only that it can store integers between zero and N.
- 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.
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.
http://www.brand.site.co.il/riddles/201101a.html
http://www.matrix67.com/blog/archives/4228
答案：最少需要读取两次磁带。
首先我们来说明，读取一次磁带是不够的。假设 N 是 100 的某个很大的倍数。磁带前面有 (N/2) + 50 个互不相同的数。磁带后面则又是 50 个不同的数，其中每个数都出现了 (N/100) – 1 次，从而恰好填充满整个磁带。注意，出现了 (N/100) – 1 次就意味着，再多出现一次就能成为代表了。因此正确的输出结果就是，如果这 50 个人中有人正好也在磁带前半部分出现过，则他将获得一票的代表权力。因此，如果程序想要一次读带就完成任务，在读完前 (N/2) + 50 个数之后，它必须要能记住哪些数出现过哪些数没出现过，这显然无法用 O(1) 的空间存下。这就说明，仅用一次磁带是不够的。
如果允许读磁带两次，我们有下面这个算法。
首先，通读一遍磁带，同时维护一个“谁谁谁目前都得到了多少次提名”的表（没有被提名的人就不用写进表里了）。为了保证内存空间在常数级别，我们引入“裁减”操作：只要表里的人数达到 100，就让所有代表都减少一个提名。这样的话，必然有人又会变成“零提名”，从而让表里的人数回到 100 以下。每当表里的人数达到 100 时，我们都进行一次裁减操作，除非我们正好处理完最后一个提名。
现在我们证明，最后没有留在表中的人，都绝不可能成为代表。反证，假设某人得到了 x ≥ N/100 次提名，但最后却没有留在表中。由于一次裁减只能让他失去一个提名，因此读取磁带的过程中至少发生了 x 次裁减。每次裁减都会裁掉 100 个提名，因此整个过程中至少有 100x 个提名被裁掉了。但我们一共就只有 N 个提名，而且最后一个提名是肯定不会被裁掉的，因此 100x 必然严格地小于 N 。这与 x ≥ N/100 矛盾。因此，所有有可能成为代表的人都已经留在表里了。
接下来就容易了。再从头至尾读一遍磁带，并且记录每个代表真正的提名次数。只不过这一次，我们只为上一轮最后还留在表里的那些人做记录。第二轮磁带读完后，我们便能算出每个代表拥有的权力了。
Read full article from Using your Head is Permitted