← 返回题目列表

Codeforces · 1089/C

C. 仙人掌搜索

中文机器翻译题面 查看原题

以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。

Cactus Search - 原题 PDF 第 1 页
原题PDF第3页
Cactus Search - 原题 PDF 第 2 页
原题PDF第4页
可复制的 PDF 提取文本
ICPC 2018 2019, NEERC   Northern Eurasia Finals, Online Mirror
                         St. Petersburg   Barnaul   Tbilisi   Almaty, December 2, 2018
Problem C. Cactus Search



                                                                                          If you want to make an array problem
                                                               harder   solve it on a tree.
                                                                                          If you want to make a tree problem harder
                                                                       solve it on a cactus

                                                                                     Conventional wisdom


NEERC featured a number of problems in previous years about cactuses   connected undirected graphs
in which every edge belongs to at most one simple cycle. Intuitively, a cactus is a generalization of a tree
where some cycles are allowed. An example of a cactus from NEERC 2007 problem is given on the picture
below.

                                            6

                                                    13     12
                                       7          5

                                       8          4
                                                      10   11

                                           3     9    15

                                            2   14

                                        1


You are playing a game on a cactus with Chloe. You are given a cactus. Chloe had secretly picked one
vertex v from the cactus and your goal is to  nd it. You can make at most 10 guesses. If your guess is
vertex v   you win. Otherwise, if your guess is another vertex u   Chloe helps you and tells you some
vertex w which is adjacent to u and such that the distance from w to v is strictly less than the distance
from u to v (here the distance is the number of edges in the shortest path between vertices).

Interaction Protocol

First, the testing system writes a line with two integers n and m (1 ≤n ≤500; 0 ≤m ≤500). Here
n is the number of vertices in the graph. Vertices are numbered from 1 to n. Edges of the graph are
represented by a set of edge-distinct paths, where m is the number of such paths. Each of the following m
lines contains a path in the graph. A path starts with an integer ki (2 ≤ki ≤500) followed by ki integers
from 1 to n. These ki integers represent vertices of a path. Adjacent vertices in a path are distinct. The
path can go to the same vertex multiple times, but every edge is traversed exactly once in the whole
input. The graph in the input is a cactus.

To prove that your program can  nd a secret vertex in at most 10 queries, you need to do that n times.
Each time testing system picks some vertex before interacting with your program. Your program makes
guesses by writing lines with a single number u (1 ≤u ≤n).

Testing system responds by writing lines with one of the two responses:

   •  FOUND    means that your guess is correct. After that, your program should proceed to the next
      test case or terminate if n vertices were already guessed.
   •  GO w    means that your guess is incorrect, but now you know that the distance from vertex w
      to the secret vertex is less than the distance from u. It is guaranteed that vertices u and w are
     connected by an edge.

Do not forget to  ush the output after each guess!




                                         Page 3 of 15

ICPC 2018 2019, NEERC   Northern Eurasia Finals, Online Mirror
                         St. Petersburg   Barnaul   Tbilisi   Almaty, December 2, 2018

Example

      standard input            standard output              Illustration
 5 2
 5 1 2 3 4 5
 2 1 3
                            3
 FOUND
                            3
                                                                  1                   2 GO 4
                            4
 FOUND
                            3
                                                                           3
 GO 2
                            2
 FOUND
                                                                           4
                            3
 GO 1
                            1
 FOUND                                                                    5
                            3
 GO 4
                            4
 GO 5
                            5
 FOUND

Note

Empty lines are added to the standard input and the standard output examples for clarity only. They are
not present during the actual interaction.





                                         Page 4 of 15