// @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*

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/