Problema A: Timeout

Verificar se para toda sequência de inteiros \(a_1, a_2, \dots, a_n\), com \(a_0 = 0\), a condição \(a_i - a_{i-1} \le S\) é satisfeita para cada \(i\) entre 1 e \(n\).

A solução envolve iterar pelos elementos e comparar as diferenças consecutivas com o limite.

#include <iostream>
using namespace std;

int main() {
    int n, limite, valorAnterior = 0, valorAtual;
    cin >> n >> limite;
    for (int i = 0; i < n; ++i) {
        cin >> valorAtual;
        if (valorAtual - valorAnterior > limite) {
            cout << "No" << endl;
            return 0;
        }
        valorAnterior = valorAtual;
    }
    cout << "Yes" << endl;
    return 0;
}

Problema B: Compression

Dado um array \(A\), ordenar seus elementos e remover duplicatas, em seguida imprimir o array resultante.

A implementação utiliza funções da biblioteca padrão para ordenação e remoção de duplicatas.

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

int main() {
    int tamanho;
    cin >> tamanho;
    vector<int> vetor(tamanho);
    for (int i = 0; i < tamanho; ++i) {
        cin >> vetor[i];
    }
    sort(vetor.begin(), vetor.end());
    auto iteradorUnico = unique(vetor.begin(), vetor.end());
    int novoTamanho = iteradorUnico - vetor.begin();
    cout << novoTamanho << endl;
    for (int i = 0; i < novoTamanho; ++i) {
        cout << vetor[i];
        if (i < novoTamanho - 1) cout << " ";
    }
    cout << endl;
    return 0;
}

Problema C: Not All Covered

Dado vários intervalos, encontrar o número mínimo de intervalos a remover para que exista pelo menos um ponto não coberto por nenhum intervalo restante.

Transforma-se o problema em calcular a cobertura mínima global usando um array de diferenças.

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> diferenca(n + 2, 0);
    for (int i = 0; i < m; ++i) {
        int esquerda, direita;
        cin >> esquerda >> direita;
        diferenca[esquerda]++;
        diferenca[direita + 1]--;
    }
    int cobertura = 0, minimo = 1e9;
    for (int i = 1; i <= n; ++i) {
        cobertura += diferenca[i];
        minimo = min(minimo, cobertura);
    }
    cout << minimo << endl;
    return 0;
}

Problema D: Flip to Gather

Dada uma string de 0s e 1s, encontrar o número mínimo de operações para transformá-la em uma string com no máximo um segmento contínuo de 1s. Uma operação consiste em inverter um caractere.

A solução usa programação dinâmica para rastrear o custo mínimo de transformação em cada posição, combinando com um array de sufixo.

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

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        string s;
        cin >> s;
        s = " " + s; // Ajuste de índice
        vector<vector<int>> dp(n + 1, vector<int>(2, 0));
        vector<int> sufixo(n + 2, 0);
        for (int i = 1; i <= n; ++i) {
            if (s[i] == '1') {
                dp[i][0] = dp[i-1][0] + 1;
                dp[i][1] = min(dp[i-1][0], dp[i-1][1]);
            } else {
                dp[i][0] = dp[i-1][0];
                dp[i][1] = min(dp[i-1][0], dp[i-1][1]) + 1;
            }
        }
        int resposta = min(dp[n][0], dp[n][1]);
        for (int i = n; i >= 1; --i) {
            sufixo[i] = sufixo[i+1] + (s[i] == '1' ? 1 : 0);
            resposta = min(resposta, sufixo[i] + dp[i-1][1]);
        }
        cout << resposta << endl;
    }
    return 0;
}

Problema E: Minimum OR Path

Encontrar o caminho de menor custo em um grafo, onde o custo é o OR bit a bit dos pesos das arestas no caminho.

A abordagem utiliza conjuntos disjuntos e eliminação de bits, processando dos bits mais significativos para os menos significativos.

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

struct Aresta {
    int origem, destino, peso;
    bool operator<(const Aresta& outro) const {
        return peso < outro.peso;
    }
};

vector<int> pai;

int encontrar(int x) {
    if (pai[x] != x) {
        pai[x] = encontrar(pai[x]);
    }
    return pai[x];
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<Aresta> arestas(m);
    for (int i = 0; i < m; ++i) {
        cin >> arestas[i].origem >> arestas[i].destino >> arestas[i].peso;
    }
    sort(arestas.begin(), arestas.end());
    int resposta = 0;
    pai.resize(n + 1);
    for (int bit = 29; bit >= 0; --bit) {
        for (int i = 1; i <= n; ++i) {
            pai[i] = i;
        }
        int maxPeso = 0;
        for (auto& aresta : arestas) {
            int raizOrigem = encontrar(aresta.origem);
            int raizDestino = encontrar(aresta.destino);
            if (raizOrigem != raizDestino) {
                pai[raizOrigem] = raizDestino;
                maxPeso = max(maxPeso, aresta.peso);
            }
            if (encontrar(1) == encontrar(n)) break;
        }
        if (arestas.empty() || maxPeso == 0) break;
        int bitSignificativo = log2(maxPeso);
        resposta |= (1 << bitSignificativo);
        vector<Aresta> novasArestas;
        for (auto& aresta : arestas) {
            if (aresta.peso < (1 << (bitSignificativo + 1))) {
                aresta.peso &= ~(1 << bitSignificativo);
                novasArestas.push_back(aresta);
            }
        }
        arestas = novasArestas;
        sort(arestas.begin(), arestas.end());
    }
    cout << resposta << endl;
    return 0;
}

Problema F: Athletic

Dada uma permutação \(p\), e parâmetros \(R\) e \(D\), encontrar o número máximo de movimentos possíveis, onde de uma posição \(i\) pode-se mover para \(j\) se \(|i-j| \le R\) e \(p_j \le p_i + D\).

A solução usa programação dinâmica com uma árvore de segmentos para otimizar a consulta de máximo em intervalos.

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

vector<int> segmento;

void atualizar(int no, int esq, int dir, int pos, int valor) {
    if (esq == dir) {
        segmento[no] = valor;
        return;
    }
    int meio = (esq + dir) / 2;
    if (pos <= meio) atualizar(2*no, esq, meio, pos, valor);
    else atualizar(2*no+1, meio+1, dir, pos, valor);
    segmento[no] = max(segmento[2*no], segmento[2*no+1]);
}

int consultar(int no, int esq, int dir, int l, int r) {
    if (r < esq || dir < l) return -1;
    if (l <= esq && dir <= r) return segmento[no];
    int meio = (esq + dir) / 2;
    int maxEsq = consultar(2*no, esq, meio, l, r);
    int maxDir = consultar(2*no+1, meio+1, dir, l, r);
    return max(maxEsq, maxDir);
}

int main() {
    int n, d, r;
    cin >> n >> d >> r;
    vector<int> permutacao(n+1), inversa(n+1);
    for (int i = 1; i <= n; ++i) {
        cin >> permutacao[i];
        inversa[permutacao[i]] = i;
    }
    segmento.assign(4*n, -1);
    vector<int> dp(n+1, 0);
    int maxMovimentos = 0;
    for (int valor = n; valor >= 1; --valor) {
        int posAtual = inversa[valor];
        int posInsercao = inversa[valor + d];
        if (valor + d <= n) {
            atualizar(1, 1, n, posInsercao, dp[valor + d]);
        }
        int esquerda = max(1, posAtual - r);
        int direita = min(n, posAtual + r);
        dp[valor] = consultar(1, 1, n, esquerda, direita) + 1;
        maxMovimentos = max(maxMovimentos, dp[valor]);
    }
    cout << maxMovimentos << endl;
    return 0;
}

Problema G: A/B < p/q < C/D

Dados \(A, B, C, D\), encontrar o menor denominador \(q\) tal que exista um numerador \(p\) satisfazendo \(A/B < p/q < C/D\).

A solução usa uma abordagem recursiva baseada em frações continuadas.

#include <iostream>
using namespace long long;

void resolverFracoes(long long a, long long b, long long c, long long d, long long& p, long long& q) {
    if (a < b && c > d) {
        p = 1; q = 1;
        return;
    }
    long long quociente = d / c;
    resolverFracoes(d % c, c, b - quociente * a, a, q, p);
    q += quociente * p;
}

int main() {
    int casos;
    cin >> casos;
    while (casos--) {
        long long a, b, c, d;
        cin >> a >> b >> c >> d;
        long long p, q;
        resolverFracoes(a, b, c, d, p, q);
        cout << q << '\n';
    }
    return 0;
}