A - Ônibus Aeroportuário

Algoritmo guloso processa passageiros ordenados. Cada ônibus parte no tempo de chegada de um passageiro. Ao processar cada passageiro, libera-se o mínimo de ônibus necessário para acomodá-lo, respeitando o intervalo máximo de espera.

#include <algorithm>
#include <cctype>
#include <cstdio>
using namespace std;
typedef long long ll;

ll leitura() {
    int sinal = 1; ll num = 0; char c = getchar();
    while(!isdigit(c)) { if(c == '-') sinal = -1; c = getchar(); }
    while(isdigit(c)) num = num * 10 + (c - '0'), c = getchar();
    return sinal * num;
}

const int MAX = 100005;
int passageiros, capacidade, intervalo, tempos[MAX], inicio;

int main() {
    passageiros = leitura(), capacidade = leitura(), intervalo = leitura();
    for(int idx = 0; idx < passageiros; idx++) tempos[idx] = leitura();
    
    sort(tempos, tempos + passageiros);
    int onibus = 0;
    inicio = 0;

    for(int idx = 0; idx < passageiros; idx++) {
        while(inicio <= idx && tempos[idx] > tempos[inicio] + intervalo) {
            int vagas = capacidade;
            int limite = tempos[inicio] + intervalo;
            onibus++;
            while(vagas-- && inicio <= idx && tempos[inicio] <= limite) inicio++;
        }
    }
    printf("%d\n", onibus + (passageiros - inicio + capacidade - 1) / capacidade);
    return 0;
}

B - Criaturas Coloridas

Ordena-se as criaturas por tamanho. Uma criatura sobrevive se conseguir consumir todas menores e a próxima maior. Verifica-se sufixos: se a soma acumulada até uma posição é suficiente para consumir a criatura seguinte.

#include <algorithm>
#include <cstdio>
using namespace std;
typedef long long ll;

ll ler() {
    ll num = 0; char c = getchar();
    while(c < '0' || c > '9') c = getchar();
    while(c >= '0' && c <= '9') num = num * 10 + (c - '0'), c = getchar();
    return num;
}

const int MAXN = 100005;
ll tamanhos[MAXN], prefixo[MAXN];
int total;

int main() {
    total = ler();
    for(int i = 0; i < total; i++) tamanhos[i] = ler();
    sort(tamanhos, tamanhos + total);
    
    for(int i = 0; i < total; i++) 
        prefixo[i] = (i > 0 ? prefixo[i-1] : 0) + tamanhos[i];
    
    int sobreviventes = 1;
    for(int i = total - 2; i >= 0; i--) {
        if(prefixo[i] * 2 < tamanhos[i+1]) break;
        sobreviventes++;
    }
    printf("%d\n", sobreviventes);
    return 0;
}

C - Grafo Quadrático

Modela pares de vértices (a,b) como nós. Componentes conexas originais influenciam conectividade: componentes bipartidas contribuem diferentemente. Isolados geram pares específicos. Contabiliza-se componentes bipartidas e não-bipartidas.

#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
typedef long long ll;

ll ler() {
    ll num = 0; char c = getchar();
    while(c < '0' || c > '9') c = getchar();
    while(c >= '0' && c <= '9') num = num * 10 + (c - '0'), c = getchar();
    return num;
}

const int MAX = 100005;
vector<int> adj[MAX];
int vertices, arestas;
bool visitado[MAX], cor[MAX];

bool dfs(int u, int c, int &cont) {
    visitado[u] = true;
    cor[u] = c;
    cont++;
    bool bipartido = true;
    for(int v : adj[u]) {
        if(!visitado[v]) bipartido &= dfs(v, c^1, cont);
        else if(cor[u] == cor[v]) bipartido = false;
    }
    return bipartido;
}

int main() {
    vertices = ler(), arestas = ler();
    for(int i = 0; i < arestas; i++) {
        int u = ler(), v = ler();
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    int isolados = 0, bipartidas = 0, nao_bipartidas = 0;
    for(int i = 1; i <= vertices; i++) {
        if(visitado[i]) continue;
        int nos = 0;
        bool bp = dfs(i, 0, nos);
        if(nos == 1) isolados++;
        else if(bp) bipartidas++;
        else nao_bipartidas++;
    }
    
    ll resultado = 2LL * isolados * (vertices - isolados) + 1LL * isolados * isolados;
    resultado += 1LL * (bipartidas + nao_bipartidas) * (bipartidas + nao_bipartidas);
    resultado += 1LL * bipartidas * bipartidas;
    printf("%lld\n", resultado);
    return 0;
}

D - Refletor Semi-Transparente

Simulação com otimização. Reflexões invertem estados (A/B) e deslocam partículas. Após n operações, a configuração estabiliza em padrões alternados. Trata casos especiais para k grande usando paridade.

#include <cstdio>
#include <cctype>
using namespace std;

int ler() {
    int num = 0; char c = getchar();
    while(!isdigit(c)) c = getchar();
    while(isdigit(c)) num = num * 10 + (c - '0'), c = getchar();
    return num;
}

const int TAM = 400005;
int estados[TAM], comprimento, passos, pos;

int main() {
    comprimento = ler(), passos = ler();
    char c = getchar();
    while(c != 'A' && c != 'B') c = getchar();
    for(int i = 0; i < comprimento; i++) {
        estados[i] = (c == 'B') ? 1 : 0;
        c = getchar();
    }
    
    bool flip = false;
    pos = 0;
    int executados = 0;
    while(executados < passos && pos < comprimento) {
        if(estados[pos] ^ flip) {
            estados[pos] ^= 1;
            pos--;
            executados++;
        } else {
            flip ^= 1;
            estados[comprimento + pos] = flip;
            executados++;
            pos++;
        }
    }
    
    if(executados == passos) {
        for(int i = pos; i < pos + comprimento; i++) 
            putchar((estados[i] ^ flip) ? 'B' : 'A');
        return 0;
    }
    
    if(comprimento & 1) {
        putchar((passos - executados) & 1 ? 'B' : 'A');
        for(int i = 1; i < comprimento; i++) 
            putchar(i & 1 ? 'B' : 'A');
    } else {
        for(int i = 0; i < comprimento; i++) 
            putchar(i & 1 ? 'B' : 'A');
    }
    return 0;
}

E - Números Crescentes

Números crescentes são somas de repunits (111...1). Representando repunits como (10ᵗ-1)/9, busca-se o menor k tal que 9N+9k tenha soma de dígitos ≤ 9k. Incrementa k até satisfazer a condição.

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

const int TAM = 500505;
int digitos[TAM], comprimento;

int main() {
    string entrada;
    cin >> entrada;
    comprimento = entrada.size();
    reverse(entrada.begin(), entrada.end());
    
    for(int i = 0; i < comprimento; i++) 
        digitos[i] = (entrada[i] - '0') * 9;
    
    int soma_digitos = 0;
    for(int i = 0; i < comprimento; i++) {
        if(digitos[i] > 9) {
            digitos[i+1] += digitos[i] / 10;
            digitos[i] %= 10;
            if(i == comprimento-1) comprimento++;
        }
        soma_digitos += digitos[i];
    }
    
    if(soma_digitos == 0) {
        cout << "1\n";
        return 0;
    }
    
    int tentativas = 1;
    while(true) {
        digitos[0] += 9;
        soma_digitos += 9;
        int idx = 0;
        while(digitos[idx] > 9) {
            soma_digitos -= 9;
            digitos[idx] -= 10;
            digitos[++idx]++;
            if(idx == comprimento) comprimento++;
        }
        if(soma_digitos <= tentativas * 9) {
            cout << tentativas << "\n";
            return 0;
        }
        tentativas++;
    }
}

F - Planejamento de Serviço de Trens

Programação dinâmica com otimização por árvore de segmentos. Define-se estados baseados em tempos modulares. Atualizações de intervalo registram custos mínimos. Considera restrições de viagens simultâneas em trilhos únicos.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll ler() {
    ll num = 0; char c = getchar();
    while(c < '0' || c > '9') c = getchar();
    while(c >= '0' && c <= '9') num = num * 10 + (c - '0'), c = getchar();
    return num;
}

const ll INF = 1e18;
const int MAX = 100005;
int n, tipo[MAX];
ll a[MAX], suf[MAX], periodo;

struct Seg {
    int cnt, esq[MAX<<7], dir[MAX<<7];
    bool marcado[MAX<<7];
    ll valor[MAX<<7];

    void inicializar() { cnt = 1; valor[0] = INF; }

    void propagar(int no, int l, int r) {
        if(marcado[no]) {
            int m = (l + r) >> 1;
            if(!esq[no]) esq[no] = ++cnt;
            if(!dir[no]) dir[no] = ++cnt;
            marcado[esq[no]] = marcado[dir[no]] = true;
            valor[esq[no]] = -m;
            valor[dir[no]] = -r;
            marcado[no] = false;
        }
    }

    void atualizar(int &no, int l, int r, int pos, ll v) {
        if(!no) { no = ++cnt; valor[no] = INF; }
        if(l == r) { valor[no] = min(valor[no], v - pos); return; }
        propagar(no, l, r);
        int m = (l + r) >> 1;
        if(pos <= m) atualizar(esq[no], l, m, pos, v);
        else atualizar(dir[no], m+1, r, pos, v);
        valor[no] = min(valor[esq[no]], valor[dir[no]]);
    }

    void limpar(int no, int l, int r, int L, int R) {
        if(!no || valor[no] >= INF) return;
        if(L <= l && r <= R && (marcado[no] || l == r)) {
            marcado[no] = false;
            valor[no] = INF;
            return;
        }
        propagar(no, l, r);
        int m = (l + r) >> 1;
        if(L <= m) limpar(esq[no], l, m, L, R);
        if(R > m) limpar(dir[no], m+1, r, L, R);
        valor[no] = min(esq[no] ? valor[esq[no]] : INF, dir[no] ? valor[dir[no]] : INF);
    }

    void marcar(int &no, int l, int r, int L, int R) {
        if(!no) no = ++cnt;
        if(L <= l && r <= R) {
            marcado[no] = true;
            valor[no] = -r;
            return;
        }
        int m = (l + r) >> 1;
        if(L <= m) marcar(esq[no], l, m, L, R);
        if(R > m) marcar(dir[no], m+1, r, L, R);
        valor[no] = min(esq[no] ? valor[esq[no]] : INF, dir[no] ? valor[dir[no]] : INF);
    }

    ll consultar(int no, int l, int r, int L, int R) {
        if(!no) return INF;
        if(marcado[no]) return -min(r, R);
        if(L <= l && r <= R) return valor[no];
        propagar(no, l, r);
        int m = (l + r) >> 1;
        ll res = INF;
        if(L <= m) res = min(res, consultar(esq[no], l, m, L, R));
        if(R > m) res = min(res, consultar(dir[no], m+1, r, L, R));
        return res;
    }

    ll resposta(int no, int l, int r) {
        if(!no) return INF;
        if(marcado[no]) return 0;
        if(l == r) return valor[no] + l;
        propagar(no, l, r);
        int m = (l + r) >> 1;
        return min(resposta(esq[no], l, m), resposta(dir[no], m+1, r));
    }
} arvore;

int main() {
    n = ler(), periodo = ler();
    ll total = 0;
    for(int i = 1; i <= n; i++) {
        a[i] = ler();
        tipo[i] = ler();
        total += 2 * a[i];
        if(tipo[i] == 1 && 2 * a[i] > periodo) {
            printf("-1");
            return 0;
        }
    }

    while(n > 0 && tipo[n] == 2) n--;
    if(n == 0) {
        printf("%lld", total);
        return 0;
    }

    for(int i = n; i >= 1; i--) 
        suf[i] = (suf[i+1] + 2 * a[i]) % periodo;

    int raiz = 1;
    arvore.inicializar();
    arvore.marcar(raiz, 0, periodo-1, 0, periodo - 2 * a[n] - 1);

    for(int i = n-1; i >= 1; i--) {
        ll L = (periodo * 3 - 2 * a[i] - 2 * a[i+1] - suf[i+2]) % periodo;
        ll R = (periodo * 2 - suf[i+2] - 2 * a[i+1]) % periodo;
        ll temp = R;
        ll res = min(
            arvore.consultar(raiz, 0, periodo-1, temp, periodo-1) + temp + periodo,
            arvore.consultar(raiz, 0, periodo-1, 0, temp) + temp
        );

        if(tipo[i] == 1) {
            if(L <= R) arvore.limpar(raiz, 0, periodo-1, L, R);
            else {
                arvore.limpar(raiz, 0, periodo-1, L, periodo-1);
                arvore.limpar(raiz, 0, periodo-1, 0, R);
            }
        }
        arvore.atualizar(raiz, 0, periodo-1, (periodo - suf[i+1]) % periodo, res);
    }
    printf("%lld", arvore.resposta(1, 0, periodo-1) + total);
    return 0;
}