Codeforces Beta Round #59 (Div 2)

Mar 1, 2011.
Accepted: 3.        WA: 0.        NotTried: 2.

Tutorial

Problem 1: Sinking Ship.
AC: This problem is mainly about the sort algorithm, but the comparative function is determined by its character on the ship. Use the trick of data structure in STL. The pair structure will be sorted by the first index, then the second index.
Time: O(n^2), which depends on the sort function.
Source Code:
//Mon Feb 28 21:59:55 CST 2011
int main(int argc, char* argv[]) {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int number;
    while (cin >> number) {
        string a, b;
        vector<pair<int, pair<int, string> > > mp;
        for (int i = 0; i < number; i++) {
            cin >> a >> b;
            if (b == "rat") {
                mp.push_back(make_pair(0, make_pair(i, a)));
            } else if (b == "child" || b == "woman") {
                mp.push_back(make_pair(1, make_pair(i, a)));
            } else if (b == "captain") {
                mp.push_back(make_pair(4, make_pair(i, a)));
            } else {
                mp.push_back(make_pair(3, make_pair(i, a)));
            }
        }
        sort(mp.begin(), mp.end());
        for (int i = 0; i < number; i++) {
            cout << mp[i].second.second << endl;
        }
    }
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}
******************************************************************************************



Problem 2: Settlers' Training
AC: Just simple simulation with this one, I thought there is some mathematical way to solve this problem, but I didn't make it.
Source Code:
//Tue Mar  1 08:28:59 CST 2011
int main(int argc, char* argv[]) {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int k, n;
    while (cin >> n >> k) {
        vector<int> v(n);
        for (int i = 0; i < n; i++)
            cin >> v[i];
            v.push_back(-1);
        bool flag = false;
        int count = 0;
        while (!flag) {
            flag = true;
            for (int i = 0; i < n; i++) {
                if (v[i] != v[i + 1] && v[i] < k) {
                    v[i]++;
                    flag = false;
                }
            }
            if(flag == false)
                count++;
        }
        cout << count << endl;
    }
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}
******************************************************************************************
 
Problem 3:
AC: Enumeration every possible number, then check if it could be the one.
Time: O(10^4 * N).
Source Code:
//Tue Mar  1 10:57:21 CST 2011
bool check(string s1, string s2, int a, int b)
{
    int count1 = 0;
    int count2 = 0;
    for (int i = 0; i < 4; i++)
    {
        for (int j = 0; j < 4; j++)
        {
            if (s1[i] == s2[j])
            {
                if (i == j) count1++;
                else count2++;
            }
        }
    }
    return (count1 == a) && (count2 == b);
}

int main(int argc, char* argv[])
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int n;
    while (cin >> n)
    {
        int count = 0;
        vector<string> s(n);
        vector<int> bulls(n);
        vector<int> cows(n);
        string ss(4, '0');
        for (int i = 0; i < n; i++)
        {
            cin >> s[i] >> bulls[i] >> cows[i];
        }
        for (char i = '0'; i <= '9'; i++)
        {
            for (char j = '0'; j <= '9'; j++)
            {
                if (i == j) continue;
                for (char k = '0'; k <= '9'; k++)
                {
                    if (k == i || k == j) continue;
                    for (char p = '0'; p <= '9'; p++)
                    {
                        if (p == i || p == j || p == k) continue;
                        bool flag = true;
                        for (int q = 0; q < n; q++)
                        {
                            string temp(4, '0');
                            temp[0] = i;
                            temp[1] = j;
                            temp[2] = k;
                            temp[3] = p;
                            if (check(temp, s[q], bulls[q], cows[q]) != true)
                            {
                                flag = false;
                                break;
                            }
                        }
                        if (flag)
                        {
                            count++;
                            ss[0] = i;
                            ss[1] = j;
                            ss[2] = k;
                            ss[3] = p;
                        }
                    }
                }
            }
        }
        if (count == 1)
            cout << ss << endl;
        else if (count == 0)
            cout << "Incorrect data" << endl;
        else
            cout << "Need more data" << endl;
    }
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}

Problem 4:
NT:
Source Code:

Problem 5:
NT:
Source Code: