ProblemsSubmitRankingsQueue Status

Once upon a time, a king heard rumours that one of his ministers was corrupt. He asked his prime minister for advice on how to identify the culprit. The prime minister suggested that a corrupt minister would probably be wealthier than an honest one. The king immediately instructed his prime minister to identify the wealthiest minister and have him beheaded. Since a corrupt minister would not flaunt his wealth, the prime minister had to send his tax officials to raid the property of each minister to find out his true wealth. However, each tax raid takes a day or two to complete and, due to budget cuts, the prime minister has only enough tax officials at his disposal to raid three ministers' properties at a time. Time was running out and the king was getting impatient. The prime minister hit upon an idea. Whenever the ministers met the king, they sat around a circular table in a fixed order. At the next meeting, if the prime minister could point out a minister at the table who was wealthier than both his neighbours, the king would believe that this was the guilty minister and the prime minister's job would be done. For instance, suppose that the ministers were numbered 1, 2, 3, 4, 5 and 6 and they sat around the table in that order, so the neighbours of 1 were 6 and 2, the neighbours of 2 were 1 and 3, ..., the neighbours of 6 were 5 and 1. Let the net wealth of these six ministers, in lakhs of rupees, be 175, 32, 433, 515, 601 and 62, respectively. Then, minister 1 is a candidate for beheading because his wealth (175) exceeds those of his neighbours, minister 6 (62) and minister 2(32), even though he is not the wealthiest minister overall. Of course, the wealthiest minister, minister 5, is also a candidate for beheading. The problem is to identify any one minister at the circular table who is richer than both his neighbours in the quickest time possible. In general, there will not be enough time to raid every minister's house, even with three simultaneous raids possible. Input and output Your program will not perform any input or output. Instead it will interact with a library identifylib. The library contains three functions:

• int getsize()
  This function should be called first, at the beginning of the program. The value it returns is the number of ministers, an integer N such that 6 ≤ N ≤ 100000.
• void raid(int i, int j, int k, int *vi, int *vj, int *vk)
  This function simulates a simultaneous raid on the properties of ministers i, j and k, 1 ≤ i,j,k ≤ N. The net wealth of minister i is returned via vi, the net wealth of minister j is returned via vj and the net wealth of minister k is returned via vk. It is not necessary that the values i, j and k in the call to raid are all distinct.
  You are only permitted 200 calls to the function raid. If you make more calls, your program will be terminated and an error message "Too many calls to raid" will be printed on the screen.
• void behead(int i)
  When you have identified a minister to sacrifice to the king, you call the function behead with the identity of the guilty minister. This will terminate your program. Note that there may be more than one correct answer. It is sufficient to identify any one minister who meets the criteria.

The library reads the input from a file called identify.in. In this file, the first line is the number N of ministers and the next N lines specify the wealth of ministers 1 to N, in order. The sequence in which the ministers sit around the table is always 1,2,...,N. You may assume that no two ministers have the same amount of wealth. The file that is provided corresponds to the example discussed above. To experiment with your program, create a different file with the same name with data in the same format. After you call behead(), the answer you report will be written in a file identify.out. The first line of identify.out is a single number, the identity of the minister that your program reported to behead. The second line gives the number of calls made to the function raid and the third line tells you if your answer is correct. In addition, every call to raid is recorded in the file identify.log. If you exceed 200 calls, the error message you see on the screen will also be printed to the log file. This file is erased and rewritten each time you run your program. Using the library In your C/C++ file, add the header: #include "identifylib.h" This header file defines the following functions for you to use:

int getsize();
void raid(int, int, int, int *, int *, int *);
void behead(int);

To compile your program, use one of the following:

gcc identify.c identifylib.o -o identify
g++ identify.cpp identifylib.o -o identify

DO NOT OUTPUT ANYTHING TO STDOUT! Constraints on execution Your program should identify a candidate for beheading without making more than 200 calls to the function raid. File name Your program should be in a file named identify.c if you work in C, or identify.cpp if you work in C++.

---

File translated from T_EX by T_TH, version 3.74.
On 25 Jun 2007, 21:18.

CPU Timelimit:	1 seconds
Memory limit:	256M
Grading style:	ioi