Soluzioni OII territoriali 2018

antivirus.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 n1, n2, n3, n4, m;
        cin >> n1 >> n2 >> n3 >> n4 >> m;
        string a, b, c, d;
        cin >> a >> b >> c >> d;
        for(size_t i1 = 0; i1 <= n1 - m; i1++) {
            for(size_t i2 = 0; i2 <= n2 - m; i2++) {
                for(size_t i3 = 0; i3 <= n3 - m; i3++) {
                    for(size_t i4 = 0; i4 <= n4 - m; i4++) {
                        bool ok = true;
                        for(size_t j = 0; j < m && ok; j++) {
                            ok = ok && (a[i1 + j] == b[i2 + j]);
                            ok = ok && (a[i1 + j] == c[i3 + j]);
                            ok = ok && (a[i1 + j] == d[i4 + j]);
                        }
                        if(ok) {
                            cout << "Case #" << caso << ": " << i1 << " " << i2 << " " << i3 << " " << i4 << endl;
                        }
                    }
                }
            }
        }
    }
    return 0;
}

escursione.cpp

#include <bits/stdc++.h>

using namespace std;

bool dfs(int row, int col, int k, vector<vector<bool>>& visited, vector<vector<int>>& m) {
    int rows = m.size();
    int cols = m[0].size();
    visited[row][col] = true;
    if(row == rows - 1 && col == cols - 1) {
        return true;
    }
    bool ok = false;
    if(col > 0 && abs(m[row][col] - m[row][col - 1]) <= k && !visited[row][col - 1]) {
        ok = ok || dfs(row, col - 1, k, visited, m);
    }
    if(row > 0 && abs(m[row][col] - m[row - 1][col]) <= k && !visited[row - 1][col]) {
        ok = ok || dfs(row - 1, col, k, visited, m);
    }
    if(col < cols - 1 && abs(m[row][col] - m[row][col + 1]) <= k && !visited[row][col + 1]) {
        ok = ok || dfs(row, col + 1, k, visited, m);
    }
    if(row < rows - 1 && abs(m[row][col] - m[row + 1][col]) <= k && !visited[row + 1][col]) {
        ok = ok || dfs(row + 1, col, k, visited, m);
    }
    return ok;
}

int main() {
    size_t T;
    cin >> T;
    for(size_t caso = 1; caso <= T; caso++) {
        int cols, rows;
        cin >> rows >> cols;
        vector<vector<int>> m(rows, vector<int>(cols));
        for(size_t i = 0; i < rows; i++) {
            for(size_t j = 0; j < cols; j++) {
                cin >> m[i][j];
            }
        }
        int lo = -1, hi = 1000001;
        while(lo + 1 < hi) {
            vector<vector<bool>> visited(rows, vector<bool>(cols));
            int mid = (lo + hi) / 2;
            if(dfs(0, 0, mid, visited, m)) {
                hi = mid;
            } else {
                lo = mid;
            }
        }
        cout << "Case #" << caso << ": " << hi << endl;
    }
    return 0;
}

party.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 acc = 0;
        for(size_t i = 0; i < n; i++) {
            int a;
            cin >> a;
            if(a > 0) {
                acc += a;
            }
        }
        cout << "Case #" << caso << ": " << acc << endl;
    }
    return 0;
}

xray.cpp

#include <bits/stdc++.h>

using namespace std;

int f(int start, int size, vector<int>& v) {
    if(size == 0) {
        return 0;
    }
    if(size == 1) {
        return v[start];
    }
    int minimum = start;
    for(int i = start + 1; i < start + size; i++) {
        if(v[i] < v[minimum]) {
            minimum = i;
        }
    }
    int value = v[minimum];
    for(int i = start; i < start + size; i++) {
        v[i] -= value;
    }
    return f(start, minimum - start, v) + f(minimum + 1, start + size - minimum - 1, v) + value;
}

int main() {
    size_t T;
    cin >> T;
    for(size_t caso = 1; caso <= T; caso++) {
        size_t n;
        cin >> n;
        vector<int> v(n);
        for(size_t i = 0; i < n; i++) {
            cin >> v[i];
        }
        cout << "Case #" << caso << ": " << f(0, n, v) << endl;
    }
    return 0;
}