Quaranterry 2020 solutions

alberi2.cpp

#include <bits/stdc++.h>

using namespace std;

int64_t fastexp(int64_t b, int64_t e) {
    if(e == 0) {
        return 1;
    } else if(e % 2 == 1) {
        return b * fastexp(b, e - 1);
    } else {
        int64_t tmp = fastexp(b, e / 2);
        return tmp * tmp;
    }
}

int main() {
    size_t T;
    cin >> T;
    for(size_t caso = 1; caso <= T; caso++) {
        size_t n;
        int64_t v, y, k;
        cin >> n >> v >> y >> k;
        vector<int64_t> h(n);
        for(size_t i = 0; i < n; i++) {
            cin >> h[i];
        }
        vector<int64_t> prefix(n + 1);
        prefix[0] = 0;
        for(size_t i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + h[i];
        }
        vector<vector<int64_t>> memo(n, vector<int64_t>(n, -1LL));
        vector<vector<char>> choice(n, vector<char>(n));
        function<int64_t(size_t, size_t)> f = [&f, &memo, &choice, &h, &v, &k, &y, &n, &prefix](size_t index,
                                                                                                size_t upgrade) -> int64_t {
            if(index >= n) {
                return 0;
            }
            if(memo[index][upgrade] >= 0) {
                return memo[index][upgrade];
            }
            int64_t speed = v * fastexp(2LL, min(upgrade, 20UL));
            int64_t budget = prefix[index] - k * upgrade;
            int64_t a_choice = h[index] / speed + (h[index] % speed != 0) + f(index + 1, upgrade);
            memo[index][upgrade] = a_choice;
            choice[index][upgrade] = 'A';
            int64_t e_choice = y + f(index + 3, upgrade);
            if(e_choice < memo[index][upgrade]) {
                memo[index][upgrade] = e_choice;
                choice[index][upgrade] = 'E';
            }
            if(budget >= k) {
                speed *= 2LL;
                int64_t i_choice = h[index] / speed + (h[index] % speed != 0) + f(index + 1, upgrade + 1);
                if(i_choice < memo[index][upgrade]) {
                    memo[index][upgrade] = i_choice;
                    choice[index][upgrade] = 'I';
                }
            }
            return memo[index][upgrade];
        };
        f(0, 0);
        string sol;
        size_t i = 0;
        size_t upg = 0;
        while(i < n) {
            sol.push_back(choice[i][upg]);
            if(choice[i][upg] == 'A') {
                i++;
            } else if(choice[i][upg] == 'I') {
                i++;
                upg++;
            } else if(choice[i][upg] == 'E') {
                i += 3;
            } else {
                assert(!"UNREACHABLE");
            }
        }
        cout << "Case #" << caso << ": " << sol << endl;
    }
    return EXIT_SUCCESS;
}

ascensore.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, q;
        cin >> n >> q;
        vector<uint64_t> v(n);
        for(size_t i = 0; i < n; i++) {
            cin >> v[i];
        }
        sort(v.begin(), v.end());
        uint64_t best = ULLONG_MAX;
        uint64_t index = -1;
        for(size_t i = 0; i < q; i++) {
            uint64_t z;
            cin >> z;
            if(z <= v[0]) {
                if(v.back() - z < best) {
                    best = v.back() - z;
                    index = i;
                }
            } else if(z >= v.back()) {
                if(z - v[0] < best) {
                    best = z - v[0];
                    index = i;
                }
            } else {
                uint64_t sol = min(z - v[0], v.back() - z) + v.back() - v[0];
                if(sol < best) {
                    best = sol;
                    index = i;
                }
            }
        }
        cout << "Case #" << caso << ": " << index + 1 << endl;
    }
    return EXIT_SUCCESS;
}

carte.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;
        vector<int> a(n), b(n);
        for(size_t i = 0; i < n; i++) {
            cin >> a[i];
        }
        for(size_t i = 0; i < n; i++) {
            cin >> b[i];
        }
        sort(a.begin(), a.end());
        sort(b.begin(), b.end());
        reverse(a.begin(), a.end());
        int sol = 0;
        for(size_t i = 0; i < n; i++) {
            sol += max(b[i] - a[i], 0);
        }
        cout << "Case #" << caso << ": " << sol << endl;
    }
    return EXIT_SUCCESS;
}

dublino.cpp

#include <bits/stdc++.h>

using namespace std;

using is = pair<int64_t, size_t>;
using vis = vector<is>;

int main() {
    size_t T;
    cin >> T;
    for(size_t caso = 1; caso <= T; caso++) {
        size_t n, m, k;
        cin >> n >> m >> k;
        vector<vis> children(n);
        for(size_t i = 0; i < m; i++) {
            size_t a, b;
            int64_t c;
            cin >> a >> b >> c;
            a--;
            b--;
            children[a].emplace_back(c, b);
            children[b].emplace_back(c, a);
        }
        vector<int64_t> ticket(k);
        for(size_t i = 0; i < k; i++) {
            cin >> ticket[i];
        }
        sort(ticket.begin(), ticket.end());
        ticket.push_back(0);
        priority_queue<is, vis, greater<is>> pq;
        vector<int64_t> cost(n * (k + 1), LLONG_MAX);
        pq.emplace(0, 0);
        while(!pq.empty()) {
            auto top = pq.top();
            pq.pop();
            if(cost[top.second] <= top.first) {
                continue;
            }
            cost[top.second] = top.first;
            size_t node = top.second % n;
            size_t level = top.second / n;
            for(size_t i = 0; i < children[node].size(); i++) {
                if(top.first + children[node][i].first < cost[children[node][i].second + n * level]) {
                    pq.emplace(top.first + children[node][i].first, children[node][i].second + n * level);
                }
                if(level < k) {
                    if(top.first < cost[children[node][i].second + n * (level + 1)]) {
                        pq.emplace(top.first, children[node][i].second + n * (level + 1));
                    }
                }
            }
        }
        int64_t best = LLONG_MAX;
        int64_t prefix = accumulate(ticket.begin(), ticket.end(), 0LL);
        for(size_t i = 0; i <= k; i++) {
            best = min(best, cost[(n - 1) + n * i] - prefix);
            prefix -= ticket[i];
        }
        cout << "Case #" << caso << ": " << best << endl;
    }
    return EXIT_SUCCESS;
}

seed.cpp

#include <bits/stdc++.h>

using namespace std;

int main() {
    size_t T;
    cin >> T;
    for(size_t caso = 1; caso <= T; caso++) {
        uint64_t n;
        cin >> n;
        if(n <= 2) {
            cout << "Case #" << caso << ": -1" << endl;
        } else {
            cout << "Case #" << caso << ": " << 0 << " " << 1 << " " << n - 1 << endl;
        }
    }
    return EXIT_SUCCESS;
}