DWITE '09 R7 #5 - Snapper Chain - Olympiads Online Judge

DWITE '09 R7 #5 - Snapper Chain

View as PDF

Submit solution

All submissions

Best submissions

Points: 10

Time limit: 1.0s

Memory limit: 64M

Problem type

DWITE Online Computer Programming Contest, May 2010, Problem 5

This problem is from a Qualification Round of Google Code Jam.

The Snapper is a clever little device that, on one side, plugs its input plug into an output socket, and, on the other side, exposes an output socket for plugging in a light or other device.

When a Snapper is in the ON state and is receiving power from its input plug, then the device connected to its output socket is receiving power as well. When you snap your fingers – making a clicking sound – any Snapper receiving power at the time of the snap toggles between the ON and OFF states.

In hopes of destroying the universe by means of a singularity, I have purchased $N$ $N$ Snapper devices and chained them together by plugging the first one into a power socket, the second one into the first one, and so on. The light is plugged into the $N^{th}$ $N^{t h}$ Snapper.

Initially, all the Snappers are in the OFF state, so only the first one is receiving power from the socket, and the light is off. I snap my fingers once, which toggles the first Snapper into the ON state and gives power to the second one. I snap my fingers again, which toggles both Snappers and then promptly cuts power off from the second one, leaving it in the ON state, but with no power. I snap my fingers the third time, which toggles the first Snapper again and gives power to the second one. Now both Snappers are in the ON state, and if my light is plugged into the second Snapper it will be on.

I keep doing this for hours. Will the light be on or off after I have snapped my fingers $K$ $K$ times? The light is on if and only if it's receiving power from the Snapper it's plugged into.

The input will contain 5 lines, integers $1 \le N \le 30$ $1 \leq N \leq 30$ , and $1 \le K \le 10^8$ $1 \leq K \leq 10^{8}$ , separated by a single space.

The output will contain 5 lines, either ON or OFF for each corresponding case.

Sample Input

Copy

1 0
1 1
4 0
4 47
30 100000000

Sample Output

Copy

OFF
ON
OFF
ON
OFF

Problem Resource: DWITE

Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported

Comments

0

Backer01 commented on July 11, 2022, 10:16 a.m.

Test cases are weak. This (https://dmoj.ca/submission/4688136) solution gets AC, but it's wrong.

9

codingWhale commented on April 21, 2019, 10:45 a.m.

The constraint of K in the problem statement says 1 <= K. In the sample test case, K is 0, though...