codeforces-scrape

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

1970C1.md (1813B)


      1 Source: https://codeforces.com/problemset/problem/1970/C1
      2 
      3 C1. Game on Tree (Easy)
      4 
      5 time limit per test
      6 
      7 1 second
      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 the easy version of the problem. The difference in this version is that $t=1$ and we work on an array-like tree.
     22 
     23 Ron and Hermione are playing a game on a tree of $n$ nodes that are initially inactive. This tree is special because it has exactly two leaves. It can thus be seen as an array. The game consists of $t$ rounds, each of which starts with a stone on exactly one node, which is considered as activated. A move consists of picking an inactive neighbor of the node with a stone on it and moving the stone there (thus activating this neighbor). Ron makes the first move, after which he alternates with Hermione until no valid move is available. The player that cannot make a move loses the round. If both players play optimally, who wins each round of this game?
     24 
     25 Note that all the rounds are played with the same tree; only the starting node changes. Moreover, after each round, all active nodes are considered inactive again.
     26 
     27 Input
     28 
     29 The first line contains integers $n$ ($2 \leq n \leq 2\times 10^5$), $t$ ($t=1$), the number of nodes in the tree and the number of rounds, respectively.
     30 
     31 The next $n-1$ lines contain two integers $1 \leq u, v \leq n$ each, corresponding to an edge of the tree. It is guaranteed that the tree has exactly two leaves.
     32 
     33 The next line contains $t$ integers $1 \leq u_1 , \dots, u_t \leq n$, corresponding to the node where the stone is initially put.
     34 
     35 Output
     36 
     37 The output consists of $t=1$ line which is either "Ron" or "Hermione".
     38 
     39 Examples
     40 
     41 Input
     42 
     43 ```
     44 3 1
     45 
     46 2 3
     47 
     48 3 1
     49 
     50 3
     51 ```
     52 
     53 Output
     54 
     55 ```
     56 Ron
     57 ```
     58 
     59 Input
     60 
     61 ```
     62 5 1
     63 
     64 1 2
     65 
     66 2 3
     67 
     68 3 4
     69 
     70 4 5
     71 
     72 5
     73 ```
     74 
     75 Output
     76 
     77 ```
     78 Hermione
     79 ```