TLE '17 Contest 2 P5 - Crew Selection TestView as PDF
Fax McClad, Croneria's most independent bounty hunter, has decided to form a crew of people to operate his spacecraft carrier, the Great Fax.
The people that Fax can choose from are numbered from to . Among all pairs of people, they either know each other or don't know each other.
Fax wants the crew to be able to work together flawlessly, so the crew should follow one of these two conditions:
- Among all pairs of people in the crew, they know each other.
- Among all pairs of people in the crew, they don't know each other.
This is because people tend to prefer to work with people they know than those they don't know. Fax wants to ensure that each person will want to work with others equally.
In order to accomplish this, Fax can perform the following three actions:
A x: Ask person to categorize all of the people that they know and don't know. Because Fax is lazy, he will do this at most times.
C a b ...: Create a crew containing people with distinct numbers . There should be people in this crew.
C -1: Give up because there is no way to create a crew.
Important Note: Up to 8 seconds of the time limit could be used up by the generator.
The first line of input will contain three integers , , and .
To answer this problem, print
C a b .... The people in the crew will be numbered . If there is no solution, print
C -1. Afterwards, your program must terminate.
This is an interactive problem. After reading the first line of input, your program can make queries.
A query is in the form
A x, where . After printing
A x and flushing (see Note 1), a string of length will appear as input. This string consists of
0's. If the character is
1, then person and person know each other. If the character is
0, then person and person don't know each other. The character is guaranteed to be a
You must not make more than queries (see Constraints for the exact number).
After your program is done making queries, your program can print an answer. If there are distinct people, numbered , who satisfy the conditions, then your program is allowed to print
C a b ... as the answer. If there is no solution, print
C -1 instead. Afterwards, make sure you flush and terminate your program.
Note 1: To flush, you can use
fflush(stdout); in C++, or
System.out.flush(); in Java, or
import sys; sys.stdout.flush() in Python 2/3. For other languages, search in its documentation.
Note 2: An answer does not count as a query.
>>> denotes your output; don't actually print this out.
9 3 5 >>> A 1 100100100 >>> A 2 010010010 >>> C 1 2 3
All pairs of people in the crew don't know each other. In total, queries are used.
Report an issue