Problema 1: Avaliação de Polinômios com Atualizações em Intervalos
Este problema consiste em processar um conjunto de N polinômios, realizar M operações de atualização em seus coeficientes e, finalmente, avaliar cada polinômio em um ponto específico (x=233), retornando o resultado modulo 10^7 + 9.
Inicialmente, são fornecidos N polinômios. Para cada polinômio, é dado seu grau t_i e seus t_i + 1 coeficientes, do termo de grau zero ao termo de grau t_i.
Posteriormente, M operações de modificação são executadas. Cada modificação afeta um intervalo de polinômios, do L-ésimo ao R-ésimo (inclusive). Para cada polinômio nesse intervalo, os coeficientes de grau 0 até P são alterados. Um valor V é lido; se a modificação for de índice par, V é multiplicado por -1. Este valor ajustado é então adicionado aos coeficientes correspondentes.
Para lidar com as atualizações de intervalo de forma eficiente, uma técnica de diferença finita é empregada. Em vez de aplicar as modificações diretamente a cada um dos N polinômios, registramos as mudanças acumuladas. Um array modificacoes\_acumuladas\[i\]\[j\] armazena a alteração líquida no coeficiente de grau j para o polinômio i.
Quando uma atualização é definida para o intervalo [L, R] para os coeficientes até o grau P, e com valor V_ajustado, nós incrementamos modificacoes\_acumuladas\[L-1\]\[j\] por V_ajustado e decrementamos modificacoes\_acumuladas\[R\]\[j\] por V_ajustado para cada j de 0 a P. Este método permite que, em uma segunda passagem, as mudanças sejam propagadas corretamente para cada polinômio.
Após todas as modificações, cada polinômio i é avaliado em x=233. O coeficiente efetivo para o termo de grau j do polinômio i é a soma de seu coeficiente original coeficientes\_originais\[i\]\[j\] e a modificação acumulada modificacoes\_acumuladas\[i\]\[j\]. A avaliação é realizada iterativamente, calculando 233^j e multiplicando pelo coeficiente efetivo, somando ao resultado total, tudo modulo 10^7 + 9.
#include <iostream>
#include <vector>
#include <numeric>
const int MODULO_VALOR = 1e7 + 9; // Valor do módulo para todas as operações
const int MAX_GRAU_AVALIACAO = 500; // Limite superior para o grau de avaliação do polinômio
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int num_polinomios, dimensao_dummy, num_modificacoes;
std::cin >> num_polinomios >> dimensao_dummy >> num_modificacoes; // "dimensao_dummy" não é utilizada na lógica
// Armazena os coeficientes originais de cada polinômio
// coeficientes_originais[i][j] é o coeficiente do termo de grau j para o polinômio i
std::vector<std::vector<long long>> coeficientes_originais(num_polinomios, std::vector<long long>(MAX_GRAU_AVALIACAO + 1, 0));
// Armazena o grau máximo de cada polinômio
std::vector<int> graus_polinomios(num_polinomios);
for (int i = 0; i < num_polinomios; ++i) {
std::cin >> graus_polinomios[i];
for (int j = 0; j <= graus_polinomios[i]; ++j) {
std::cin >> coeficientes_originais[i][j];
}
}
// Armazena as diferenças para as atualizações de intervalo
// modificacoes_acumuladas[i][j] é a mudança líquida no coeficiente j para o polinômio i
std::vector<std::vector<long long>> modificacoes_acumuladas(num_polinomios + 1, std::vector<long long>(MAX_GRAU_AVALIACAO + 1, 0));
for (int k = 0; k < num_modificacoes; ++k) {
int grau_max_afetado, indice_inicio, indice_fim;
std::cin >> grau_max_afetado >> indice_inicio >> indice_fim;
for (int j = 0; j <= grau_max_afetado; ++j) {
long long valor_modificacao;
std::cin >> valor_modificacao;
// A regra específica do problema: alternar o sinal da modificação
if (k % 2 == 0) {
valor_modificacao = (MODULO_VALOR - valor_modificacao) % MODULO_VALOR; // Equivalente a -valor_modificacao
}
// Aplicar a técnica de array de diferenças
modificacoes_acumuladas[indice_inicio - 1][j] = (modificacoes_acumuladas[indice_inicio - 1][j] + valor_modificacao) % MODULO_VALOR;
modificacoes_acumuladas[indice_fim][j] = (modificacoes_acumuladas[indice_fim][j] - valor_modificacao + MODULO_VALOR) % MODULO_VALOR;
}
}
// Calcular o valor de cada polinômio f(233)
for (int i = 0; i < num_polinomios; ++i) {
long long resultado_polinomio = 0;
long long base_potencia = 1; // Representa 233^j
for (int j = 0; j <= MAX_GRAU_AVALIACAO; ++j) {
// Propagar as modificações acumuladas para o polinômio atual
// Este passo precisa ser feito antes de usar modificacoes_acumuladas[i][j]
if (i > 0) {
modificacoes_acumuladas[i][j] = (modificacoes_acumuladas[i][j] + modificacoes_acumuladas[i - 1][j]) % MODULO_VALOR;
}
// Coeficiente final para o termo de grau j
long long coeficiente_efetivo = (coeficientes_originais[i][j] + modificacoes_acumuladas[i][j]) % MODULO_VALOR;
// Adicionar (coeficiente_efetivo * 233^j) ao resultado
resultado_polinomio = (resultado_polinomio + (coeficiente_efetivo * base_potencia) % MODULO_VALOR) % MODULO_VALOR;
// Preparar a próxima potência de 233
base_potencia = (base_potencia * 233) % MODULO_VALOR;
}
std::cout << resultado_polinomio << (i == num_polinomios - 1 ? "" : " ");
}
std::cout << std::endl;
return 0;
}
Problema 2: Encontrar a Soma Mínima de uma Subsequência Contígua
Dada uma sequência de números inteiros, que podem ser positivos ou negativos, o objetivo é determinar a soma mínima possível de qualquer subsequência contígua não vazia. Este problema é uma variação do algoritmo de Kadane, que tipicamente busca a soma máxima de uma subsequência.
Para encontrar a soma mínima, iteramos pela sequência, mantendo duas variáveis principais: soma\_atual\_minima e min\_soma\_global. soma\_atual\_minima acumula a soma da subsequência contígua terminando no elemento atual. Se soma\_atual\_minima se tornar positiva, significa que começar uma nova subsequência a partir do próximo elemento potencialmente gerará uma soma menor (ou igual a zero, que é o ponto de reinício para buscar o mínimo). Portanto, resetamos soma\_atual\_minima para 0 se ela se tornar positiva, assegurando que estamos sempre considerando as menores somas possíveis.
min\_soma\_global armazena o menor valor encontrado para soma\_atual\_minima em qualquer ponto da iteração, garantindo que a subsequência mais negativa (ou menos positiva) seja capturada. A condição "não pode ser uma subsequência vazia" é intrinsecamente tratada pelo fato de que min\_soma\_global é inicializada com um valor muito grande ou com o primeiro elemento, e sempre atualizada com base em somas de subsequências que incluem pelo menos um elemento.
#include <iostream>
#include <vector>
#include <algorithm> // Para std::min
#include <limits> // Para std::numeric_limits
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int tamanho_sequencia;
std::cin >> tamanho_sequencia;
long long soma_atual_minima = 0;
// Inicializar min_soma_global com um valor muito alto para garantir que qualquer soma real seja menor.
// Ou, como no exemplo original, com um valor grande como 1e7, assumindo os limites do problema.
long long min_soma_global = std::numeric_limits<long long>::max();
// Se a sequência consistir apenas de números positivos, a soma mínima será o menor número positivo.
// Se todos forem negativos, a soma mínima será a soma de todos os negativos.
// A lógica abaixo lida com ambos os casos e misturas.
bool todos_positivos = true; // Flag para verificar se todos os números são positivos
long long menor_elemento_positivo = std::numeric_limits<long long>::max();
for (int i = 0; i < tamanho_sequencia; ++i) {
long long elemento;
std::cin >> elemento;
if (elemento < 0) {
todos_positivos = false;
} else {
menor_elemento_positivo = std::min(menor_elemento_positivo, elemento);
}
soma_atual_minima += elemento;
min_soma_global = std::min(min_soma_global, soma_atual_minima);
// Se a soma atual se tornar positiva, é melhor "recomeçar" a subsequência a partir de 0
// para buscar um mínimo ainda menor, a menos que o próprio elemento atual seja o menor.
// Se a soma_atual_minima for 0, isso significa que a subsequência não contribui negativamente
// e um novo segmento pode ser iniciado.
soma_atual_minima = std::min(0LL, soma_atual_minima);
}
// Caso especial: se todos os números são positivos, o algoritmo de Kadane para mínimo pode retornar 0
// se houver um caso onde soma_atual_minima é reiniciada para 0.
// No entanto, o problema exige uma subsequência *não vazia*.
// Se todos os números são positivos, a subsequência de soma mínima é o menor número individual.
if (todos_positivos) {
std::cout << menor_elemento_positivo << std::endl;
} else {
std::cout << min_soma_global << std::endl;
}
return 0;
}
Problema 3: Tempo de Encontro em um Mapa com Expansão de Obstáculos
Este problema apresenta um mapa em grade de dimensões N x M. Dois agentes, A e B, começam em posições específicas (x1, y1) e (x2, y2), respectivamente. Adicionalmente, existem K fontes de água no mapa. A cada segundo, a água se expande para as quatro direções ortogonais (cima, baixo, esquerda, direita) a partir de todas as células que já estão com água. Os agentes A e B também se movem um passo por segundo, podendo ir para qualquer uma das quatro direções ortogonais, contanto que a célula de destino não esteja inundada pela água no momento da chegada.
O objetivo é determinar o tempo mínimo, em segundos, para que os agentes A e B se encontrem. Se for impossível para eles se encontrarem, o programa deve retornar -1.
A solução para este problema envolve uma busca em largura (BFS) multi-fonte e por camadas. É necessário simular a expansão da água e o movimento de A e B simulteneamente, segundo a segundo. Utilizaremos três filas (deques) para gerenciar o BFS: uma para a expansão da água, uma para o agente A e outra para o agente B.
Um mapa de grade (mapa\_status) será usado para rastrear o estado de cada célula: 0 para vazio, 1 para células visitadas por A, 2 para células visitadas por B, e 3 para células inunddaas pela água. A ordem das operações em cada segundo é crucial: primeiro, todas as células que serão inundadas no próximo segundo são determinadas; em seguida, A se move para as células acessíveis; finalmente, B se move para as células acessíveis. Se A e B ocuparem a mesma célula em qualquer ponto (ou A alcançar uma célula marcada por B, ou vice-versa), um encontro é registrado.
#include <iostream>
#include <vector>
#include <deque>
#include <utility> // Para std::pair
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int num_testes;
std::cin >> num_testes;
while (num_testes--) {
int linhas, colunas;
std::cin >> linhas >> colunas;
// mapa_status: 0=vazio, 1=A visitou, 2=B visitou, 3=água
std::vector<std::vector<int>> mapa_status(linhas + 1, std::vector<int>(colunas + 1, 0));
std::deque<std::pair<int, int>> fila_agua; // Fila para a expansão da água
std::deque<std::pair<int, int>> fila_agenteA; // Fila para o Agente A
std::deque<std::pair<int, int>> fila_agenteB; // Fila para o Agente B
int pos_A_x, pos_A_y, pos_B_x, pos_B_y;
std::cin >> pos_A_x >> pos_A_y >> pos_B_x >> pos_B_y;
fila_agenteA.push_back({pos_A_x, pos_A_y});
fila_agenteB.push_back({pos_B_x, pos_B_y});
mapa_status[pos_A_x][pos_A_y] = 1;
mapa_status[pos_B_x][pos_B_y] = 2;
int num_fontes_agua;
std::cin >> num_fontes_agua;
for (int i = 0; i < num_fontes_agua; ++i) {
int x_fonte, y_fonte;
std::cin >> x_fonte >> y_fonte;
mapa_status[x_fonte][y_fonte] = 3; // Marcar como água
fila_agua.push_back({x_fonte, y_fonte});
}
// Vetores de direção para movimentos ortogonais
std::vector<std::vector<int>> direcoes = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int tempo_passado = 0;
int tempo_encontro = -1;
bool encontro_ocorre = false;
// Continuar enquanto houver movimento possível para A ou B e nenhum encontro ocorreu
while ((!fila_agenteA.empty() || !fila_agenteB.empty()) && !encontro_ocorre) {
tempo_passado += 1; // Incrementa o tempo a cada "camada" do BFS
// 1. Expandir a água
int tamanho_fila_agua_atual = fila_agua.size();
for (int i = 0; i < tamanho_fila_agua_atual; ++i) {
std::pair<int, int> celula_agua = fila_agua.front();
fila_agua.pop_front();
for (int d = 0; d < 4; ++d) {
int prox_x = celula_agua.first + direcoes[d][0];
int prox_y = celula_agua.second + direcoes[d][1];
// Verificar limites do mapa e se a célula já é água
if (prox_x >= 1 && prox_x <= linhas && prox_y >= 1 && prox_y <= colunas && mapa_status[prox_x][prox_y] != 3) {
mapa_status[prox_x][prox_y] = 3; // Marcar como água
fila_agua.push_back({prox_x, prox_y});
}
}
}
// 2. Mover o Agente A
int tamanho_fila_agenteA_atual = fila_agenteA.size();
for (int i = 0; i < tamanho_fila_agenteA_atual; ++i) {
std::pair<int, int> celula_A = fila_agenteA.front();
fila_agenteA.pop_front();
for (int d = 0; d < 4; ++d) {
int prox_x = celula_A.first + direcoes[d][0];
int prox_y = celula_A.second + direcoes[d][1];
// Verificar limites do mapa, se não é água e se A já não visitou nesta camada
if (prox_x >= 1 && prox_x <= linhas && prox_y >= 1 && prox_y <= colunas && mapa_status[prox_x][prox_y] != 3 && mapa_status[prox_x][prox_y] != 1) {
if (mapa_status[prox_x][prox_y] == 2) { // A encontrou B
encontro_ocorre = true;
if (tempo_encontro == -1) tempo_encontro = tempo_passado;
}
if (mapa_status[prox_x][prox_y] == 0) { // Célula vazia, A pode mover
mapa_status[prox_x][prox_y] = 1;
fila_agenteA.push_back({prox_x, prox_y});
}
}
}
}
// 3. Mover o Agente B
int tamanho_fila_agenteB_atual = fila_agenteB.size();
for (int i = 0; i < tamanho_fila_agenteB_atual; ++i) {
std::pair<int, int> celula_B = fila_agenteB.front();
fila_agenteB.pop_front();
for (int d = 0; d < 4; ++d) {
int prox_x = celula_B.first + direcoes[d][0];
int prox_y = celula_B.second + direcoes[d][1];
// Verificar limites do mapa, se não é água e se B já não visitou nesta camada
if (prox_x >= 1 && prox_x <= linhas && prox_y >= 1 && prox_y <= colunas && mapa_status[prox_x][prox_y] != 3 && mapa_status[prox_x][prox_y] != 2) {
if (mapa_status[prox_x][prox_y] == 1) { // B encontrou A
encontro_ocorre = true;
if (tempo_encontro == -1) tempo_encontro = tempo_passado;
}
if (mapa_status[prox_x][prox_y] == 0) { // Célula vazia, B pode mover
mapa_status[prox_x][prox_y] = 2;
fila_agenteB.push_back({prox_x, prox_y});
}
}
}
}
}
std::cout << tempo_encontro << std::endl;
}
return 0;
}