A friends game
All submissions for this problem are available.
Ross and Rachel are playing a game. They have a tree rooted at 1. Each vertex is having some number of stones in it. In one move a player can choose 2 stones from some same node and move it to any of the ancestors of that node in the tree. The player not able to make a move loses. Help them find the winner of the game if they play optimally. Rachel starts first.
First line will contain n (no of nodes in the tree. The next line contains n integers, number of stones in ith node.
Next n-1 lines contain a pair of integers (x,y) denoting an edge between x and y.
Print "Rachel" (without quotes) if Rachel wins the game and "Ross" if Ross wins.
- 1 ≤ n ≤ 105
- 1 ≤ stones[i] ≤ 109
- 1 ≤ x,y ≤ n
Input: 5 10 6 7 19 3 1 2 1 3 1 4 2 5 Output: Rachel
|Tags||easy-medium, game, grundy, npl_nitw, numbers, theory|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions