A. Cobirndo com Água

Aálise

O comportamento da água segue uma lógica semelhante à de jogos de sandbox: quando uma célula vazia possui água em ambos os lados, ela é preenchida automaticamente. Com a operação 2, é possível criar um gerador de água infinita. Portanto, ao idantificar três ou mais células vazias consecutivas, basta duas aplicações da operação 1 para estabelecer esse fluxo contínuo e preencher tudo. Caso contrário, sem sequências de tamanho 3 ou superior, cada célula deve ser preenchida manualmente.

Implementação

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int casos;
    cin >> casos;
    while (casos--) {
        int tamanho;
        string faixa;
        cin >> tamanho >> faixa;
        
        faixa = "#" + faixa + "#";
        int sequencia = 0, total = 0;
        
        for (int i = 0; i < tamanho + 2; i++) {
            if (faixa[i] == '.') {
                sequencia++;
                if (sequencia >= 3) {
                    total = 2;
                    break;
                }
            } else {
                if (total != 2) total += sequencia;
                sequencia = 0;
            }
        }
        
        cout << total << '\n';
    }
    return 0;
}

B. Operações da Laura

Análise

Para manter um valor intacto, é preciso que os outros dois se igualem. Observando as operações: ao reduzir a diferença entre dois números, eventualmente precisamos que essa diferença seja nula. O processo envolve equalizar parcialmente e verificar se a diferença restante é divisível por 2, garantindo paridade para que ambos cheguem ao mesmo valor simultaneamente.

Implementação

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int consultas;
    cin >> consultas;
    while (consultas--) {
        long long x, y, z;
        cin >> x >> y >> z;
        
        cout << (abs(y - z) % 2 == 0) << ' ';
        cout << (abs(x - z) % 2 == 0) << ' ';
        cout << (abs(x - y) % 2 == 0) << '\n';
    }
    return 0;
}

C. Árvore Binária do Anji

Análise

O problema exige encontrar o menor número de alterações para que um caminho válido exista da raiz até alguma folha. Cada nó armazena filho esquerdo, filho direito e a direção atual indicada. A estratégia consiste em explorar recursivamente, acumulando o custo de mudanças necessárias quando a direção não corresponde ao caminho desejado.

Implementação

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

struct No {
    int esq = 0;
    int dir = 0;
    char sentido = 'U';
};

int melhor = INT_MAX;
vector<No> arvore;

void buscar(int atual, int acumulado) {
    if (atual == 0) return;
    
    if (arvore[atual].esq == 0 && arvore[atual].dir == 0) {
        melhor = min(melhor, acumulado);
        return;
    }
    
    int filhoEsq = arvore[atual].esq;
    int filhoDir = arvore[atual].dir;
    char orientacao = arvore[atual].sentido;
    
    if (orientacao == 'L') {
        buscar(filhoEsq, acumulado);
        arvore[atual].sentido = 'R';
        buscar(filhoDir, acumulado + 1);
        arvore[atual].sentido = 'L';
    } else if (orientacao == 'R') {
        buscar(filhoDir, acumulado);
        arvore[atual].sentido = 'L';
        buscar(filhoEsq, acumulado + 1);
        arvore[atual].sentido = 'R';
    } else {
        arvore[atual].sentido = 'L';
        buscar(filhoEsq, acumulado + 1);
        arvore[atual].sentido = 'R';
        buscar(filhoDir, acumulado + 1);
        arvore[atual].sentido = 'U';
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int instancias;
    cin >> instancias;
    
    while (instancias--) {
        int n;
        string direcoes;
        cin >> n >> direcoes;
        
        direcoes = " " + direcoes;
        arvore.assign(n + 1, No());
        melhor = INT_MAX;
        
        for (int i = 1; i <= n; i++) {
            int l, r;
            cin >> l >> r;
            arvore[i].esq = l;
            arvore[i].dir = r;
            arvore[i].sentido = direcoes[i];
        }
        
        buscar(1, 0);
        cout << melhor << '\n';
    }
    return 0;
}