SRM511

Summary:

The main problem I met is I don't have any experience on game problems. I need more math knowledge and practice more.

	Level 1	Level 2	Level 3
Div 1	Level 1	Level 2	Level 3
Div 2	Level 1	Level 2	Level 3

Tutorials:

Division One - Level Three:

Solution

Source Code:

Division One - Level Two:

Solution

Same to Div2 level 3;

Source Code:

Division One - Level One:

Solution

Same to Div2 level 2;

Source Code:

Division Two - Level Three:

Solution

Source Code:

//Wed Jul  6 15:05:39 CDT 2011
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

class FiveHundredEleven {
public:
    string theWinner(vector <int>);
    int N;
    vector<int> c;
    int visited[512][51];

    int winning(int mem, int played){
        if(mem==511) return 1;
        if(played==N) return 0;
        int &ret = visited[mem][played];
        if(ret != -1) return ret;
        int cnt = 0;
        for(int i=0; i<N; i++)
            if((mem | c[i]) == mem)
                cnt++;
        if(cnt > played && !winning(mem, played+1)) return ret = 1;
        for(int i=0; i<N; i++){
            if((mem | c[i]) != mem && !winning(mem|c[i], played+1))
                return ret = 1;
        }
        return ret = 0;
    }
};

string FiveHundredEleven::theWinner(vector <int> cards) {
    N = cards.size();
    c = cards;
    memset(visited, -1, sizeof(visited));
    if(winning(0, 0)) return "Fox Ciel";
    return "Toastman";
}


//Powered by [KawigiEdit] 2.0!

Division Two - Level Two:

Solution

Source Code:

//Sat Jul  2 20:32:01 CDT 2011
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

class Zoo {
public:
    long long theCount(vector <int>);
    map<int, int> mp;
};

long long Zoo::theCount(vector <int> ans) {
    int N = ans.size();
    sort(ans.begin(), ans.end());
    for(int i=0; i<N; i++){
        mp[ans[i]]++;
        if(mp[ans[i]] > 2) return 0;
    }
    for(int i=0; i<=40; i++){
        if(mp[i] < mp[i+1]) return 0;
    }
    int ones = 0;
    int twos = 0;
    for(int i=0; i<=40; i++){
        if(mp[i]==1) ones++;
        else if(mp[i]==2) twos++;
    }
    long long ret = 1;
    for(int i=0; i<twos; i++) ret *= 2;
    if(ones > 0) ret *= 2;
    return ret;
}

//Powered by [KawigiEdit] 2.0!

Division Two - Level One:

Solution

Source Code:

//Sat Jul  2 16:43:23 CDT 2011
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

class GameOfLifeDivTwo {
public:
    string theSimulation(string, int);
};

string GameOfLifeDivTwo::theSimulation(string init, int T) {
    int N = init.size();
    for(int i=0; i<T; i++){
        string tmp = "";
        for(int j=0; j<N; j++){
            int p = (j-1+N)%N;
            int q = (j+1)%N;
            int sum = (init[p]-'0')+(init[q]-'0')+(init[j]-'0');
            if(sum >=2)
                tmp+="1";
            else
                tmp +="0";
        }
        init = tmp;
    }
    return init;
}


//Powered by [KawigiEdit] 2.0!