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.need) {
int M = coins / v.need;
count += M;
coins -= (v.need - v.give) * M;
//              cout << v.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;
}
};

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:

### Solution

Problem hints:
• Words can be considered as states. There are at most 26^4 different words composed of 4 letters (thus a linear complexity will run in allowed time).
• There are some ways to pass from one state to another.
• The cost of passing from a state to another is always 1 (i.e. a single button click).
• You need to find the minimum number of steps required to reach the end state from start state.

### Source Code:

//Thu May 19 11:12:55 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;

int dx[] = { 0, 0, 1, -1, 0, 0, 0, 0 };
int dy[] = { 0, 0, 0, 0, 1, -1, 0, 0 };
int dz[] = { 0, 0, 0, 0, 0, 0, 1, -1 };
int dw[] = { 1, -1, 0, 0, 0, 0, 0, 0 };

class State {
public:
int a;
int b;
int c;
int d;
State(string s) {
this->a = s - 'a';
this->b = s - 'a';
this->c = s - 'a';
this->d = s - 'a';
}
State(int aa, int bb, int cc, int dd) {
this->a = aa;
this->b = bb;
this->c = cc;
this->d = dd;
}
bool equals(State s) {
return this->a == s.a && this->b == s.b && this->c == s.c && this->d
== s.d;
}
};

class SmartWordToy {

private:
bool forbiden;
int cost;
public:
int minPresses(string start, string finish, vector<string> forbid) {
init(forbid);
//      if (forbiden[start - 'a'][start - 'a'][start - 'a'][start
//              - 'a'])
//          return -1;
State st(start);
cost[start - 'a'][start - 'a'][start - 'a'][start - 'a']
= 0;
queue<State> q;
q.push(st);
while (!q.empty()) {
int a = q.front().a;
int b = q.front().b;
int c = q.front().c;
int d = q.front().d;
int dist = cost[a][b][c][d];
q.pop();
for (int i = 0; i < 8; i++) {
int x = (a + dx[i] + 26) % 26;
int y = (b + dy[i] + 26) % 26;
int z = (c + dz[i] + 26) % 26;
int w = (d + dw[i] + 26) % 26;
State tmpST(x, y, z, w);
if (forbiden[x][y][z][w] || cost[x][y][z][w] != -1)
continue;
cost[x][y][z][w] = dist + 1;
q.push(tmpST);
}
}
return cost[finish - 'a'][finish - 'a'][finish - 'a'][finish
- 'a'];
}

void init(vector<string> f) {
for (int i = 0; i < 26; i++) {
for (int j = 0; j < 26; j++) {
for (int p = 0; p < 26; p++) {
for (int q = 0; q < 26; q++) {
forbiden[i][j][p][q] = false;
cost[i][j][p][q] = -1;
}
}
}
}
for (int i = 0; i < (int) f.size(); i++) {
vector<string> tmp = split(f[i]);
for (int a = 0; a < (int) tmp.size(); a++) {
for (int b = 0; b < (int) tmp.size(); b++) {
for (int c = 0; c < (int) tmp.size(); c++) {
for (int d = 0; d < (int) tmp.size(); d++) {
forbiden[tmp[a] - 'a'][tmp[b] - 'a'][tmp[c]
- 'a'][tmp[d] - 'a'] = true;

}
}
}
}
}
}

vector<string> split(string s) {
vector<string> ret;
stringstream ss(s);
while (ss >> s) {
ret.push_back(s);
}
return ret;
}
};

### Solution

Same with Div2, Level2.

### Solution

All cuts / C(N,2).

### Source Code:

//SRM233Div2_500;
//SRM233DIV1_250;
//2009/10/23 16:28:28
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class PipeCuts
{
public:
double probability(vector <int> weldLocations, int L)
{
int count = 0;
sort(weldLocations.begin(), weldLocations.end());
for(int i=0; i<weldLocations.size(); i++)
{
for(int j=i+1; j<weldLocations.size(); j++)
if((weldLocations[j]-weldLocations[i]>L) || weldLocations[i]>L || (100-weldLocations[j])>L)
count ++;
}
return 2.0 * count / ((weldLocations.size()-1) * weldLocations.size());
}
};

### Source Code:

//2009/08/15 18:43:18
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <sstream>
#include <algorithm>

using namespace std;

class JustifyText
{
public:
vector <string> format(vector <string> text)
{
int sz = 0;
vector<string> ret;
for(int i=0; i<text.size(); i++) sz = max((int)text[i].size(), sz);
for(int i=0; i<text.size(); i++)
{
string s(sz-text[i].size(), ' ');
ret.push_back(s+text[i]);
}
return ret;
}
};

## Summary: Don't know how to solve level three, also the programming speed is too slow. My rate has been improved, also I am a green man now... Happy. 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 Source Code: Division One - Level Two: Solution Source Code: Division One - Level One: Solution Same to the Div2, Level Two. Source Code: Division Two - Level Three: Solution Source Code: Division Two - Level Two: Solution Sort, find any combination of part of array, the sum would no less than the other part. Just go through each element, then check it. PS: 1st, add the one if they are the same. 2nd, add the one if it's less than the upgraded element. Source Code: //Wed May 11 19:58:39 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 SlimeXSlimesCity { public:     int merge(vector<int> population) {         int N = population.size();         long long sum = 0;         for (int i = 0; i < N; i++) {             v.push_back(make_pair(population[i], i));             sum += population[i];         }         sort(v.begin(), v.end());         int count = 0;         for (int i = 0; i < N; i++) {             int p;             for (p = 0; p < N; p++) {                 if (v[p].second == i)                     break;             }             long long tmp = 0;             for (int k = 0; k < N; k++) {                 if (tmp >= v[k].first || v[k].first <= v[p].first)                     tmp += v[k].first;                 else                     break;             }             if (tmp * 2 >= sum)                 count++;         }         return count;     } private:     vector<pair<int, int> > v; }; Division Two - Level One: Solution Only operations are stay the same or increase some amount of number. Thus, sort the array, then sum all the difference between the maximum and each element. Source Code:

//Wed May 11 19:58:39 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 SlimeXSlimeRancher2 {
public:
int train(vector<int> attributes) {
sort(attributes.begin(), attributes.end());
int sum = 0;
for(int i=0; i<attributes.size(); i++)
sum += attributes[attributes.size()-1] - attributes[i];
return sum;
}
};