Cobertura de Área em Movimento Sequencial

Para resolver o problema de cobertura dinâmica, observamos que uma nuvem gerada no instante t afeta todos os períodos subsequentes [t+1, N]. A abordagem consiste em monitorar o deslocamento acumulado (deslocX, deslocY) durante a simulação. Em cada passo, verificamos se existe um momento anterior x onde a diferença entre os deslocamentos atuais e passados corresponde exatamente às coordenadas-alvo (raio, coluna). Utilizamos uma tabela hash para registrar posições visitadas e validar cobertura em tempo real.

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

map<pair<int, int>, bool> posicoes;
int N, raio, coluna;
int movX[4] = {0, 1, 0, -1};
int movY[4] = {1, 0, -1, 0};

int main() {
    cin >> N >> raio >> coluna;
    if (raio == 0 && coluna == 0) {
        for (int i = 0; i < N-1; i++) cout << '1';
        return 0;
    }
    int x = 0, y = 0;
    posicoes[{0, 0}] = true;
    for (int t = 0; t < N-1; t++) {
        char direcao;
        int indice;
        cin >> direcao;
        switch(direcao) {
            case 'E': indice = 0; break;
            case 'S': indice = 1; break;
            case 'O': indice = 2; break;
            case 'N': indice = 3; break;
        }
        x += movX[indice];
        y += movY[indice];
        cout << (posicoes.count({x - raio, y - coluna}) ? '1' : '0');
        posicoes[{x, y}] = true;
    }
}

Otimização de Palíndromos com Algoritmo KMP

A solução eficiente para minimizar operações de construção de palíndromos explora a proprieadde de que o maior sufixo palindrômico da string original determina a parte mínima a ser adicionada. Ao concatenar a string reversa com um delimitador especial e a string original (reverso + '#' + original), aplicamos o algoritmo KMP para calcular o array de prefixos. O valor final desse array indica exatamente o tamanho do maior sufixo palindrômico, permitindo construir a solução ótima com complexidade linear.

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

const int MAX = 2000010;
int n, prefix[MAX];
char original[MAX], combinado[MAX];

int main() {
    cin >> (original + 1);
    n = strlen(original + 1);
    for (int i = 1; i <= n; i++) 
        combinado[n - i + 1] = original[i];
    combinado[n + 1] = '$';
    for (int i = n + 2; i <= 2*n + 1; i++) 
        combinado[i] = original[i - n - 1];
    
    int len = 2*n + 1;
    for (int i = 2, j = 0; i <= len; i++) {
        while (j > 0 && combinado[j+1] != combinado[i])
            j = prefix[j];
        if (combinado[j+1] == combinado[i]) j++;
        prefix[i] = j;
    }
    
    int palindromoMax = prefix[len];
    for (int i = 1; i <= n; i++) 
        cout << original[i];
    for (int i = n - palindromoMax; i >= 1; i--) 
        cout << original[i];
}

Estratégia Vencedora em Adição de Arestas em Grafos

A natureza bipartida de árvores é fundamental para resolver este problema. Após colorir os vértices em dois conjuntos disjuntos (A e B) usando DFS, calculamos o número máximo de arestas possíveis entre os conjuntos que não existem na árvore original. A paridade desse valor determina o vencedor: se for ímpar, o primeiro jogador tem vantagem estratégica. Durante a execução, os jogadores alternam escolhendo arestas válidas entre os conjuntos, mantendo a propriedade bipartida do grafo.

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

vector<int> adj[105];
vector<int> particaoA, particaoB;
map<pair<int, int>, bool> existente;
vector<pair<int, int>> arestasDisponiveis;

void colorir(int no, int cor, vector<int>& grupo) {
    grupo.push_back(no);
    for (int vizinho : adj[no]) {
        if (particaoA[vizinho] == 0) {
            particaoA[vizinho] = 3 - cor;
            colorir(vizinho, 3 - cor, (cor == 1) ? particaoB : particaoA);
        }
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n-1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        existente[{min(u,v), max(u,v)}] = true;
    }
    
    particaoA.assign(n+1, 0);
    colorir(1, 1, particaoA);
    
    for (int u : particaoA) 
        for (int v : particaoB) 
            if (!existente[{min(u,v), max(u,v)}])
                arestasDisponiveis.push_back({u, v});
    
    cout << (arestasDisponiveis.size() % 2 ? "Primeiro" : "Segundo") << endl;
    // Lógica de interação omitida por simplicidade
}