Codeforces Beta Round #67(Div 2)

Apr 13, 2011.

Accepted: .        WA: .        NotTried: .

A. Life Without Zeros

B. Facetook Priority Wall

C. Modified GCD

D. Big Maximum Sum

E. Ships Shortest Path

Tutorial

Problem 1:

Solution:

Ad-hoc.

Source Code:

//Wednesday, April  13, 2011 09:48 CDT
#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;

string add(string A, string B) {
    reverse(A.begin(), A.end());
    reverse(B.begin(), B.end());
    string sum = "";
    int flag = 0;
    int i;
    for (i = 0; i < min(A.size(), B.size()); i++) {
        int tmp = (A[i] - '0') + (B[i] - '0') + flag;
        sum += '0' + tmp % 10;
        flag = tmp > 9 ? 1 : 0;
    }
    while (i < A.size()) {
        int tmp = A[i] - '0' + flag;
        sum += '0' + tmp % 10;
        flag = tmp > 9 ? 1 : 0;
        i++;
    }
    while (i < B.size()) {
        int tmp = B[i] - '0' + flag;
        sum += '0' + tmp % 10;
        flag = tmp > 9 ? 1 : 0;
        i++;
    }
    if (flag > 0)
        sum += '0' + flag;
    reverse(sum.begin(), sum.end());
    return sum;
}

string removeZero(string A) {
    string C;
    for (int i = 0; i < A.size(); i++) {
        if (A[i] != '0')
            C += A[i];
    }
    return C;
}

bool check(string A, string B) {
    return removeZero(add(A, B)) == add(removeZero(A), removeZero(B));
}

int main(int argc, char* argv[]) {
    string A, B;
    cin >> A >> B;
    if (check(A, B))
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
    return 0;
}

Problem 2:

Solution:

ad-hoc;

Source Code:

//Wednesday, April  13, 2011 09:48 CDT
#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 Friends {
public:
    string name;
    int priority;
    Friends(string n, int p) {
        name = n;
        priority = p;
    }
    static bool check(const Friends &A, const Friends &B) {
        if (A.priority > B.priority)
            return true;
        else if (A.priority == B.priority && A.name < B.name)
            return true;
        return false;
    }
};
string myname;
map<string, int> ID;
vector<Friends> friends;
int counter;
int n;

void init() {
    cin >> myname;
    cin >> n;
    counter = 0;
    ID.clear();
    friends.clear();
    ID[myname] = counter++;
    friends.push_back(Friends(myname, 0));
}

void stringProcess(string s) {
    string s1, s2;
    stringstream ss(s);
    ss >> s1 >> s2;
    if (s2 == "posted") {
        ss >> s2 >> s2;
        s2 = s2.substr(0, s2.size() - 2);
        if (s1 == myname) {
            if (ID[s2]) {
                friends[ID[s2]].priority += 15;
            } else {
                friends.push_back(Friends(s2, 15));
                ID[s2] = counter++;
            }
        } else if (s2 == myname) {
            if (ID[s1])
                friends[ID[s1]].priority += 15;
            else {
                friends.push_back(Friends(s1, 15));
                ID[s1] = counter++;
            }
        } else {
            if (ID[s1] == 0) {
                friends.push_back(Friends(s1, 0));
                ID[s1] = counter++;
            }
            if (ID[s2] == 0) {
                friends.push_back(Friends(s2, 0));
                ID[s2] = counter++;
            }

        }
    }
    else if (s2 == "commented") {
        ss >> s2 >> s2;
        s2 = s2.substr(0, s2.size() - 2);
        if (s1 == myname) {
            if (ID[s2]) {
                friends[ID[s2]].priority += 10;
            } else {
                friends.push_back(Friends(s2, 10));
                ID[s2] = counter++;
            }
        } else if (s2 == myname) {
            if (ID[s1])
                friends[ID[s1]].priority += 10;
            else {
                friends.push_back(Friends(s1, 10));
                ID[s1] = counter++;
            }
        } else {
            if (ID[s1] == 0) {
                friends.push_back(Friends(s1, 0));
                ID[s1] = counter++;
            }
            if (ID[s2] == 0) {
                friends.push_back(Friends(s2, 0));
                ID[s2] = counter++;
            }

        }
    }
    else if (s2 == "likes") {
        ss >> s2;
        s2 = s2.substr(0, s2.size() - 2);
        if (s1 == myname) {
            if (ID[s2]) {
                friends[ID[s2]].priority += 5;
            } else {
                friends.push_back(Friends(s2, 5));
                ID[s2] = counter++;
            }
        } else if (s2 == myname) {
            if (ID[s1])
                friends[ID[s1]].priority += 5;
            else {
                friends.push_back(Friends(s1, 5));
                ID[s1] = counter++;
            }
        } else {
            if (ID[s1] == 0) {
                friends.push_back(Friends(s1, 0));
                ID[s1] = counter++;
            }
            if (ID[s2] == 0) {
                friends.push_back(Friends(s2, 0));
                ID[s2] = counter++;
            }
        }
    }
}

void solve() {
    getchar();
    for (int i = 0; i < n; i++) {
        string str;
        getline(cin, str);
        stringProcess(str);
    }
    sort(friends.begin(), friends.end(), Friends::check);
    for (int i = 0; i < friends.size(); i++) {
        if (friends[i].name != myname)
            cout << friends[i].name << endl;
    }
}

int main(int argc, char* argv[]) {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    init();
    solve();
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}

Problem 3:

Solution:

For this problem, one needs to store every prime factors of the greatest common divisor, which will save a lot of time.

Source Code:

//Wednesday, April  13, 2011 09:48 CDT
#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 gcd(int a, int b) {
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

int main(int argc, char* argv[]) {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int a, b;
    cin >> a >> b;
    int div = gcd(a, b);
    vector<int> factor;
    for (int i = 1; i * i <= div; i++) {
        if (div % i == 0) {
            factor.push_back(i);
            factor.push_back(div / i);
        }
    }
    sort(factor.begin(), factor.end());
    int n;
    cin >> n;
    while (n--) {
        int low, high;
        cin >> low >> high;
        int ret = -1;
        for (int i = factor.size() - 1; i >= 0; i--) {
            if (factor[i] >= low && factor[i] <= high) {
                ret = factor[i];
                break;
            }
        }
        cout << ret << endl;
    }
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}

Problem 4:

Solution:

This is the advanced classical problem of array's maximum.

First, we need to store the local maximum and the maximum from left, right. Also the total sum of each array.

Then, for each array in the  sequence, we need to use the classic algorithm to check if

1st, the local maximum is the maximum;

2nd, the sum including previous arrays has a greater maximum; If so, we need to update the sum, which is the summation of the previous arrr

Source Code:

//Wednesday, April  13, 2011 09:48 CDT
#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 Array {
public:
    long long total;
    long long left;
    long long right;
    long long mmax;

    Array() {
        this->total = 0;
        this->left = -(1 << 30);
        this->mmax = -(1 << 30);
        this->right = 0;
    }
};

vector<Array> v;
vector<int> sequence;

void init(int m, int n) {
    v.resize(m, Array());
//  cout << "Left, Max, Right, Total" << endl;
    for (int i = 0; i < m; i++) {
        int len;
        cin >> len;
        int sum = 0;
        int mmax = -(1 << 30);
        int number;
        for (int j = 0; j < len; j++) {
            cin >> number;
            sum += number;
            v[i].total += number;
            v[i].left = max(v[i].left, v[i].total);
            v[i].right = min(v[i].right, v[i].total);
            mmax = max(mmax, sum);
            if (sum < 0)
                sum = 0;
            //          else
            //              mmax = max(mmax, sum);
        }
        v[i].mmax = mmax;
        v[i].right = v[i].total - v[i].right;
//      cout << v[i].left << ", " << v[i].mmax << ", " << v[i].right << ", "
//              << v[i].total << endl;
    }
    sequence.resize(n, 0);
    for (int i = 0; i < n; i++) {
        cin >> sequence[i];
        sequence[i]--;
    }
}

long long solve(int m, int n) {
    long long ret = (long long) (-1e18);
    long long sum = 0;
    for (int i = 0; i < n; i++) {
        ret = max(ret, v[sequence[i]].mmax);
        ret = max(ret, sum + v[sequence[i]].left);
        sum = max(sum + v[sequence[i]].total, v[sequence[i]].right);
        if (sum < 0)
            sum = 0;
    }
    return ret;
}

int main(int argc, char* argv[]) {
//  freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int m, n;
    cin >> m >> n;
    init(m, n);
    cout << solve(m, n) << endl;
//  fclose(stdin);
    //fclose(stdout);
    return 0;
}

Problem 5:

Solution:

Source Code: