MLE '19 Contest 3 P1 - PHP

View as PDF

Points: 17
Time limit: 5.0s
Memory limit: 1G

Author:
Problem types

Your friend has a randomly-generated directed graph of nodes. This is a special graph. Each node will have an outdegree of at most one. That is, there will be at most one edge going out from each node. He does not want to tell you the graph, but will allow you to ask questions of the form:

• ? a b Is a descendant of ? That is, is there a path that allows for you to travel from to ? If , then your friend will tell you 1 for "Yes" and 0 for "No". Otherwise, your friend will give you -1 and continue on to the next question.

After questions, your friend will simply stop responding.

Your goal is to surprise your friend by telling him the number of cycles in the graph. A cycle is a path that visits not less than two nodes, uses each edge at most once, and returns to the starting node. For example is a cycle, while is not. Each node can only be used in one cycle.

When you have the answer, surprise your friend by output ! k, where is the number of cycles. Afterwards, your friend will stop responding, and your program must exit.

The algorithm that your friend used to generate the graph is described below:

# N is the number of nodes in the graph
def generate_graph(N):
# for x between 1 and N, inclusive:
for x in range(1, N+1):
# u = random number between 1 and N
u = randint(1, N)
if u != x:
# add a directed edge from x to u
directed_edge_to[x] = u
else:
# outdegree of 0
directed_edge_to[x] = -1


Interaction

The first line will contain the integer .

Afterwards, you must start asking questions.

To ask a question, output ? a b, which asks whether is a descendant of . You will receive a 1 for a "Yes" and 0 for "No". If you receive a -1, that means and were invalid, and your friend will simply continue on to the next question. They will, however, count this as a question.

Once you have the answer (the number of cycles), output ! k, where is the number of cycles. Your friend will stop responding, and you must exit. Note that printing the answer does not count as question.

Note: after each output, you may need to flush your output for your friend to receive it. Please search up how to flush in the language that you are using.
Note 2: your friend may take up to seconds of the time limit.

, where .

Sample Interaction

The given graph is:

The only cycle in this graph is .

>>> denotes your output, and <<< denotes your friend's output.

<<< 4
>>> ? 2 1
<<< 1
>>> ? 4 2
<<< 1
>>> ? 2 4
<<< 1
>>> ? 1 3
<<< 0
>>> ? 3 2
<<< 1
>>> ! 1