A. Design Simples

Uma aobrdagem de força bruta é viável aqui, já que o limite superior de 1e9 não é atingido na prática. O objetivo é encontrar o menor inteiro maior ou igual a x cuja soma dos dígitos seja divisível por k.

#include <iostream>
using namespace std;

void resolver() {
    long long inicio, divisivel_por;
    cin >> inicio >> divisivel_por;
    for (long long candidato = inicio; candidato <= 2000000000; candidato++) {
        long long temporario = candidato;
        int soma_digitos = 0;
        while (temporario > 0) {
            soma_digitos += temporario % 10;
            temporario /= 10;
        }
        if (soma_digitos % divisivel_por == 0 && soma_digitos >= divisivel_por) {
            cout << candidato << endl;
            return;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int testes;
    cin >> testes;
    while (testes--) resolver();
    return 0;
}

B. Casa Mal-Assombrada

Este problema envolve manipulação de uma string binária e cálculo de custos para transformar '0's em '1's com base em índices. A string é invertida e processada para determinar os custos mínimos acumulados.

#include <iostream>
#include <string>
#include <deque>
#include <algorithm>
using namespace std;

void resolver() {
    int n;
    string s;
    cin >> n >> s;
    reverse(s.begin(), s.end());
    deque<int> posicoes_zero;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '0') posicoes_zero.push_back(i);
    }
    if (posicoes_zero.empty()) {
        for (int i = 0; i < s.size(); i++) cout << -1 << " ";
        cout << endl;
        return;
    }
    long long custo = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '0') {
            posicoes_zero.pop_front();
            cout << custo << " ";
        } else {
            if (posicoes_zero.empty()) {
                for (int j = i; j < s.size(); j++) cout << -1 << " ";
                cout << endl;
                return;
            } else {
                custo += posicoes_zero.front() - i;
                s[posicoes_zero.front()] = '1';
                posicoes_zero.pop_front();
                cout << custo << " ";
            }
        }
    }
    cout << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int testes;
    cin >> testes;
    while (testes--) resolver();
    return 0;
}

C. Design Médio

Existe uma conclusão: o mínimo deve estar na posição 1 ou na posição m. O problema utiliza soma de prefixos e compressão de coordenadas para calcular a máximma sobreposição de intervalos em relação a essas posições.

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

const int MAXN = 200010;
int prefix[MAXN], inverso[MAXN];

void resolver() {
    int n, m;
    cin >> n >> m;
    vector<int> pontos;
    pontos.push_back(1);
    pontos.push_back(m);
    vector<pair<int,int>> intervalos(n);
    for (auto &inter : intervalos) {
        cin >> inter.first >> inter.second;
        pontos.push_back(inter.first);
        pontos.push_back(inter.second);
    }
    sort(pontos.begin(), pontos.end());

    memset(prefix, 0, sizeof(prefix));
    memset(inverso, 0, sizeof(inverso));

    int idx_m = lower_bound(pontos.begin(), pontos.end(), m) - pontos.begin() + 1;
    for (auto &inter : intervalos) {
        inter.first = lower_bound(pontos.begin(), pontos.end(), inter.first) - pontos.begin() + 1;
        inter.second = lower_bound(pontos.begin(), pontos.end(), inter.second) - pontos.begin() + 1;
    }

    for (auto [l, r] : intervalos) {
        if (l > 1) {
            prefix[l]++;
            prefix[r + 1]--;
        }
        if (r < idx_m) {
            inverso[l]++;
            inverso[r + 1]--;
        }
    }
    for (int i = 1; i <= idx_m; i++) {
        prefix[i] += prefix[i - 1];
        inverso[i] += inverso[i - 1];
    }
    int max_prefix = *max_element(prefix + 1, prefix + 1 + idx_m);
    int max_inverso = *max_element(inverso + 1, inverso + 1 + idx_m);
    cout << max(max_prefix, max_inverso) << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int testes;
    cin >> testes;
    while (testes--) resolver();
    return 0;
}

D. Contagem de Rimas

Este problema conta o número de pares com GCD específico e utiliza uma técnica similar ao crivo de Eratóstenes para otimização. A solução envolve calcular a contagem de múltiplos e subtrair as contribuições de GCDs maiores.

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

const int MAXVAL = 1000010;
int contagem[MAXVAL];
int contagem_exata[MAXVAL];
bool visitado[MAXVAL];

void resolver() {
    int n;
    cin >> n;
    vector<int> arr(n);
    int maximo = 0;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        contagem[arr[i]]++;
        maximo = max(maximo, arr[i]);
    }
    for (int i = 1; i <= maximo; i++) {
        for (int j = 2 * i; j <= maximo; j += i) {
            contagem[i] += contagem[j];
        }
    }
    for (int i = maximo; i > 0; i--) {
        contagem_exata[i] = contagem[i] * (contagem[i] - 1) / 2;
        for (int j = 2 * i; j <= maximo; j += i) {
            contagem_exata[i] -= contagem_exata[j];
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = arr[i]; j <= maximo; j += arr[i]) {
            visitado[j] = true;
        }
    }
    long long resposta = 0;
    for (int i = 1; i <= maximo; i++) {
        if (!visitado[i]) {
            resposta += contagem_exata[i];
        }
    }
    cout << resposta << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int testes;
    cin >> testes;
    while (testes--) resolver();
    return 0;
}