Soluções do Concurso Codeforces Hello 2024

A. Troca de Carteiras

Este problema consiste em determinar o vencdeor de um jogo simples. Dado dois inteiros a e b representando o dinheiro de Alice e Bob respectivamente, Alice vence se a soma for ímpar, caso contrário Bob vence.

#include <iostream>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int casos;
    cin >> casos;

    while (casos--) {
        int valorAlice, valorBob;
        cin >> valorAlice >> valorBob;
        
        int total = valorAlice + valorBob;
        if (total % 2 != 0) {
            cout << "Alice\n";
        } else {
            cout << "Bob\n";
        }
    }

    return 0;
}

B. Divisão Mais-Menos

Dada uma string composta pelos caracteres '+' e '-', devemos minimizar o tamanho final da sequência após remover pares adjacentes de sinais opostos até não ser mais possível.

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int casos;
    cin >> casos;

    while (casos--) {
        int comprimento;
        string sequencia;
        cin >> comprimento >> sequencia;

        vector<char> pilha;
        for (char caractere : sequencia) {
            if (!pilha.empty() && ((pilha.back() == '+' && caractere == '-') || 
                                   (pilha.back() == '-' && caractere == '+'))) {
                pilha.pop_back();
            } else {
                pilha.push_back(caractere);
            }
        }
        
        cout << pilha.size() << "\n";
    }

    return 0;
}

C. Agrupamento Crescente

Dada uma sequência de números, devemos dividir em dois subsequências crescentes minimizanod o número total de elementos que violam a condição de não decrescimento.

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int casos;
    cin >> casos;

    while (casos--) {
        int n;
        cin >> n;

        vector<long long> elementos(n);
        for (int i = 0; i < n; ++i) {
            cin >> elementos[i];
        }

        const long long INFINITO = 1e18;
        vector<long long> grupo1 = {INFINITO};
        vector<long long> grupo2 = {INFINITO};

        for (long long valor : elementos) {
            long long topo1 = grupo1.back();
            long long topo2 = grupo2.back();

            if (valor <= topo1 && valor <= topo2) {
                if (topo1 <= topo2) {
                    grupo1.push_back(valor);
                } else {
                    grupo2.push_back(valor);
                }
            } else if (valor > topo1 && valor > topo2) {
                if (topo1 <= topo2) {
                    grupo1.push_back(valor);
                } else {
                    grupo2.push_back(valor);
                }
            } else if (valor <= topo1) {
                grupo1.push_back(valor);
            } else {
                grupo2.push_back(valor);
            }
        }

        long long contagem = 0;
        for (size_t i = 1; i + 1 < grupo1.size(); ++i) {
            if (grupo1[i] < grupo1[i+1]) contagem++;
        }
        for (size_t i = 1; i + 1 < grupo2.size(); ++i) {
            if (grupo2[i] < grupo2[i+1]) contagem++;
        }

        cout << contagem << "\n";
    }

    return 0;
}

D. Árvore 01

Determinar se uma dada sequência de números pode representar os valores de uma árvore binária onde a raiz vale 0 e cada pai vale exatamente um a mais que seus filhos.

#include <iostream>
#include <vector>
#include <map>
#include <list>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int casos;
    cin >> casos;

    while (casos--) {
        int nos;
        cin >> nos;

        vector<int> valor(nos);
        map<int, vector<int>> indicesPorValor;

        for (int i = 0; i < nos; ++i) {
            cin >> valor[i];
            indicesPorValor[valor[i]].push_back(i);
        }

        if (indicesPorValor[0].size() != 1) {
            cout << "NO\n";
            continue;
        }

        list<int> listaOrdenada(nos);
        iota(listaOrdenada.begin(), listaOrdenada.end(), 0);

        vector<list<int>::iterator> iteradores(nos);
        auto itLista = listaOrdenada.begin();
        for (int i = 0; i < nos; ++i, ++itLista) {
            iteradores[i] = itLista;
        }

        bool possivel = true;
        for (int valorAtual = nos - 1; valorAtual > 0 && possivel; --valorAtual) {
            for (int noAtual : indicesPorValor[valorAtual]) {
                auto it = iteradores[noAtual];
                auto proximo = next(it);
                auto anterior = prev(it);

                bool vizinhoValido = false;
                if (proximo != listaOrdenada.end() && valor[*proximo] == valorAtual - 1) {
                    vizinhoValido = true;
                }
                if (it != listaOrdenada.begin() && valor[*anterior] == valorAtual - 1) {
                    vizinhoValido = true;
                }

                if (!vizinhoValido) {
                    possivel = false;
                    break;
                }

                listaOrdenada.erase(it);
            }
        }

        if (possivel) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }

    return 0;
}