## Wednesday, May 25, 2011

### TCO11 Qualification Round 3

Date: 2011-05-25.

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

## Tutorials:

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

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