Codeforces Round #377 Div. 2 review

Link

• Codeforces Round #377 Div. 2 (Contest 732)

A. Buy a Shovel

• Problem

It can be paid without change if the change is 0 or \(r\).

#include <cstdio>
#include <iostream>

using namespace std;

int main(){
#ifndef ONLINE_JUDGE
    freopen("a3.in", "r", stdin);
#endif
    int k, r;
    scanf("%d %d", &k, &r);

    int i;
    for (i = 1; i < 10; ++i) {
        int change = k * i % 10;
        if (change == 0 || change == r) break;
    }
    printf("%d", i);
    return 0;
}

B. Cormen — The Best Friend Of a Man

• Problem

At day \(i\), dog need to walk \(k−a[i−1]\) times.

/*
 *
 */
#include <cstdio>
#include <iostream>

using namespace std;

int a[505];

int main(){
#ifndef ONLINE_JUDGE
    freopen("b3.in", "r", stdin);
#endif
    int n, k;
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
    }

    int inc = 0;
    for (int i = 1; i < n; ++i) {
        if (a[i-1] + a[i] >= k) continue;
        inc += k - a[i-1] - a[i];
        a[i] = k - a[i-1];
    }
    printf("%d\n", inc);
    for (int i = 0; i < n; ++i) {
        printf("%d%c", a[i], i==n-1 ? '\n' : ' ');
    }

    return 0;
}

C. Sanatorium

• Problem

Basic idea to the solution is not difficult, just check all the popssibility of what time start eating (enter room) and what time end eating (exit room). But the corner case handling makes this problem difficult and I cannot answer correctly in one time.

Rather than below, more elegant/ short code solution can be found at pekempey’s solution.

#include <cstdio>
#include <iostream>

using namespace std;
typedef long long ll;

int main(){
#ifndef ONLINE_JUDGE
    freopen("c4.in", "r", stdin);
#endif
    ll b[3];
    cin >> b[0] >> b[1] >> b[2];

    ll minimum = 3000000000000000000LL;
    for (int i = 0; i < 3; ++i) {// 0: 0,0,0. 1: 0,0,1, 2: 0,1,1
        for (int k = 0; k < i; ++k) { b[2-k]--; }
        for (int j = 0; j < 3; ++j) {// 0: 0,0,0. 1: 1,0,0, 2: 1,1,0
            for (int k = 0; k < j; ++k) { b[k]--; }
            ll missed = 0;
            ll middleDay = max(max(b[0], b[1]), b[2]);
            if (middleDay >= 0) {
                missed += middleDay*3 - (b[0]+b[1]+b[2]);
                minimum = min(minimum, missed);
            }
            for (int k = 0; k < j; ++k) { b[k]++; }
        }
        for (int k = 0; k < i; ++k) { b[2-k]++; }
    }
    if (b[0] == 0 && b[1] == 1 && b[2] == 0) minimum = 0;
    cout << minimum;
    return 0;
}

D. Exams

• Problem

Use binary search. Fix the duration x days, and we can check if it is possible to pass all the tests in x days or not. 

In each check it costs \(O(N)\), so in total it takes \(O(NlogN)\) to find the solution.

/*
 * Binary search
 * O(NlogN)
 *
 * Check if all tests can be passed by n days or not.
 */
#include <cstdio>
#include <iostream>

using namespace std;

int n, m;
int d[100005];
int a[100005];
bool used[100005];

//Check if all tests can be passed by x days or not.
bool C(int x) {
    used[0] = true;
    for (int i = 1; i <= m; ++i) {
        used[i] = false; // init
    }
    int passed = 0;  // #of passed subject
    int day = 0;     // total necessary preparation days
    for (int i = x - 1; i >= 0; --i) {
        if (!used[d[i]]) { // take exam of d[i]
            passed++;
            day += a[d[i]];
            used[d[i]] = true;
        } else {  // study subject of used[d[i]] == true.
            if(day > 0) day--;
        }
    }
    if (passed == m && day == 0) return true;
    else return false;
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("d3.in", "r", stdin);
#endif
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &d[i]);
    }
    for (int i = 1; i <= m; ++i) {
        scanf("%d", &a[i]);
    }
    int lb=0, ub=n;  // can do between (lb, ub]
    while (ub - lb > 1) {
        int middle = (lb+ub)/2;
        if (C(middle)) ub = middle;
        else lb = middle;
        //cout << lb << " " << ub << " " << middle << endl;
    }
    if (ub == n && !C(n)) ub = -1;
    printf("%d\n", ub);

    return 0;
}