Google Code Jam : Snapper Chain (small)


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

10 thoughts on “Google Code Jam : Snapper Chain (small)

  1. @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.

  2. 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 …

  3. 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

  4. @raj,
    try these cases, hope it’ll help.

    Input : 
    9
    1 1
    2 3
    3 7
    4 15
    5 31
    6 63
    7 127
    8 255
    9 511
    
    Output : 
    Case #1: ON
    Case #2: ON
    Case #3: ON
    Case #4: ON
    Case #5: ON
    Case #6: ON
    Case #7: ON
    Case #8: ON
    Case #9: ON
    

    and yes, at line 57 :
    it should be j < n – 1

  5. 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s