Task 6  Select  
Selecting a Majority Member PROBLEM Students in your school belong to two disjoint groups. It is known that one group, called the majority group, contains more students than the other group. We want to select a student who belongs to the majority group. Student’s identifiers are integers from 1 to the number of students. The only operation that we can perform is to query whether two students belong to the same group. You are to write a program that finds a student who belongs to the majority group, while it performs as few queries as possible. LIBRARY To perform queries, you are given a library query with three operations:
The dialogue between your program and the library procedures is logged in the text file select.out. This log file also contains your answer and an indication whether your answer was correct. Your answer is accepted only if for any two disjoint groups of all students A and B, for which all your queries give the same result, your answer identifies a member of the largest group of A and B. The library forces your program to issue all the queries that are necessary to identify a member of the majority group. That is, there are no predefined test cases but the library produces them "on the fly". If you give an answer before you are 100% certain that the answer is correct, you will get 0 points. So don’t guess! J
Instruction for Pascal programmers: include the import statement
in the source code. Instructions for C/C++ programmers: use the instruction
in the source code, create a project file select.gpr in the task directory, add the files select.c (select.cpp) and query.o into this project, and then compile and/or make your program. EXPERIMENTATION You can experiment with the library by creating a text file select.in. The first and only line must contain the integer N, the number of all students. N must be an odd number! EXAMPLE INPUT AND OUTPUT
For example, the answer 1 would not be accepted because, while all your queries give the same result for the groups {2, 5, 6, 7} and {1, 3, 4} 1 is not member of the majority group {2, 5, 6, 7}. (a..b denotes the set of integers from a to b.) CONSTRAINTS
GRADING If your answer is correct and the number of queries that your program has performed is K then you obtain Max(0, NK) points, where N is the number of students.
