Wheel Game

It’s yet another rainy day in 1959, there are no video games, and you are stuck indoors playing a game with a friend. The game is played using an even number $2n$ of sticks, laid out on a table to form a wheel with $n$ spokes as shown in the figure below.

You and your friend take turns removing sticks (you always start, since you are you). The rules are simple: each turn, the current player selects one of the remaining sticks. She then removes this stick and all sticks touching the selected stick. This goes on until there are no sticks left, and the player who removed the last stick is declared the winner.

(a) A wheel with $5$ spokes
(b) What remains after the grey stick is selected
Figure 1: A possible initial move in the wheel game

After a while, this gets boring, and you start fantasizing about what the world will be like in the $21$st century: no doubt there will be robots to play stick games with instead of plain old friends. Oh what jolly fun it would be! But what if the robots are super smart? Then you would never be able to win. That wouldn’t be very fun.

Write a program which, given the value of $n$, determines whether you would have any possibility of winning when playing against a robot, or whether you would lose no matter what you do. Assume that the robot is clever enough to always play optimally, and unemotional enough that it would never intentionally lose just to make you feel better.


The input consists of a single integer $n$ between $3$ and $500\, 000$, inclusive. (You may complain that it is impossible to lay out that many sticks to form something resembling a wheel, but recall that this took place in 1959 – the times were different back then.)


Output a single line, containing “The robot is your friend” if it is possible for you to win, or “Destroy the robot before it is too late” if the robot would win no matter how you play.

Sample Input 1 Sample Output 1
Destroy the robot before it is too late
Sample Input 2 Sample Output 2
The robot is your friend
CPU Time limit 1 second
Memory limit 1024 MB
Difficulty 8.7hard
Statistics Show
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in