A. Ano Quadrado

Verifique se um número é quadrado perfeito usando sqrtl. Se positivo, retorne 0 e a raiz; caso contrário, retorne -1.

#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int testes;
    cin >> testes;
    while (testes--) {
        string entrada;
        cin >> entrada;
        ll valor = 0;
        for (char c : entrada) valor = valor * 10 + (c - '0');
        ll raiz = sqrtl(valor);
        if (raiz * raiz == valor) cout << 0 << " " << raiz << "\n";
        else cout << -1 << "\n";
    }
    return 0;
}

B. String Quase-Palíndroma

Conte os dígitos 0 e 1. Tente formar pares priorizando o dígito mais frequente. Se caracteres sobrarem após k operações, retorne "NO".

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int casos;
    cin >> casos;
    while (casos--) {
        int n, k;
        cin >> n >> k;
        string s;
        cin >> s;
        int zeros = 0, uns = 0;
        for (char c : s) (c == '0') ? zeros++ : uns++;
        bool valido = true;
        while (k--) {
            if (zeros >= uns) {
                if (zeros >= 2) zeros -= 2;
                else {valido = false; break;}
            } else {
                if (uns >= 2) uns -= 2;
                else {valido = false; break;}
            }
        }
        if (zeros > 0 && uns > 0) valido = false;
        cout << (valido ? "YES" : "NO") << "\n";
    }
}

C. Arrays Adicionais

Agrupe segmentos contínuos não decrescentes. Para cada segmento, calcule (tamanho + 1) / 2 e some os resultados.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int testes;
    cin >> testes;
    while (testes--) {
        int n;
        cin >> n;
        vector<long> arr(n);
        for (int i = 0; i < n; i++) cin >> arr[i];
        long total = 0, seq = 1;
        for (int i = 1; i < n; i++) {
            if (arr[i] == arr[i-1] + 1) seq++;
            else if (arr[i] != arr[i-1]) {
                total += (seq + 1) / 2;
                seq = 1;
            }
        }
        total += (seq + 1) / 2;
        cout << total << "\n";
    }
}

D. Aproximação de Pontos

Armazene coordenadas em sets. Parra cada ponto, remova-o temporariamente e calcule a área mínima possível com os pontos restantes.

#include <iostream>
#include <set>
#include <climits>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int casos;
    cin >> casos;
    while (casos--) {
        int n;
        cin >> n;
        set<pair<long, long>> linhas, colunas;
        for (int i = 0; i < n; i++) {
            long x, y;
            cin >> x >> y;
            linhas.insert({x, i});
            colunas.insert({y, i});
        }
        if (n == 1) {
            cout << 1 << "\n";
            continue;
        }
        long menor_area = LONG_MAX;
        for (int i = 0; i < n; i++) {
            auto min_lin = *linhas.begin();
            auto max_lin = *linhas.rbegin();
            auto min_col = *colunas.begin();
            auto max_col = *colunas.rbegin();
            if (min_lin.second == i) min_lin = *next(linhas.begin());
            if (max_lin.second == i) max_lin = *prev(linhas.end());
            if (min_col.second == i) min_col = *next(colunas.begin());
            if (max_col.second == i) max_col = *prev(colunas.end());
            long largura = max_lin.first - min_lin.first + 1;
            long altura = max_col.first - min_col.first + 1;
            if (largura * altura == n - 1) {
                menor_area = min(menor_area, min((largura + 1) * altura, largura * (altura + 1)));
            } else {
                menor_area = min(menor_area, largura * altura);
            }
        }
        cout << menor_area << "\n";
    }
}

E. Ataque à Propriedade

Realize uma DFS calculando dois estados DP por nó (profundidade par/ímpar). Propague valores máximos do pai para os filhoss.

#include <iostream>
#include <vector>
#include <functional>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int testes;
    cin >> testes;
    while (testes--) {
        int n;
        cin >> n;
        vector<long> valores(n+1);
        vector<vector<int>> grafo(n+1);
        for (int i = 1; i <= n; i++) cin >> valores[i];
        for (int i = 1; i < n; i++) {
            int u, v;
            cin >> u >> v;
            grafo[u].push_back(v);
            grafo[v].push_back(u);
        }
        vector<int> profundidade(n+1);
        vector<vector<long>> dp(n+1, vector<long>(2, 0));
        vector<long> res(n+1);
        function<void(int, int)> dfs = [&](int no, int pai) {
            profundidade[no] = profundidade[pai] + 1;
            int paridade = profundidade[no] % 2;
            dp[no][paridade] = max(valores[no], dp[pai][paridade] + valores[no]);
            dp[no][!paridade] = dp[pai][!paridade] - valores[no];
            for (int viz : grafo[no]) {
                if (viz == pai) continue;
                dfs(viz, no);
            }
            res[no] = dp[no][paridade];
        };
        profundidade[0] = -1;
        dfs(1, 0);
        for (int i = 1; i <= n; i++) cout << res[i] << " ";
        cout << "\n";
    }
}

F. Operações Pequenas

Fatore x e y. Se produtos dos fatores > k forem diferentes, retorne -1. Caso contrário, calcule custos de transformação via DP recursiva.

#include <iostream>
#include <vector>
#include <set>
#include <cmath>
using namespace std;
typedef long long ll;

const int LIMITE = 1000000;
vector<int> fatores[LIMITE+1];

void preencher_fatores() {
    vector<bool> primo(LIMITE+1, true);
    for (int i = 2; i <= LIMITE; i++) {
        if (primo[i]) {
            for (int j = i; j <= LIMITE; j += i) {
                primo[j] = false;
                int temp = j;
                while (temp % i == 0) {
                    fatores[j].push_back(i);
                    temp /= i;
                }
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    preencher_fatores();
    int testes;
    cin >> testes;
    while (testes--) {
        ll x, y, k;
        cin >> x >> y >> k;
        if (x == y) {
            cout << 0 << "\n";
            continue;
        }
        if (k == 1) {
            cout << -1 << "\n";
            continue;
        }
        ll prod_x = 1, prod_y = 1;
        multiset<ll> freq_x, freq_y;
        for (int f : fatores[x]) {
            if (f > k) prod_x *= f;
            freq_x.insert(f);
        }
        for (int f : fatores[y]) {
            if (f > k) prod_y *= f;
            freq_y.insert(f);
        }
        if (prod_x != prod_y) {
            cout << -1 << "\n";
            continue;
        }
        auto calcular = [&](ll num) -> ll {
            if (num == 1) return 0;
            vector<ll> divisores;
            for (ll d = 1; d*d <= num; d++) {
                if (num % d == 0) {
                    if (d <= k) divisores.push_back(d);
                    if (num/d != d && num/d <= k) divisores.push_back(num/d);
                }
            }
            sort(divisores.begin(), divisores.end());
            function<ll(int, ll)> resolver = [&](int idx, ll atual) -> ll {
                if (atual == 1) return 0;
                if (idx < 0) return 1e18;
                ll minimo = 1e18;
                for (int i = idx; i >= 0; i--) {
                    if (atual % divisores[i] == 0) {
                        minimo = min(minimo, resolver(i, atual/divisores[i]) + 1);
                    }
                }
                return minimo;
            };
            return resolver(divisores.size()-1, num);
        };
        ll alvo_x = 1, alvo_y = 1;
        for (int f : freq_x) {
            if (freq_y.count(f) < freq_x.count(f)) {
                int diff = freq_x.count(f) - freq_y.count(f);
                while (diff--) alvo_y *= f;
            }
        }
        for (int f : freq_y) {
            if (freq_x.count(f) < freq_y.count(f)) {
                int diff = freq_y.count(f) - freq_x.count(f);
                while (diff--) alvo_x *= f;
            }
        }
        cout << calcular(alvo_x) + calcular(alvo_y) << "\n";
    }
}

G. Construir um Array

Para cada elemento, decomponha-o em fatores mínimos. Use somas prefixo/sufixo para calcular operações necessárias e verifique se ≤ k.

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int testes;
    cin >> testes;
    while (testes--) {
        ll n, k;
        cin >> n >> k;
        vector<ll> arr(n+2, 0), base(n+1);
        for (int i = 1; i <= n; i++) cin >> arr[i];
        if (n == k) {
            cout << "YES\n";
            continue;
        }
        for (int i = 1; i <= n; i++) {
            ll temp = arr[i];
            while (temp % 2 == 0) temp /= 2;
            base[i] = temp;
        }
        vector<ll> prefixo(n+2, 0), sufixo(n+2, 0);
        for (int i = 1; i <= n; i++) {
            ll atual = arr[i], esq = arr[i-1];
            ll passos = 0, flag = 0;
            while (atual) {
                if (atual == esq) flag = passos;
                if (atual & 1) break;
                atual /= 2;
                passos++;
            }
            prefixo[i] = (flag ? 1 + ((1LL << (flag-1)) - 1) * (arr[i] / (1LL << (flag-1)) / esq) : (1LL << passos));
        }
        for (int i = n; i >= 1; i--) {
            ll atual = arr[i], dir = arr[i+1];
            ll passos = 0, flag = 0;
            while (atual) {
                if (atual == dir) flag = passos;
                if (atual & 1) break;
                atual /= 2;
                passos++;
            }
            sufixo[i] = (flag ? 1 + ((1LL << (flag-1)) - 1) * (arr[i] / (1LL << (flag-1)) / dir) : (1LL << passos));
        }
        ll total_ops = 0;
        for (int i = 1; i <= n; i++) {
            ll expoentes = 0, num = arr[i];
            while (num % 2 == 0) {
                expoentes++;
                num /= 2;
            }
            ll ops = prefixo[i-1] + sufixo[i+1] + (1LL << expoentes);
            total_ops = max(total_ops, ops);
        }
        cout << (total_ops <= k ? "YES" : "NO") << "\n";
    }
}