C - Soma de Produtos

Problema clássico de otimização da ordem de somatórios usando identidades algébricas.

Dada a igualadde:

#include <iostream>
#include <vector>

using namespace std;

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

    long long soma = 0;
    long long soma_quadrados = 0;
    for (int v : valores) {
        soma += v;
        soma_quadrados += static_cast<long long>(v) * v;
    }

    long long resultado = (soma * soma - soma_quadrados) / 2;
    cout << resultado << endl;

    return 0;
}

D - Rota de Fuga

Utiliza-se uma Busca em Largura (BFS) a partir de todas as saídas para determinar a direção ótima para cada célula livre.

Primeiro, enfileiram-se todas as células marcadas como 'E' (saída). Para cada célula visitada, seus vizinhos adjacentes recebem a direção de volta (por exemplo, 'v' para cima se a vizinha está acima). A BFS propaga as distâncias e grava a direção correspondente.

#include <iostream>
#include <vector>
#include <queue>
#include <utility>

using namespace std;

int main() {
    int altura, largura;
    cin >> altura >> largura;

    vector<string> grid(altura);
    for (int i = 0; i < altura; ++i) {
        cin >> grid[i];
    }

    vector<string> resposta(altura, string(largura, '?'));
    vector<vector<int>> dist(altura, vector<int>(largura, -1));
    queue<pair<int, int>> fila;

    // Direções: cima, baixo, esquerda, direita
    int dr[] = {-1, 1, 0, 0};
    int dc[] = {0, 0, -1, 1};
    char direcao[] = {'v', '^', '>', '<'};

    // Inicializa a BFS a partir das saídas
    for (int r = 0; r < altura; ++r) {
        for (int c = 0; c < largura; ++c) {
            if (grid[r][c] == 'E') {
                dist[r][c] = 0;
                fila.push({r, c});
            }
        }
    }

    while (!fila.empty()) {
        auto [r, c] = fila.front();
        fila.pop();

        for (int d = 0; d < 4; ++d) {
            int nr = r + dr[d];
            int nc = c + dc[d];

            if (nr >= 0 && nr < altura && nc >= 0 && nc < largura &&
                grid[nr][nc] == '.' && dist[nr][nc] == -1) {
                dist[nr][nc] = dist[r][c] + 1;
                resposta[nr][nc] = direcao[d];
                fila.push({nr, nc});
            }
        }
    }

    // Monta a saída final
    for (int r = 0; r < altura; ++r) {
        for (int c = 0; c < largura; ++c) {
            if (grid[r][c] == '.') {
                cout << resposta[r][c];
            } else {
                cout << grid[r][c];
            }
        }
        cout << endl;
    }

    return 0;
}

E - Fileira de Frutas

Problema de contagem combinatória com restrições de ordem. A solução envolve pré-calcular fatoriais e seus inversos modulo 998244353.

A estratégia consiste em iterar sobre a posição possível da primeira uva (índice \(i\)). Antes dessa posição, as frutas são laranjas, maçãs e bananas, com a condição de que todas as maçãs venham entes das bananas. Depois da posição, restam bananas e as demais uvas.

A contagem para uma posição \(i\) é dada por:

#include <iostream>
#include <vector>

using namespace std;

const int MOD = 998244353;
const int MAX_N = 4000000;

long long fatorial[MAX_N + 1];
long long inv_fatorial[MAX_N + 1];

long long potencia(long long base, long long expoente) {
    long long resultado = 1;
    while (expoente > 0) {
        if (expoente % 2 == 1) {
            resultado = (resultado * base) % MOD;
        }
        base = (base * base) % MOD;
        expoente /= 2;
    }
    return resultado;
}

void pre_calcular() {
    fatorial[0] = 1;
    for (int i = 1; i <= MAX_N; ++i) {
        fatorial[i] = (fatorial[i - 1] * i) % MOD;
    }
    inv_fatorial[MAX_N] = potencia(fatorial[MAX_N], MOD - 2);
    for (int i = MAX_N - 1; i >= 0; --i) {
        inv_fatorial[i] = (inv_fatorial[i + 1] * (i + 1)) % MOD;
    }
}

long long combinacao(long long n, long long k) {
    if (k < 0 || k > n) return 0;
    return (fatorial[n] * inv_fatorial[k] % MOD) * inv_fatorial[n - k] % MOD;
}

int main() {
    pre_calcular();

    long long a, b, c, d;
    cin >> a >> b >> c >> d;

    long long n = a + b + c + d;
    long long total = 0;

    // i é a posição (1-indexada) da primeira uva
    for (long long i = a + b + 1; i <= n - d + 1; ++i) {
        long long bananas_antes = i - 1 - a - b;
        if (bananas_antes < 0) continue;
        long long termo = combinacao(i - 1, b) * combinacao(n - i, c - bananas_antes) % MOD;
        total = (total + termo) % MOD;
    }

    cout << total << endl;

    return 0;
}