GCJ2010  Snapper Chain
Problem
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 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 Nth 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 times? The light is on if and only if it's receiving power from the Snapper it's plugged into.
Input
The first line of the input gives the number of test cases, T. T lines follow. Each one contains two integers, N and K.
Output
For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is either "ON" or "OFF", indicating the state of the light bulb.
Limits
1 ≤ T ≤ 10,000.
Small dataset
1 ≤ N ≤ 10;
0 ≤ K ≤ 100;
Large dataset
1 ≤ N ≤ 30;
0 ≤ K ≤ 10^{8};
Sample
4
1 0
1 1
4 0
4 47
Output:
Case #1: OFF
Case #2: ON
Case #3: OFF
Case #4: ON
hide comments
nadstratosfer:
20180527 16:32:57
Challenge version would be nice. Got AC with 109 bytes in Py2, best golfers would likely do it under 60. 

praveen:
20100915 18:10:09
can i get more test cases.. if anyone has solved this problem pls give some more testcases 

Nithin.A.G:
20100907 21:09:34
got through gcj 2010 cos of this prob :) 

Peutri:
20100903 21:46:22
My passing entry during GCJ was about 3.5kB. I could squeeze it down to 685, but it seems unlikely I'll make it to 500.


:(){ :: & };::
20100526 06:20:47

Added by:  Kumar Anurag 
Date:  20100514 
Time limit:  0.414s 
Source limit:  500B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS OBJC PERL6 SQLITE VB.NET 
Resource:  Google Code Jam 2010 Qualifying round 