ICPC Live : 4855 (Hyper Box)



// Cpu time : 0.004s
// Memory : minimum 
// Tag : Fibonacci, Gotcha, Elegant

// @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>
#define INT_MAX 2147483647
#define INT_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL unsigned long long
using namespace std;

int ar [50];
int index;

void fibo ()
{
    LL a = 0, b = 1, c = 1;
    index = 0;

    while ( c <= 2000000000 ) {
        ar [index++] = c;
        a = b;
        b = c;
        c = a + b;
    }
}

int numsOfFibo (int n)
{
    int ret = 0;

    for ( int i = index - 1; i >= 0; i-- ) {
        if ( n == 0 ) return ret;
        else if ( ar [i] <= n ) { n -= ar [i]; ret++; }
    }

    return ret;
}

int main ()
{
    fibo ();

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

    while ( testCase-- ) {
        int d;
        scanf ("%d", &d);

        int input;
        LL cnt = 1;

        for ( int i = 0; i < d; i++ ) {
            scanf ("%d", &input);
            cnt *= numsOfFibo (input);
        }

        cout << "Case " << ++cases << ": " << cnt << endl;
    }

	return 0;
}

// @END_OF_SOURCE_CODE
Advertisements

ICPC Live : 4493 (That is Your Queue)



// http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4493
// Cpu Time : 0.033s
// Memory : minimum 
// Algo : Ad-hoc


// @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>
#define INT_MAX 2147483647
#define INT_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL unsigned long long
using namespace std;


int main ()
{
    int p, c;
    int cases = 0;

    while ( scanf ("%d %d", &p, &c) ) {
        if ( p == 0 && c == 0 ) break;

        list <int> l;

        p = min (c, p);

        for ( int i = 1; i <= p; i++ ) l.push_back (i);

        char ch [10];
        printf ("Case %d:\n", ++cases);

        for ( int i = 0; i < c; i++ ) {
            scanf ("%s", ch);
            if ( ch [0] == 'N' ) {
                printf ("%d\n", l.front ());
                l.push_back (l.front ());
                l.pop_front ();
            }
            else {
                int num;
                scanf ("%d", &num);
                l.remove (num);
                l.push_front (num);
            }
        }
    }

	return 0;
}

// @END_OF_SOURCE_CODE

UVa : 4201 (Switch Bulbs)


// http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4201

// CPU Time : 3.182s
// memory : 1388 kbytes

// @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 <bitset>
#include <utility>
#include <set>
#include <math.h>
#define pi acos(-1.0)
#define N 1000000
using namespace std;

map <int, int> visited;
int n, m;

void reset ()
{
    for ( int i = 1; i < (1 << n); i++ ) {
        visited [i] = -1;
    }

    visited [0] = 0;
}

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

    while ( testCase-- ) {
        scanf ("%d %d", &n, &m);

        visited.clear ();
        vector <int> switchs;

        for ( int i = 0; i < m; i++ ) {
            int nums; scanf ("%d", &nums);
            int total = 0;
            for ( int j = 0; j < nums; j++ ) {
                int bulb; scanf ("%d", &bulb);
                total |= (1 << bulb);
            }
            switchs.push_back (total);
        }

        reset ();

        queue <int> q;
        q.push (0);

        while ( !q.empty () ) {
            int p = q.front ();
            q.pop ();

            for ( int j = 0; j < m; j++ ) {
                int ns = p ^ switchs [j];
                if ( visited [ns] == -1 ) {
                    visited [ns] = visited [p] + 1;
                    q.push (ns);
                }
            }
        }

        int query;
        scanf ("%d", &query);

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

        for (int i = 0; i < query; i++ ) {
            char q [30]; scanf ("%s", q);
            long int p = strtol (q, NULL, 2);
            printf ("%d\n", visited [p]);
        }

        printf ("\n");
    }

    return 0;
}

// @END_OF_SOURCE_CODE