codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

2258C.md (4490B)


      1 Source: https://codeforces.com/problemset/problem/2258/C
      2 
      3 C. Far Cities
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 This is an interactive problem.
     22 
     23 Seferoglu lives in a small coastal city called Samsun, a city where not many people study competitive programming. Whenever an event takes place, he has to travel to far cities where he can meet his friends. Since he is tired of calculating the length of his journey exactly each time, he is just curious about the maximum distance he will ever have to travel between two cities in the worst case scenario. Your task is to help him find this distance while keeping the amount of web searches he has to make small.
     24 
     25 There is a hidden tree$^{\text{∗}}$ with $n$ vertices. You can make queries. In one query, you choose two vertices $1 \le u, v \le n$ and an integer $0 \le d \le n$; the grader responds with $1$ if $\operatorname{dist}(u, v) \ge d$ and $0$ otherwise. Here, $\operatorname{dist}(u,v)$ denotes the distance$^{\text{†}}$ between vertices $u$ and $v$ in the tree.
     26 
     27 Your task is to determine the diameter's length$^{\text{‡}}$ of the tree and any pair of nodes that are this distance apart. You may ask at most $3 \cdot n$ queries.
     28 
     29 $^{\text{∗}}$A tree is a connected graph without cycles.
     30 
     31 $^{\text{†}}$The distance between two nodes in a tree is the number of edges in the unique simple path between these nodes.
     32 
     33 $^{\text{‡}}$The diameter's length is the largest distance between two vertices.
     34 
     35 Input
     36 
     37 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 500$). The description of the test cases follows.
     38 
     39 The first line of each test case contains $n$ ($2 \le n \le 1000$), denoting the number of vertices in the tree.
     40 
     41 It is guaranteed that the sum of $n$ over all test cases does not exceed $1000$.
     42 
     43 Interaction
     44 
     45 To make a query, first pick $u$, $v$ and $d$ ($1 \le u, v \le n$, $0 \le d \le n$), a pair of nodes and a constant to check the distance between them against, and output the following line (without quotes):
     46 
     47 * "? u v d"
     48 
     49 Afterwards, you should read one single integer ($1$ or $0$), whether $d$ was less than or equal to $\text{dist}(u, v)$ or not.
     50 
     51 Note you may ask at most $3 \cdot n$ such queries.
     52 
     53 Next, if your program has found an answer, it should print the following line (without quotes):
     54 
     55 * "! u v d"
     56 
     57 For some candidate $u$ and $v$ nodes denoting the endpoints of a diameter ($1 \le u, v \le n$) and the length of the path between them ($0 \le d \le n-1$). If there are multiple answers, any one of them may be printed.
     58 
     59 Note that this action is not counted towards the maximum query limit.
     60 
     61 The grader is non-adaptive. This means that the graph is fixed at the beginning and will not change based on your interactions.
     62 
     63 After printing each query do not forget to output the end of line and flush$^{\text{∗}}$ the output. Otherwise, you will get Idleness limit exceeded verdict.
     64 
     65 If, at any interaction step, you read $-1$ instead of valid data, your solution must exit immediately. This means that your solution will receive Wrong answer because of an invalid query or any other mistake. Failing to exit can result in an arbitrary verdict because your solution will continue to read from a closed stream.
     66 
     67 Hacks
     68 
     69 To hack, use the following format:
     70 
     71 The first line contains the number of test cases $t$ ($1 \le t \le 500$).
     72 
     73 The first line of each test case contains $n$ ($2 \le n \le 1000$), denoting the number of vertices in the tree.
     74 
     75 The next $n-1$ lines of each test case contain two integers each $u_i, v_i$ ($1 \le u_i, v_i \le n$), denoting the edges of the tree.
     76 
     77 $^{\text{∗}}$To flush, use:
     78 
     79 * fflush(stdout) or cout.flush() in C++;
     80 * sys.stdout.flush() in Python;
     81 * see the documentation for other languages.
     82 
     83 Example
     84 
     85 Input
     86 
     87 ```
     88 3
     89 
     90 4
     91 
     92 1
     93 
     94 0
     95 
     96 0
     97 
     98 0
     99 
    100 2
    101 
    102 4
    103 
    104 1
    105 
    106 1
    107 
    108 1
    109 
    110 1
    111 
    112 0
    113 
    114 0
    115 
    116 0
    117 
    118 0
    119 ```
    120 
    121 Output
    122 
    123 ```
    124 ? 1 2 1
    125 
    126 ? 1 2 2
    127 
    128 ? 2 3 2
    129 
    130 ? 3 4 2
    131 
    132 ! 1 4 3
    133 
    134 ! 1 2 1
    135 
    136 ? 1 2 1
    137 
    138 ? 1 3 1
    139 
    140 ? 1 4 1
    141 
    142 ? 3 4 2
    143 
    144 ? 3 4 3
    145 
    146 ? 1 2 2
    147 
    148 ? 1 3 2
    149 
    150 ? 1 4 2
    151 
    152 ! 4 2 2
    153 ```
    154 
    155 Note
    156 
    157 The hidden graph in the first test case is $(1,2), (2,3), (3,4)$.
    158 
    159 The hidden graph in the second test case is $(1,2)$.
    160 
    161 The hidden graph in the third test case is $(1,2), (1,3), (1,4)$.
    162 
    163 In the third test case, the answer "! 3 4 2" is also correct.
    164 
    165 |  |  |  |  |
    166 | --- | --- | --- | --- |
    167 |  |  |  |  |
    168 | The tree of the first testcase | The tree of the second testcase | The tree of the third testcase |