// @BEGIN_OF_SOURCE_CODE
// Small input verdict : Correct!
// *** Do not Copy the code *** //
// *** Valid, Only for Learning purpose *** //
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <sstream>
#include <set>
#include <math.h>
#define N 1000000
using namespace std;
struct snapper {
bool power;
bool on;
} a [10 + 2];
void reset (int n)
{
for ( int i = 0; i < n; i++ ) {
a [i].power = false;
a [i].on = false;
}
a [0].power = true;
}
int main ()
{
//freopen ("A-small-attempt1.in", "r", stdin);
//freopen ("A-small-attempt1.out", "w", stdout);
int T;
scanf ("%d", &T);
int cases = 0;
while ( T-- ) {
int n;
int k;
scanf ("%d %d", &n, &k);
reset (n);
for ( int i = 0; i < k; i++ ) {
for ( int j = 0; j < n; j++ ) {
if ( a [j].power )
a [j].on = a [j].on ? false : true;
}
for ( int j = 0; j < n; j++ ) {
if ( a [j].power && a [j].on )
a [j + 1].power = true;
else
a [j + 1].power = false;
}
}
if ( a [n - 1].power && a [n - 1].on )
printf ("Case #%d: ON\n", ++cases);
else
printf ("Case #%d: OFF\n", ++cases);
}
return 0;
}
// @END_OF_SOURCE_CODE

### Like this:

Like Loading...

*Related*

## Published by Shahab

Completed B.Sc in CSE, @United International University, Dhaka.
Currently working as Development Engineer, Android and iOS Application.
View all posts by Shahab

please give this one in java language…

and also of fair problem in java only

you should keep this entry until the qualification round ends.

@raj,

i don’t think, there is an extra benefit if i used java. My logic will be same, irrespective any language. rather if u asked for algorithm, i could have tried.

@yama,

i am not going to post any further entry regarding code jam until qualification rounds ends, even if i can solve. this is just a sample code for educational purpose. Thanks for your concern.

This algorithm is NOT applicable for Large input. Surely u’ll get TLE.

But u can use this code for some sample inputs. analyze output and try to figure out the internal logic.

For example,

when N = 1,

following values of K, will give output ON.

1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29 …

when N = 2,

ON for K = 3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47 …

when N = 3,

ON for K = 7, 15, 23, 31, 39, 47, 55, 63, 71, 79, 87 …

actually i had made program using java…n ur logic exacly matches mine

but on submitting it is marked incorrect from code jam..though mine is working on small inputs…and i am unable to find the mistake since morning

and for ur last or loop j<n-1 will be there instead of j<n

@raj,

try these cases, hope it’ll help.

and yes, at line 57 :

it should be j < n – 1

7 127

8 255

9 511

these r invalid inputs for small data set. sorry 🙂

This is a very inefficient method of solving the problem. You should have noticed the pattern that to turn the light with N snappers, you need to clap (2^N – 1) times.

Now, to determine whether or not the light will be on after K claps, just evaluate (((K + 1) % (2^N)) == 0). If that statement is true, the light will be on with N snappers and after K claps. My solution solved the large data set in literally less than a second.

my code for large input set :

https://tausiq.wordpress.com/2010/05/09/google-code-jam-snapper-chain-large-3/