GCJ 2010 - Snapper Chain

Below is the description of a problem called 'Snapper Chain', from the 'Google Code Jam - 2010':

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 ≤ 108;

Sample Input
------------
4
1 0
1 1
4 0
4 47

Sample Output
-------------
Case #1: OFF
Case #2: ON
Case #3: OFF
Case #4: ON


The description of the problem might be a bit confusing, but if you spend some time and clearly understand about what it really wants, then its really easy to code the solution for that. In my case, I wrote it down on paper and looked at the pattern of the snappers, for different values of n (number of snapper devices)....After looking at the different patterns, it was easy for me to figure out that the number of minimum snaps required to power the end device is equal to "(2 power n) - 1". Ok, this is just the minimum number of snaps! After the minimum number of snaps, it takes 1 snap to totally power off all the snappers...and it again takes "minimum number of snaps', to power the end device. So, after the 'minimum number of snaps', it takes (2 power n) to power the end device. Below is the solution, that I coded in Java:



The solution for this problem can be coded in different ways...In the 'Content Analysis' section of Code Jam site, there is another interesting solution of using XOR operation of bits.

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.