Soluzioni OII territoriali 2019

download.cpp

#include <bits/stdc++.h>

using namespace std;

int main() {
    size_t T;
    cin >> T;
    for(size_t caso = 1; caso <= T; caso++) {
        int n, f, c;
        cin >> n >> f >> c;
        int v = n / f;
        n -= v * f;
        int s = n / c;
        cout << "Case #" << caso << ": " << v << " " << s << endl;
    }
    return 0;
}

gerarchie.cpp

#include <bits/stdc++.h>

using namespace std;

int f(int node, int parent, vector<vector<size_t>>& children, vector<int>& value) {
    queue<int> q;
    int n = children.size();
    vector<int> p(n, -1);
    vector<bool> visited(n, false);
    int maximum = node;
    visited[node] = true;
    for(size_t i = 0; i < children[node].size(); i++) {
        if(children[node][i] != parent) {
            q.push(children[node][i]);
            visited[children[node][i]] = true;
            p[children[node][i]] = node;
        }
    }
    if(q.empty()) {
        return 0;
    }
    while(!q.empty()) {
        int front = q.front();
        q.pop();
        if(value[front] > value[maximum]) {
            maximum = front;
        }
        for(size_t i = 0; i < children[front].size(); i++) {
            if(!visited[children[front][i]]) {
                q.push(children[front][i]);
                visited[children[front][i]] = true;
                p[children[front][i]] = front;
            }
        }
    }
    int swaps = 0;
    while(p[maximum] != -1) {
        swap(value[maximum], value[p[maximum]]);
        maximum = p[maximum];
        swaps += 1;
    }
    for(size_t i = 0; i < children[node].size(); i++) {
        if(children[node][i] != parent) {
            swaps += f(children[node][i], node, children, value);
        }
    }
    return swaps;
}

int main() {
    size_t T;
    cin >> T;
    for(size_t caso = 1; caso <= T; caso++) {
        size_t n;
        cin >> n;
        vector<vector<size_t>> children(n);
        vector<int> value(n);
        int root;
        for(size_t i = 0; i < n; i++) {
            int a, b;
            cin >> a >> b;
            if(a == -1) {
                root = i;
            } else {
                children[a].push_back(i);
                children[i].push_back(a);
            }
            value[i] = b;
        }
        cout << "Case #" << caso << ": " << f(root, -1, children, value) << endl;
    }
    return 0;
}

multicore.cpp

#include <bits/stdc++.h>

using namespace std;

int f(int n, int v, vector<int>& c, vector<int>& p, vector<vector<int>>& memo) {
    if(v < 0) {
        return -1;
    }
    if(memo[n][v] >= -1) {
        return memo[n][v];
    }
    if(n == 0) {
        if(v == 0) {
            return 0;
        } else {
            return -1;
        }
    }
    if(v == 0) {
        return 0;
    }
    int index = n - 1;
    int pp = f(n - 1, v - c[index], c, p, memo);
    int pn = f(n - 1, v, c, p, memo);
    if(pp >= 0 && pn >= 0) {
        memo[n][v] = min(pp + p[index], pn);
    } else if(pp >= 0) {
        memo[n][v] = pp + p[index];
    } else if(pn >= 0) {
        memo[n][v] = pn;
    } else {
        memo[n][v] = -1;
    }
    return memo[n][v];
}

int main() {
    size_t T;
    cin >> T;
    for(size_t caso = 1; caso <= T; caso++) {
        size_t n;
        int b;
        cin >> n >> b;
        vector<int> c(n);
        vector<int> p(n);
        int w = 0;
        for(size_t i = 0; i < n; i++) {
            cin >> c[i] >> p[i];
            w += c[i];
        }
        vector<vector<int>> memo(n + 1, vector<int>(w + 1, -2));
        int maximum = 0;
        for(int i = 1; i <= n; i++) {
            for(int j = 0; j <= w; j++) {
                int a = f(i, j, c, p, memo);
                if(a <= b && a >= 0) {
                    maximum = max(maximum, j);
                }
            }
        }
        cout << "Case #" << caso << ": " << maximum << endl;
    }
    return 0;
}

tornello.cpp

#include <bits/stdc++.h>

using namespace std;

int main() {
    size_t T;
    cin >> T;
    for(size_t caso = 1; caso <= T; caso++) {
        size_t n;
        cin >> n;
        int ma = 0, mi = 0, c = 0;
        for(size_t i = 0; i < n; i++) {
            int a;
            cin >> a;
            c += a;
            ma = max(ma, c);
            mi = min(mi, c);
        }
        cout << "Case #" << caso << ": " << ma - mi << endl;
    }
    return 0;
}