Cutting Brownies

• Vicky가 선공이라고 생각하자. (Harry가 선공일때도 똑같다)
• RxC 크기의 초콜렛을 처음에 Vicky가 RxC1 이랑 RxC2 로 나눈다 (C1>=C2). Harry는 RxC2 초콜렛에서만 이길수 있다면, 승리할수 있다. Harry와 Vicky가 서로 번갈아가면서 RxC2 초콜렛을 잘랐을 때 마지막 턴이 Harry에게 돌아가게 되고, Vicky는 결국 다시 RxC1 초콜렛을 잘라야 하는 상황이 된다. 이것은 처음 RxC를 가지고 있을때보다 Vicky에게 불리해진 상태가 되었다.
• 그래서 결국 Vicky는 처음에 초콜렛을 자를때, 두 조각이 모두 Harry가 이길수 없는 상태가 되도록 잘라야 한다. 그러려면 작은쪽을 크게 해야 하므로, C1과 C2가 최대한 비슷해지도록 자르는 것이 최선이다.
• 이것은 Harry도 마찬가지. 최대한 가운데를 자르는 것이 최선이다.
• 그래서 서로 번갈아서 가운데를 자르게 되고, 초콜렛은 R*C ⇒ R*(C/2) ⇒ (R/2)*(C/2) ⇒ (R/2)*(C/4) … 와 같은 식으로 작아지다가, 자기차례에 잘라야하는 가로 또는 세로폭의 길이가 1이라서 더이상 자를 수가 없어지면 지게 된다.
• 시뮬레이션을 돌려도 O(logn)에 풀리기는 하지만, R값과 C값을 보고 각각 몇번까지 자를수 있는지를 바로 계산해서 비교해도 된다. 반씩 줄어들어서 언제 1이 되는지를 보면 되니까 간단하게 2진법으로 썼을때의 길이를 보면 된다.
• 시간복잡도는 O(R+C)

"""Solution code for "BOJ 11090. Cutting Brownies".

- Problem link: https://www.acmicpc.net/problem/11090
- Solution link: http://www.teferi.net/ps/problems/boj/11090

Tags: [game theory]
"""

import sys
from teflib import psutils


@psutils.run_n_times
def main():
    B, D, S = sys.stdin.readline().split()

    h_count, v_count =int(D).bit_length(), int(B).bit_length()
    harry_can_win = h_count > v_count or (h_count == v_count and S == 'Vicky')
    can_win = harry_can_win if S == 'Harry' else not harry_can_win

    print(S, 'can win' if can_win else 'cannot win')


if __name__ == '__main__':
    main()