Projeto Prático da Disciplina de Projeto e Análise de Algoritmos 2019.1

Q1.cpp

#include <iostream>
#include <vector>

using namespace std;

struct Soldier { int id, strength; };

int main() {
    int n;
    cin >> n;

    vector <Soldier> soldiers(n);
    for (size_t i = 0; i < soldiers.size(); i++) {
        soldiers[i].id = i;
        cin >> soldiers[i].strength;
    }

    Soldier strongest = soldiers[0];
    for (size_t i = 1; i < soldiers.size(); i++) {
        if (soldiers[i].strength > strongest.strength) {
            strongest = soldiers[i];
        }
    }

    soldiers.erase(soldiers.begin() + strongest.id);

    Soldier weakest = soldiers[0];
    for (size_t i = 1; i < soldiers.size(); i++) {
        if (soldiers[i].strength > weakest.strength) {
            weakest = soldiers[i];
        }
    }

    int first = min(weakest.id, strongest.id);
    int second = max(weakest.id, strongest.id);
    cout << first + 1 << ' ' << second + 1 << endl;

    return 0;
}

Q2.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#define int unsigned long long // ;)

using namespace std;

int n, k;
vector <int> memo, a;

int f(int i) {
    if (i >= n) return 0;
    if (~memo[i]) return memo[i];
    return memo[i] = max(f(i+1), a[i] + f(i+k));
}

signed main() {
    cin >> n;
    a.assign(n, 0);
    memo.assign(n, -1);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    cin >> k;
    f(0);
    cout << *max_element(memo.begin(), memo.end()) << endl;

    return 0;
}

Q3.cpp

#include <iostream>
#include <algorithm>
#include <vector>
#define int unsigned long long // ¯\_(ツ)_/¯

using namespace std;

struct Cuboid {
    int h, l, w;
    int sumSquares() {
        return (h * h) + (l * l) + (w * w);
    }
};

bool cmp(Cuboid& a, Cuboid& b) {
    return a.sumSquares() < b.sumSquares();
}

signed main() {
    ios_base::sync_with_stdio(0);

    int n;
    cin >> n;
    vector <Cuboid> cuboids(n);
    for (int i = 0; i < n; i++) {
        cin >> cuboids[i].h;
        cin >> cuboids[i].l;
        cin >> cuboids[i].w;
    }

    vector <int> r(n);
    for (int i = 0; i < n; i++) {
        cin >> r[i];
    }

    sort(cuboids.begin(), cuboids.end(), cmp);
    sort(r.begin(), r.end());
    int ans = 0;
    for (int i = 0, j = 0; i < n and j < n; i++) {
        if (cuboids[j].sumSquares() <= 4LL * r[i] * r[i]) {
            ans++, j++;
        }
    }

    cout << ans << endl;

    return 0;
}

Q4.cpp

#include <iostream>
using namespace std;

int main() {
    long long n, c;
    cin >> n >> c;
    cout << (n > c ? c+((n-c+1)*(n-c+2))/2-1 : n) << endl;

    return 0;
}