TCO11 Qualification Round 3

Date: 2011-05-25.

Div 1, Level 1

Div 1, Level 2

Div 1, Level 3

Tutorials:

Division One - Level Three:

Solution

Source Code:

Division One - Level Two:

Solution

Brute-force, but need to sort the elements wisely first.

Source Code:

//Tue May 24 20:07:48 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 <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

class Coins {
public:
    int need;
    int give;
    Coins(int n, int g) {
        this->need = n;
        this->give = g;
    }
    static bool cmp(const Coins &A, const Coins &B) {
        if (abs(A.need - A.give) < abs(B.need - B.give))
            return true;
        else if ((abs(A.need - A.give) == abs(B.need - B.give)) && A.need
                < B.need)
            return true;
        //      if (A.need < B.need)
        //          return true;
        //      if (A.need == B.need && A.give > B.give)
        //          return true;
        return false;
    }
};

class CoinMachinesGame {
public:
    int maxGames(int coins, vector<int> need, vector<int> give) {
        int N = need.size();
        vector<Coins> v;
        for (int i = 0; i < N; i++)
            v.push_back(Coins(need[i], give[i]));
        sort(v.begin(), v.end(), Coins::cmp);
        int count = 0;
        while (coins > 0 && v.size() > 0) {
            if (coins >= v[0].need) {
                int M = coins / v[0].need;
                count += M;
                coins -= (v[0].need - v[0].give) * M;
                //              cout << v[0].need << endl;
            } else
                v.erase(v.begin());
        }
        return count;
    }
};

Division One - Level One:

Solution

Brute-force.

Source Code:

//Tue May 24 20:01:07 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 <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

class AllButOneDivisor {
public:
    int getMinimum(vector<int> divisors) {
        sort(divisors.begin(), divisors.end());
        int K = divisors.size();
        long long product = 1;
        for (int i = 0; i < K; i++)
            product *= divisors[i];
        for (int i = divisors[K - 2]; i<=product; i++) {
            int count = 0;
            for (int j = 0; j < K; j++)
                if (i % divisors[j] == 0)
                    count++;
            if (count == K - 1)
                return i;
        }
        return -1;
    }
};