Problema 1 – Caracteres distintos
Problema 2 – Comparação de bits
Problema 3 – K-ésimo menor distinto
Problema 4 – Desarranjos
Problema 5 – Tempo de espera
Problema 6 – Ponto crítico (Union-Find)
Problema 7 – Conectividade em grade
Problema 8 – Mediana das cooordenadas
Problema 9 – Soma dos divisores
Problema 10 – Caminho crescente mais longo

Problema 1 – Caracteres distintos

Código reformulado:

#include <iostream>
#include <unordered_set>
#include <string>

using namespace std;

int main() {
    string entrada;
    getline(cin, entrada);                     // lê a string completa
    
    unordered_set<char> caracteres(entrada.begin(), entrada.end()); // extrai caracteres únicos
    
    if (caracteres.size() % 2 == 1)            // quantidade ímpar?
        cout << "IGNORE HIM!" << endl;
    else
        cout << "CHAT WITH HER!" << endl;
            
    return 0;
}

Problema 2 – Comparação de bits

Código reformulado:

#include <iostream>
#include <bitset>

using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    
    int popA = bitset<32>(a).count();
    int popB = bitset<32>(b).count();
    
    if (popA > popB)
        cout << a;
    else if (popB > popA)
        cout << b;
    else
        cout << max(a, b);
    
    return 0;
}

Problema 3 – K-ésimo menor distnito

Código reformulado:

#include <iostream>
#include <set>
#include <vector>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    
    set<int> valores;                         // armazena apenas elementos distintos
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        valores.insert(x);
    }
    
    if (k <= valores.size()) {
        auto it = valores.begin();
        advance(it, k-1);                     // k-ésimo (índice 0)
        cout << *it << endl;
    } else {
        cout << "NO RESULT" << endl;
    }
    
    return 0;
}

Problema 4 – Desarranjos

Código reformulado (usando recorrrência):

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int testes;
    cin >> testes;
    
    while (testes--) {
        int n;
        cin >> n;
        
        if (n <= 8) {                         // n pequeno: recorrência exata
            long long d0 = 1, d1 = 0;         // D(0)=1, D(1)=0
            for (int i = 2; i <= n; ++i) {
                long long di = (i-1) * (d0 + d1);
                d0 = d1;
                d1 = di;
            }
            long long total = 1;              // n!
            for (int i = 2; i <= n; ++i) total *= i;
            double probabilidade = (double) d1 / total * 100.0;
            printf("%.2lf%%\n", probabilidade);
        } else {
            cout << "36.79%" << endl;
        }
    }
    return 0;
}

Problema 5 – Tempo de espera

Código reformulado:

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

using namespace std;

struct Ticket {
    int tempo;
    int id;
};

int main() {
    int n;
    cin >> n;
    vector<Ticket> pessoas(n);
    for (int i = 0; i < n; ++i) {
        cin >> pessoas[i].tempo;
        pessoas[i].id = i+1;
    }
    
    // ordena pelo tempo (menor primeiro)
    sort(pessoas.begin(), pessoas.end(), [](const Ticket &a, const Ticket &b) {
        return a.tempo < b.tempo;
    });
    
    long long somaEspera = 0;
    for (int i = 0; i < n; ++i) {
        somaEspera += (n - i) * pessoas[i].tempo;  // (n-i) pessoas esperam esse tempo
        cout << pessoas[i].id;
        if (i != n-1) cout << " ";
    }
    cout << endl;
    
    double media = somaEspera / (double) n;
    printf("%.2lf\n", media);
    
    return 0;
}

Problema 6 – Ponto crítico (Union-Find reverso)

Código reformulado:

#include <iostream>
#include <vector>

using namespace std;

struct DSU {
    vector<int> pai, tamanho;
    DSU(int n) {
        pai.resize(n+1);
        tamanho.assign(n+1, 1);
        for (int i = 1; i <= n; ++i) pai[i] = i;
    }
    int find(int x) {
        return pai[x] == x ? x : pai[x] = find(pai[x]);
    }
    void merge(int a, int b) {
        a = find(a); b = find(b);
        if (a != b) {
            pai[a] = b;
            tamanho[b] += tamanho[a];
        }
    }
    int getTamanho(int x) {
        return tamanho[find(x)];
    }
};

int main() {
    int n;
    cin >> n;
    
    vector<vector<int>> grafo(n+1);
    for (int i = 1; i <= n; ++i) {
        int k; cin >> k;
        grafo[i].resize(k);
        for (int j = 0; j < k; ++j) cin >> grafo[i][j];
    }
    
    DSU dsu(n);
    // Processa de n até 1 (ordem reversa)
    for (int v = n; v >= 1; --v) {
        for (int u : grafo[v]) {
            if (u > v) {                    // só conecta com vértices maiores
                dsu.merge(v, u);
            }
            if (dsu.getTamanho(v) > n/2) {
                cout << v << endl;
                return 0;
            }
        }
    }
    
    return 0;
}

Problema 7 – Conectividade em grade

Código reformulado:

#include <iostream>
#include <vector>
#include <set>

using namespace std;

struct UnionFind {
    vector<int> pai;
    UnionFind(int n) : pai(n+1) {
        for (int i = 1; i <= n; ++i) pai[i] = i;
    }
    int find(int x) {
        return pai[x] == x ? x : pai[x] = find(pai[x]);
    }
    void merge(int a, int b) {
        a = find(a); b = find(b);
        if (a != b) pai[a] = b;
    }
};

inline int id(int linha, int col, int m) {
    return (linha-1) * m + col;
}

int main() {
    int n, m;
    cin >> n >> m;
    
    UnionFind uf(n*m);
    set<int> colunasProcessadas;               // colunas que já receberam horizontal
    
    // Leitura das ligações verticais
    int a1, a2, b1, b2;
    while (cin >> a1 >> a2 >> b1 >> b2) {
        if (a2 != b2)                          // ligação horizontal entre colunas
            colunasProcessadas.insert(min(a2, b2));
        int u = id(a1, a2, m);
        int v = id(b1, b2, m);
        uf.merge(u, v);
    }
    
    long long resposta = 0;
    // Adiciona arestas horizontais ausentes (cada uma custa 2)
    for (int c = 1; c < m; ++c) {
        if (!colunasProcessadas.count(c)) {
            resposta += 2;
            uf.merge(id(1, c, m), id(1, c+1, m));
        }
    }
    
    // Conta componentes conexas
    set<int> componentes;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            componentes.insert(uf.find(id(i, j, m)));
        }
    }
    resposta += componentes.size() - 1;       // arestas verticais necessárias
    
    cout << resposta << endl;
    
    return 0;
}

Problema 8 – Mediana das coordenadas

Código reformulado:

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>

using namespace std;

int main() {
    int n;
    cin >> n;
    
    vector<int> coords(n);
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x >> coords[i];          // x descartado, y armazenado
    }
    
    // nth_element coloca o k-ésimo menor na posição k (0‑based)
    nth_element(coords.begin(), coords.begin() + n/2, coords.end());
    int mediana = coords[n/2];
    
    long long soma = 0;
    for (int y : coords) {
        soma += abs(y - mediana);
    }
    
    cout << " " << soma << endl;        // mantém o espaço inicial do output original
    
    return 0;
}

Problema 9 – Soma dos divisores

Código reformulado:

#include <iostream>

using namespace std;

int main() {
    long long n;
    cin >> n;
    
    long long total = 0;
    for (long long i = 1; i <= n; ++i) {
        total += n / i;                    // quantidade de múltiplos de i entre 1 e n
    }
    
    cout << total << endl;
    
    return 0;
}

Problema 10 – Caminho crescente mais longo

Código reformulado:

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

using namespace std;

const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};

int dfs(int x, int y, const vector<vector<int>>& mat, vector<vector<int>>& memo) {
    if (memo[x][y] != 0) return memo[x][y];
    
    int melhor = 1;
    for (int dir = 0; dir < 4; ++dir) {
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        if (nx >= 0 && nx < mat.size() && ny >= 0 && ny < mat[0].size() && mat[nx][ny] > mat[x][y]) {
            melhor = max(melhor, 1 + dfs(nx, ny, mat, memo));
        }
    }
    return memo[x][y] = melhor;
}

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<vector<int>> grade(n, vector<int>(m));
    for (auto& linha : grade)
        for (int& valor : linha)
            cin >> valor;
    
    vector<vector<int>> memoria(n, vector<int>(m, 0));
    int maiorCaminho = 0;
    
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            maiorCaminho = max(maiorCaminho, dfs(i, j, grade, memoria));
    
    cout << maiorCaminho << endl;
    
    return 0;
}