SRM181

Div 1, Level 1

Div 1, Level 2

Div 1, Level 3

Div 2, Level 1

Div 2, Level 2

Div 2, Level 3

Tutorials:

Division One - Level Three:

Solution

Using priority queue in the library, but I have to redefine the < operator, since the priority queue in the library is implemented with max-heap. I use 1 << 15 to identify if the weapon is taken, or which means that boss has been killed.

Source Code:

//Sun Jun 12 16:13:59 CDT 2011
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#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 State{
public:
    int weapons;
    int shots;
    bool operator < (const State &A) const {
        return this->shots > A.shots;
    }
};

class KiloManX {
public:
    int leastShots(vector <string>, vector <int>);
    bool visited[1<<15];
    int N;
};

int KiloManX::leastShots(vector <string> damageChart, vector <int> bossHealth) {
    memset(visited, false, sizeof(visited));
    N = damageChart.size();
    priority_queue<State> q;
    State state = {0, 0};
    q.push(state);
    while(!q.empty()){
        State s = q.top();
        q.pop();
      
        if(visited[s.weapons]) continue;
        visited[s.weapons] = true;
      
        if(s.weapons == (1<<damageChart.size())-1) return s.shots;
      
        for(int i=0; i<damageChart.size(); i++){
            if((s.weapons>>i) & 1) continue;
            int best = bossHealth[i];
            for(int j=0; j<damageChart.size(); j++){
                if(i==j) continue;
                if(((s.weapons>>j) & 1) && damageChart[j][i]!='0'){
                    int shotNeeded = (bossHealth[i] + damageChart[j][i] - '1') / (damageChart[j][i] - '0');
                    best = min(best, shotNeeded);
                }
            }
            State tmp = {s.weapons | (1<<i), s.shots + best};
            q.push(tmp);
        }
    }
    return -1;
}

//Powered by [KawigiEdit] 2.0!

Division One - Level Two:

Solution

Source Code:

Division One - Level One:

Solution

Same with Div2, Lvl 2.

Source Code:

Division Two - Level Three:

Solution

Source Code:

Division Two - Level Two:

Solution

Source Code:

//2009/09/08 23:21:02
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <sstream>
#include <algorithm>

using namespace std;

class CombinationLock
{
public:
    double degreesTurned(vector <int> combo, int size, int start)
    {
        int N = combo.size(), L = N;
        double ret = 0;
        int at = start;
        int dir = 1;       //we're calling 1 counterclockwise and 1 clockwise
        for (int i = 0; i < L; i++, N--)
        {
            int K;
            if (dir == 1) K = combo[i] - at;
            else K = at - combo[i];
            if (K < 0) K += size;
            ret += 360.0 * (N + 1.0*K/size);
            at = combo[i];
            dir = -dir;
        }
        return ret;

    }
};

Division Two - Level One:

Solution

Source Code:

//2009/08/10 12:54:07
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>

using namespace std;

class KiloMan
{
public:
    int hitsTaken(vector <int> pattern, string jumps)
    {
        int score = 0;
        for(int i=0; i<pattern.size(); i++)
        {
            if(jumps[i] == 'J' && pattern[i] > 2)
                score++;
            if(jumps[i] == 'S' && pattern[i] <= 2)
                score ++;
        }
        return score;
    }
};