TLE '17 Contest 2 P5 - Crew Selection Test

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 13.0s
Memory limit: 256M

Problem types

Fax and the Great Fax.

Fax McClad, Croneria's most independent bounty hunter, has decided to form a crew of P people to operate his spacecraft carrier, the Great Fax.

The people that Fax can choose from are numbered from 1 to N. 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 x (1 \le x \le N) to categorize all of the people that they know and don't know. Because Fax is lazy, he will do this at most Q times.
  • C a b ...: Create a crew containing people with distinct numbers a,b,\dots. There should be P people in this crew.
  • C -1: Give up because there is no way to create a crew.


15N = 3P = 2Q = 1
210N = 9P = 3Q = 5
310N = 81P = 5Q = 80
450N = 19\,683P = 8Q = 24
525N = 59\,049P = 10Q = 18

Important Note: Up to 8 seconds of the time limit could be used up by the generator.

Input Specification

The first line of input will contain three integers N, P, and Q.

Output Specification

To answer this problem, print C a b .... The P people in the crew will be numbered a,b,\dots. 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 1 \le x \le N. After printing A x and flushing (see Note 1), a string of length N will appear as input. This string consists of 1's and 0's. If the i^{th} character is 1, then person x and person i know each other. If the i^{th} character is 0, then person x and person i don't know each other. The x^{th} character is guaranteed to be a 1.

You must not make more than Q queries (see Constraints for the exact number).

After your program is done making queries, your program can print an answer. If there are P distinct people, numbered a,b,\dots, 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.

Sample Interaction

>>> denotes your output; don't actually print this out.

9 3 5
>>> A 1
>>> A 2
>>> C 1 2 3

All pairs of people in the crew don't know each other. In total, 2 queries are used.


There are no comments at the moment.