C - Robô em Grade

Dada uma grade de H linhas e W colunas, com k células pré-definidas como 'R', 'D' ou 'X'. 'R' só permite movimento para a direita, 'D' só para baixo, e 'X' permite ambos os movimentos. As células restantes podem ser preenchidas com qualquer um dos três símbolos. Para cada possível preenchimento, calcule a soma dos números de caminhos de (1,1) a (H,W) módulo 998244353.

A solução envolve calcular a acessibilidade de cada célula. Para células definidas, o valor é 0 ou 1; para indefinidas, é 2/3. Multiplicando pelo número de formas de preencher as células indefinidas e utilizando inversos modulaers, podemos reoslver o problema em tempo eficiente.

// Código reescrito para ilustração
const int MAX_DIM = 5e3 + 10;
const int MOD = 998244353;
int grade[MAX_DIM][MAX_DIM], linhas, colunas, definidas;
int dp[MAX_DIM][MAX_DIM];
char entrada[5];

int exponenciacao_modular(int base, int expoente) {
    int resultado = 1;
    for (; expoente; expoente >>= 1, base = 1LL * base * base % MOD)
        if (expoente & 1) resultado = 1LL * resultado * base % MOD;
    return resultado;
}

void atualizar(int &destino, int valor) {
    destino = (1LL * destino + valor > MOD) ? destino + valor - MOD : destino + valor;
}

int main() {
    linhas = read(); colunas = read(); definidas = read();
    int i, j, x, y;
    for (i = 1; i <= linhas; i++)
        for (j = 1; j <= colunas; j++)
            grade[i][j] = -1;
    for (i = 1; i <= definidas; i++) {
        x = read(); y = read(); scanf("%s", entrada + 1);
        if (entrada[1] == 'X') grade[x][y] = 0;
        else if (entrada[1] == 'R') grade[x][y] = 1;
        else grade[x][y] = 2;
    }
    memset(dp, 0, sizeof(dp));
    dp[1][1] = 1;
    int probabilidade = 1LL * exponenciacao_modular(3, MOD - 2) * 2 % MOD;
    for (i = 1; i <= linhas; i++) {
        for (j = 1; j <= colunas; j++) {
            if (grade[i][j] == 2) atualizar(dp[i + 1][j], dp[i][j]);
            else if (grade[i][j] == 1) atualizar(dp[i][j + 1], dp[i][j]);
            else if (grade[i][j] == 0) atualizar(dp[i + 1][j], dp[i][j]), atualizar(dp[i][j + 1], dp[i][j]);
            else {
                atualizar(dp[i + 1][j], 1LL * dp[i][j] * probabilidade % MOD);
                atualizar(dp[i][j + 1], 1LL * dp[i][j] * probabilidade % MOD);
            }
        }
    }
    dp[linhas][colunas] = 1LL * dp[linhas][colunas] * exponenciacao_modular(3, linhas * colunas - definidas) % MOD;
    printf("%d\n", dp[linhas][colunas]);
    return 0;
}

D - Escolhendo Lados

Existem 2^N jogadores. Use o menor número possível de operações, onde cada operação divide todos em duas equipes, de modo que:

• Exista um inteiro n tal que para cada par 1 ≤ i < j ≤ 2^N, i e j estejam na mesma equipe exatamente n vezes.
• Exista um inteiro m tal que para cada par 1 ≤ i < j ≤ 2^N, i e j estejam em equipes diferentes exatamente m vezes.

Dado 1 ≤ N ≤ 8, forneça uma solução.

Conclusão: A resposta é 2^N - 1. A prova envolve contagem de pares e razões entre n e m.

Construção: Na i-ésima rodada, para cada j, se a contagem de bits 1 em (i AND j) for par, j vai para a equipe A; caso contrário, para B.

// Código reescrito para ilustração
#include <iostream>
using namespace std;

int contar_bits(int valor) {
    int contagem = 0;
    for (; valor; valor -= (valor & -valor)) contagem++;
    return contagem;
}

int main() {
    int n;
    cin >> n;
    int total_jogadores = 1 << n;
    cout << total_jogadores - 1 << endl;
    for (int rodada = 1; rodada < total_jogadores; rodada++) {
        for (int jogador = 0; jogador < total_jogadores; jogador++) {
            if (contar_bits(rodada & jogador) % 2 == 1) cout << "B";
            else cout << "A";
        }
        cout << endl;
    }
    return 0;
}

E - Formiga Gananciosa

No eixo numérico, existem N doces, com o i-ésimo na posição 2i e valor a_i. Inicialmente, a Formiga escolhe uma posição entre 1, 3, ..., 2N+1.

Snuke joga primeiro e pode remover qualquer doce. A Formiga, em cada turno, escolhe remover o doce com maior valor entre os dois mais próximos à esquerda e à direita.

Para cada posição inicial da Formiga, determine o valor máximo que Snuke pode obter.

A solução usa programação dinâmica com estado f[l][r][k], representando o intervalo (l, r) ainda não removido e o número k de turnos restantes para Snuke.

// Código reescrito para ilustração
#include <iostream>
#include <cstring>
using namespace std;

const int MAX_N = 410;
int n, valores[MAX_N];
int dp[MAX_N][MAX_N][MAX_N];

void maximizar(int &destino, int candidato) {
    if (candidato > destino) destino = candidato;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> valores[i];
    memset(dp, -1, sizeof(dp));
    dp[0][n + 1][(n + 1) / 2] = 0;
    for (int comprimento = n + 2; comprimento >= 3; comprimento--) {
        for (int esq = 0; esq + comprimento - 1 <= n + 1; esq++) {
            int dir = esq + comprimento - 1;
            for (int turnos = 0; turnos <= (n + 1) / 2; turnos++) {
                int valor_atual = dp[esq][dir][turnos];
                if (valor_atual < 0) continue;
                if (2 * (turnos - 1) < comprimento - 1) {
                    maximizar(dp[esq + 1][dir][turnos - 1], valor_atual + valores[esq + 1]);
                    maximizar(dp[esq][dir - 1][turnos - 1], valor_atual + valores[dir - 1]);
                }
                if (2 * turnos < comprimento - 1) {
                    if (valores[esq + 1] > valores[dir]) maximizar(dp[esq + 1][dir][turnos], valor_atual);
                    if (valores[dir - 1] > valores[esq]) maximizar(dp[esq][dir - 1][turnos], valor_atual);
                }
            }
        }
    }
    for (int posicao = 0; posicao <= n; posicao++) cout << dp[posicao][posicao + 1][0] << endl;
    return 0;
}