Ordenação de Estruturas Personalizadas

Em problemas que exigem a classificação de entidades com múltiplos critérios, a utilização de estruturas personalizadas combinadas com funções de comparação customizadas é fundamental. O cenário abaixo demonstra o cálculo de saldo líquido e a ordenação decrescente baseada em saldo, quantidade de recebimentos e identificador único.

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>

struct Participante {
    int id;
    long long saldo_liquido;
    int pacotes_recebidos;
};

bool compararParticipantes(const Participante& a, const Participante& b) {
    if (a.saldo_liquido != b.saldo_liquido) return a.saldo_liquido > b.saldo_liquido;
    if (a.pacotes_recebidos != b.pacotes_recebidos) return a.pacotes_recebidos > b.pacotes_recebidos;
    return a.id < b.id;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    int n;
    if (!(std::cin >> n)) return 0;
    
    std::vector<Participante> participantes(n);
    for (int i = 0; i < n; ++i) {
        participantes[i].id = i + 1;
        participantes[i].saldo_liquido = 0;
        participantes[i].pacotes_recebidos = 0;
    }
    
    for (int i = 0; i < n; ++i) {
        int num_pacotes;
        std::cin >> num_pacotes;
        long long total_gasto = 0;
        
        for (int j = 0; j < num_pacotes; ++j) {
            int destinatario;
            long long valor;
            std::cin >> destinatario >> valor;
            
            participantes[destinatario - 1].saldo_liquido += valor;
            participantes[destinatario - 1].pacotes_recebidos++;
            total_gasto += valor;
        }
        participantes[i].saldo_liquido -= total_gasto;
    }
    
    std::sort(participantes.begin(), participantes.end(), compararParticipantes);
    
    for (const auto& p : participantes) {
        std::cout << p.id << " " << std::fixed << std::setprecision(2) << (p.saldo_liquido / 100.0) << "\n";
    }
    
    return 0;
}

Simulação de Reorganização com Pilhas

A reorganização de sequências utilizando uma área de buffer pode ser modelada eficientemente com a estrutura de dados Pilha (Stack). O algoritmo a seguir simula o movimento de vagões, priorizando a saída direta e utilizando o buffer apenas quando a sequência alvo não pode ser atendida imediatamente.

#include <iostream>
#include <string>
#include <stack>
#include <vector>

int main() {
    std::string sequencia_entrada, sequencia_alvo;
    if (!(std::cin >> sequencia_entrada >> sequencia_alvo)) return 0;
    
    std::stack<char> trilho_entrada;
    std::stack<char> buffer;
    std::vector<std::string> registros_movimento;
    
    for (int i = sequencia_entrada.size() - 1; i >= 0; --i) {
        trilho_entrada.push(sequencia_entrada[i]);
    }
    
    int indice_alvo = 0;
    bool possivel = true;
    
    while (indice_alvo < sequencia_alvo.size()) {
        char alvo_atual = sequencia_alvo[indice_alvo];
        
        if (!trilho_entrada.empty() && trilho_entrada.top() == alvo_atual) {
            registros_movimento.push_back("1->2");
            trilho_entrada.pop();
        } else if (!buffer.empty() && buffer.top() == alvo_atual) {
            registros_movimento.push_back("3->2");
            buffer.pop();
        } else if (!trilho_entrada.empty()) {
            registros_movimento.push_back("1->3");
            buffer.push(trilho_entrada.top());
            trilho_entrada.pop();
            continue; 
        } else {
            possivel = false;
            break;
        }
        indice_alvo++;
    }
    
    if (possivel) {
        for (const auto& mov : registros_movimento) {
            std::cout << mov << "\n";
        }
    } else {
        std::cout << "Are you kidding me?\n";
    }
    
    return 0;
}

Fatoração e Sequências de Fatores Contíguos

Para encontrar a maior sequência de fatores contíguos de um número inteiro, iteramos a partir dos menores fatores possíveis. A otimização ocorre ao limitar a busca até a raiz quadrada do número e atualizar os registros de comprimento máximo dinamicamente.

#include <iostream>
#include <cmath>

int main() {
    long long n;
    if (!(std::cin >> n)) return 0;
    
    int max_comprimento = 0;
    long long melhor_inicio = 0;
    
    for (long long i = 2; i <= std::sqrt(n) + 1; ++i) {
        long long produto = 1;
        for (long long j = i; produto * j <= n; ++j) {
            produto *= j;
            if (n % produto == 0) {
                int comprimento_atual = j - i + 1;
                if (comprimento_atual > max_comprimento) {
                    max_comprimento = comprimento_atual;
                    melhor_inicio = i;
                }
            }
        }
    }
    
    if (max_comprimento == 0) {
        std::cout << 1 << "\n" << n << "\n";
    } else {
        std::cout << max_comprimento << "\n";
        for (int i = 0; i < max_comprimento; ++i) {
            std::cout << (melhor_inicio + i);
            if (i < max_comprimento - 1) std::cout << "*";
        }
        std::cout << "\n";
    }
    
    return 0;
}

Algoritmos de Caminho Mais Curto em Grafos

Problemas que exigem a minimização da distância máxima de um nó para todos os outros (problema do centro do grafo) podem ser resolvidos utilizando o algoritmo de Dijkstra. A implementação abaixo utiliza lista de adjacência e fila de prioridade para garantir eficiência em grafos esparsos.

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using aresta = std::pair<int, int>; // {destino, peso}

std::vector<int> dijkstra(int origem, int num_vertices, const std::vector<std::vector<aresta>>& grafo) {
    std::vector<int> dist(num_vertices, INT_MAX);
    std::priority_queue<aresta, std::vector<aresta>, std::greater<aresta>> pq;
    
    dist[origem] = 0;
    pq.push({0, origem});
    
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        
        if (d > dist[u]) continue;
        
        for (const auto& [v, peso] : grafo[u]) {
            if (dist[u] + peso < dist[v]) {
                dist[v] = dist[u] + peso;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

int main() {
    int n, m;
    if (!(std::cin >> n >> m)) return 0;
    
    std::vector<std::vector<aresta>> grafo(n);
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        std::cin >> u >> v >> w;
        grafo[u - 1].push_back({v - 1, w});
        grafo[v - 1].push_back({u - 1, w});
    }
    
    int melhor_no = -1;
    int menor_max_dist = INT_MAX;
    
    for (int i = 0; i < n; ++i) {
        std::vector<int> dist = dijkstra(i, n, grafo);
        int max_dist = 0;
        bool desconectado = false;
        
        for (int d : dist) {
            if (d == INT_MAX) {
                desconectado = true;
                break;
            }
            max_dist = std::max(max_dist, d);
        }
        
        if (!desconectado && max_dist < menor_max_dist) {
            menor_max_dist = max_dist;
            melhor_no = i + 1;
        }
    }
    
    if (melhor_no == -1) {
        std::cout << "0\n";
    } else {
        std::cout << melhor_no << " " << menor_max_dist << "\n";
    }
    
    return 0;
}

Conjuntos Disjuntos (Union-Find) e Relações

Para gerenciar relações de amizade e inimizade, a estrutura de Conjuntos Disjuntos (DSU) é ideal para agrupar amigos, enquanto conjuntos hash podem armazenar conexões de inimizade. A interseção dessas estruturas determina a natureza da relação entre dois indivíduos.

#include <iostream>
#include <vector>
#include <unordered_set>

class DSU {
    std::vector<int> parent;
    std::vector<int> rank;
public:
    DSU(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        for (int i = 0; i < n; ++i) parent[i] = i;
    }
    
    int find(int i) {
        if (parent[i] == i) return i;
        return parent[i] = find(parent[i]);
    }
    
    void unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j) {
            if (rank[root_i] < rank[root_j]) parent[root_i] = root_j;
            else if (rank[root_i] > rank[root_j]) parent[root_j] = root_i;
            else {
                parent[root_j] = root_i;
                rank[root_i]++;
            }
        }
    }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    int n, m, k;
    if (!(std::cin >> n >> m >> k)) return 0;
    
    DSU dsu(n + 1);
    std::vector<std::unordered_set<int>> inimigos(n + 1);
    
    for (int i = 0; i < m; ++i) {
        int a, b, relacao;
        std::cin >> a >> b >> relacao;
        if (relacao == 1) {
            dsu.unite(a, b);
        } else {
            inimigos[a].insert(b);
            inimigos[b].insert(a);
        }
    }
    
    for (int i = 0; i < k; ++i) {
        int a, b;
        std::cin >> a >> b;
        
        bool sao_amigos = (dsu.find(a) == dsu.find(b));
        bool sao_inimigos = (inimigos[a].count(b) > 0);
        
        if (sao_amigos && sao_inimigos) {
            std::cout << "OK but...\n";
        } else if (!sao_amigos && sao_inimigos) {
            std::cout << "No way\n";
        } else if (sao_amigos && !sao_inimigos) {
            std::cout << "No problem\n";
        } else {
            std::cout << "OK\n";
        }
    }
    
    return 0;
}