Problema A: Fileira

Você recebe uma fileira com n cadeiras. Uma disposição de pessoas é chamada de "máxima" se duas condições forem atendidas:

1. Nenhuma pessoa tem vizinhos adjacentes sentados.
2. Não é possível sentar mais uma pessoa sem violar a primeira regra.

A disposição é dada como uma string de zeros e uns (0 indica cadeira vazia, 1 indica ocupada). O objetivo é determinar se a disposição é "máxima". Note que as cadeiras primeiro e último não são adjacentes (exceto se n ≠ 2).

Entrada: A primeira linha contém um inteiro n (1 ≤ n ≤ 1000). A próxima linha contém uma string de n caracteres, cada um zero ou um.

Saída: Imprima "Yes" se a disposição for máxima, caso contrário "No".

Exemplos:

Entrada: 3 / 101
Saída: Yes

Entrada: 4 / 1011
Saída: No

Entrada: 5 / 10001
Saída: No

Nota: No primeiro exemplo, a disposição é máxima. No segundo, a pessoa na cadeira 3 tem um vizinho à direita. No terceiro, é possível sentar outra pessoa na cadeira 3.

Implementação em C++

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

bool verificarMaximalidade(int totalCadeiras, const string& arranjo) {
    if (totalCadeiras == 1) {
        return arranjo[0] == '1';
    }
    // Verificar cadeiras ocupadas adjacentes
    for (int i = 0; i < totalCadeiras - 1; ++i) {
        if (arranjo[i] == '1' && arranjo[i+1] == '1') {
            return false;
        }
    }
    // Verificar sequências de cadeiras vazias inválidas
    for (int i = 0; i < totalCadeiras; ++i) {
        if (arranjo[i] == '0') {
            if (i == 0 && i + 1 < totalCadeiras && arranjo[i+1] == '0') {
                return false;
            }
            if (i == totalCadeiras - 1 && i - 1 >= 0 && arranjo[i-1] == '0') {
                return false;
            }
            if (i + 2 < totalCadeiras && arranjo[i] == '0' && arranjo[i+1] == '0' && arranjo[i+2] == '0') {
                return false;
            }
        }
    }
    return true;
}

int main() {
    int totalCadeiras;
    string arranjo;
    cin >> totalCadeiras >> arranjo;
    if (verificarMaximalidade(totalCadeiras, arranjo)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

Problema B: Ônibus dos Personagens

Em um ônibus, existem n fileiras de assentos, cada uma com 2 assentos. A largura dos assentos na i-ésima fileira é w_i centímetros, e todos os w_i são distintos.

Inicialmente, o ônibus está vazio. Em cada uma das 2n paradas, um passageiro entra. Há dois tipos de passageiros:

• Introvertido: Escolhe uma fileira onde ambos os assentos estão vazios. Entre essas fileiras, escolhe a de menor largura e senta em um dos assentos.
• Extrovertido: Escolhe uma fileira onde exatamente um assento está ocupado (por um introvertido). Entre essas fileiras, escolhe a de maior largura e senta no lugar vago.

Dada a largura dos assentos e a ordem de entrada dos passageiros, determine qual fileira cada passageiro ocupará.

Entrada: A primeira linha contém n (1 ≤ n ≤ 200000). A segunda linha contém n inteiros w_1 a w_n. A terceria linha contém uma string de tamanho 2n com '0' para introvretido e '1' para extrovertido.

Saída: Imprima 2n inteiros representando as fileiras dos passageiros na ordem de entrada.

Exemplos:

Entrada: 2 / 3 1 / 0011
Saída: 2 1 1 2

Entrada: 6 / 10 8 9 11 13 5 / 010010011101
Saída: 6 6 2 3 3 1 4 4 1 2 5 5

Nota: No primeiro exemplo, o primeiro introvertido escolhe a fileira 2 por ter a menor largura, e assim por diante.

Implementação em C++

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

struct Fileira {
    int identificador;
    int largura;
};

bool compararLargura(const Fileira& a, const Fileira& b) {
    return a.largura < b.largura;
}

struct ComparadorPorLargura {
    bool operator()(const Fileira& a, const Fileira& b) {
        return a.largura < b.largura; // Para fila de prioridade máxima
    }
};

int main() {
    int numFileiras;
    cin >> numFileiras;
    vector<Fileira> fileiras(numFileiras);
    for (int i = 0; i < numFileiras; ++i) {
        cin >> fileiras[i].largura;
        fileiras[i].identificador = i + 1;
    }
    string ordemEntrada;
    cin >> ordemEntrada;
    sort(fileiras.begin(), fileiras.end(), compararLargura);
    priority_queue<Fileira, vector<Fileira>, ComparadorPorLargura> filaPrioridade;
    vector<int> resultado;
    int indiceIntrovertido = 0;
    for (char tipo : ordemEntrada) {
        if (tipo == '0') { // Introvertido
            resultado.push_back(fileiras[indiceIntrovertido].identificador);
            filaPrioridade.push(fileiras[indiceIntrovertido]);
            indiceIntrovertido++;
        } else { // Extrovertido
            Fileira escolhida = filaPrioridade.top();
            filaPrioridade.pop();
            resultado.push_back(escolhida.identificador);
        }
    }
    for (size_t i = 0; i < resultado.size(); ++i) {
        if (i > 0) cout << " ";
        cout << resultado[i];
    }
    cout << endl;
    return 0;
}

Problema C: Corte-os Todos!

Dada uma árvore com n vértices, determine o número máximo de arestas que podem ser removidas de modo que todos os componentes conectados restantes tenham tamanho par.

Entrada: A primeira linha contém n (1 ≤ n ≤ 10^5). As próximas n-1 linhas contêm dois inteiros u e v representando arestas.

Saída: Imprima o número máximo k de arestas removíveis, ou -1 se for impossível.

Exemplos:

Entrada: 4 / 2 4 / 4 1 / 3 1
Saída: 1

Entrada: 3 / 1 2 / 1 3
Saída: -1

Entrada: 10 / ... (exemplo completo)
Saída: 4

Nota: Se n for ímpar, é impossível. Caso contrário, use DFS para contar subárvores.

Implementação em C++

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

const int MAXIMO = 100005;
vector<int> grafo[MAXIMO];
int tamanhoSubarvore[MAXIMO];
int arestasRemovidas;

void dfs(int no, int pai) {
    tamanhoSubarvore[no] = 1;
    for (int vizinho : grafo[no]) {
        if (vizinho != pai) {
            dfs(vizinho, no);
            if (tamanhoSubarvore[vizinho] % 2 == 0) {
                arestasRemovidas++;
            } else {
                tamanhoSubarvore[no] += tamanhoSubarvore[vizinho];
            }
        }
    }
}

int main() {
    int numVertices;
    cin >> numVertices;
    for (int i = 0; i < numVertices - 1; ++i) {
        int u, v;
        cin >> u >> v;
        grafo[u].push_back(v);
        grafo[v].push_back(u);
    }
    if (numVertices % 2 != 0) {
        cout << -1 << endl;
    } else {
        arestasRemovidas = 0;
        dfs(1, 0);
        cout << arestasRemovidas << endl;
    }
    return 0;
}