Google Code Jam: Reverse Words



// http://code.google.com/codejam/contest/351101/dashboard#s=p1
// correct solution for both small and large dataset 


// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#include <ctime>

#define Inf 2147483647
#define Pi acos(-1.0)
#define N 1000000
#define LL long long

const double EPS = 1e-9;
inline bool Equal(double a, double b) { return abs(a-b) < EPS; }
inline LL Power(int b, int p) { LL ret = 1; for ( int i = 1; i <= p; i++ ) ret *= b; return ret; }
const int dr [] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dc [] = {0, 1, 1, 1, 0, -1, -1, -1};

#define F(i, a, b) for( int i = (a); i < (b); i++ )
#define Fs(i, sz) for( size_t i = 0; i < sz.size (); i++ )
#define Fe(i, x) for(typeof (x.begin()) i = x.begin(); i != x.end (); i++)
#define Set(a, s) memset(a, s, sizeof (a))
#define max(a, b)  (a < b ? b : a)
#define min(a, b)  (a > b ? b : a)

using namespace std;


int main ()
{
    freopen ("in.txt", "r", stdin);
    freopen ("out.txt", "w", stdout);

    int testCase; scanf ("%d", &testCase); getchar ();
    int cases = 0;

    while ( testCase-- ) {
        string words [1000 + 10];
        char inp [1000 + 10];

        gets (inp);
        char *pch = strtok (inp, " ");
        int ind = 0;

        while ( pch != NULL ) {
            words [ind++] = pch;
            pch = strtok (NULL, " ");
        }

        printf ("Case #%d:", ++cases);

        for ( int i = ind - 1; i >= 0; i-- ) {
            cout << " " << words [i];
        }

        printf ("\n");
    }

	return 0;
}

// @END_OF_SOURCE_CODE

Google Code Jam: Store Credit



// http://code.google.com/codejam/contest/351101/dashboard#s=p0
// correct solution for both small and large dataset 

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#include <ctime>

#define Inf 2147483647
#define Pi acos(-1.0)
#define N 1000000
#define LL long long

const double EPS = 1e-9;
inline bool Equal(double a, double b) { return abs(a-b) < EPS; }
inline LL Power(int b, int p) { LL ret = 1; for ( int i = 1; i <= p; i++ ) ret *= b; return ret; }
const int dr [] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dc [] = {0, 1, 1, 1, 0, -1, -1, -1};

#define F(i, a, b) for( int i = (a); i < (b); i++ )
#define Fs(i, sz) for( size_t i = 0; i < sz.size (); i++ )
#define Fe(i, x) for(typeof (x.begin()) i = x.begin(); i != x.end (); i++)
#define Set(a, s) memset(a, s, sizeof (a))
#define max(a, b)  (a < b ? b : a)
#define min(a, b)  (a > b ? b : a)

using namespace std;


int main ()
{
    freopen ("in.txt", "r", stdin);
    freopen ("out.txt", "w", stdout);

    int testCase; scanf ("%d", &testCase);
    int cases = 0;

    while ( testCase-- ) {
        int c, i; scanf ("%d %d", &c, &i);
        int p [2000 + 10];
        map <int, int> freq;

        F(j, 0, i) {
            scanf ("%d", &p [j]);
            freq [p [j]]++;
        }

        printf ("Case #%d: ", ++cases);

        F(j, 0, i) {
            freq [p [j]]--;
            if ( freq [c - p [j]] ) {
                printf ("%d ", j + 1);

                F(k, j + 1, i) {
                    if ( p [k] == c - p [j] ) { printf ("%d\n", k + 1); break; }
                }

                break;
            }

            freq [p [j]]++;
        }
    }

	return 0;
}

// @END_OF_SOURCE_CODE

Google Code Jam : Snapper Chain (large)


// @BEGIN_OF_SOURCE_CODE
// large input verdict : Correct!

#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;


int main ()
{
    //freopen ("A-large.in", "r", stdin);
    //freopen ("A-large.out", "w", stdout);
    int T;
    scanf ("%d", &T);
    int cases = 0;

    while ( T-- ) {
        int n;
        int k;
        scanf ("%d %d", &n, &k);

        int power = 1;

        for ( int i = 0; i < n; i++ )
            power *= 2;

        if ( k % power == power - 1 )
            printf ("Case #%d: ON\n", ++cases);
        else
            printf ("Case #%d: OFF\n", ++cases);
    }

    return 0;
}

// @END_OF_SOURCE_CODE

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

Google Code Jam : Alien Numbers


// practice problems, April 12, 2008

// http://code.google.com/codejam/contest/dashboard?c=32003#s=p0

// @BEGIN_OF_SOURCE_CODE

#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 For(i, a) for ( i = 0; i < a; i++ )
#define Rep(i, a, b) for ( i = a; i <= b; i++ )
#define N 1000000
using namespace std;

int returnBase (char *a, char *s)
{
    string baseFormat;
    char *pch;

    for ( int i = 0; a [i]; i++ ) {
        pch = strchr (s, a [i]);
        //printf ("%d\n", pch - s + 1);
        baseFormat += ((pch - s) + '0');
    }

    //cout << baseFormat;

    int output = 0;
    int sLength = strlen (s);
    int baseLength = baseFormat.length () - 1;
    int power = 0;

    while ( baseLength > -1 ) {
        //int p = ceil (pow (sLength, power));
        //int t = (baseFormat.at (baseLength) - '0');
        //output += (p * t);
        output += ((baseFormat.at (baseLength) - '0') * ceil (pow (sLength, power)));
        baseLength--;
        power++;
    }

    return output;
}

void printOutput (char *a, int n)
{
    int length = strlen (a);
    string convertBase;

    while ( n ) {
        convertBase += (( n % length) + '0');
        //cout << convertBase;
        n /= length;
    }

    reverse (convertBase.begin (), convertBase.end ());
    //cout << convertBase;

    for ( unsigned int i = 0; i < convertBase.size (); i++ ) {
        cout << a [convertBase [i] - '0'];
    }

    cout << endl;

}

int main ()
{
    freopen ("A-large.in", "r", stdin);
    freopen ("out-large.out", "w", stdout);
    int n;
    scanf ("%d", &n);
    int cases = 0;

    while ( n-- ) {
        char alienNumber [1000];
        char sourceLanguage [1000];
        char targetLanguage [1000];

        scanf ("%s %s %s", alienNumber, sourceLanguage, targetLanguage);

        printf ("Case #%d: ", ++cases);
        int nthNumber = returnBase (alienNumber, sourceLanguage);
        //printf ("%d\n", nthNumber);
        printOutput (targetLanguage, nthNumber);
    }

    return 0;
}

// @END_OF_SOURCE_CODE

Alien Language


/* Qualification Round 2009
http://code.google.com/codejam/contest/dashboard?c=90101#
Author : Tausiq
*/

#include
#include
using namespace std;

char query [10000];

bool check (char str [])
{
int index = 0;
//unsigned int length = strlen (query);

for ( unsigned int i = 0; i < strlen (str); i++ ) { if ( query [index] == '(' ) { index++; bool flag = false; while ( query [index] != ')' ) { if ( query [index] == str [i] ) flag = true; index++; } if ( !flag ) return false; } else { if ( query [index] != str [i] ) return false; } index++; } return true; } int main () { int l; int d; int n; int testCase = 0; cin >> l >> d >> n;

char str [5002] [18];

for ( int i = 0; i < d; i++ ) cin >> str [i];

while ( n– ) {

cin >> query;

int count = 0;
for ( int i = 0; i < d; i++ ) { if ( check (str [i]) ) count++; } printf ("Case #%d: %d\n", ++testCase, count); } return 0; } [/sourcecode]