Problema A: Verificação de Intervalo Simples
Este problema solicita uma verificação básica de intervalo. Dada uma entrada numérica $S$, determine se $S$ está dentro do intervalo fechado $[200, 299]$.
Solução
A solução envolve uma simples declaração condicional. Se $S$ for maior ou igual a 200 E $S$ for menor ou igual a 299, a saída deve ser "Success". Caso contrário, a saída deve ser "Failure".
// C++ para o Problema A
#include <iostream>
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int valorS;
std::cin >> valorS;
if (valorS >= 200 && valorS <= 299) {
std::cout << "Success\n";
} else {
std::cout << "Failure\n";
}
return 0;
}
Problema B: Simulação de Autenticação
O problema consiste em simular um sistema de autenticação básico. O programa recebe uma série de $Q$ comandos: "login", "logout" ou "private". Precisamos contar quantas vezes o comando "private" foi invocado enquanto o usuário estava deslogado.
Solução
Uma variável booleana pode ser utilizada para manter o estado de login (logado ou deslogado). Inicialmente, o usuário está deslogado. Para cada comando:
- "login": Define o estado de login como verdadeiro.
- "logout": Define o estado de login como falso.
- "private": Se o estado de login for falso, incrementa um contador de acessos não autorizados.
Ao final de todos os comandos, o valor do contador é impresso.
// C++ para o Problema B
#include <iostream>
#include <string>
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int numConsultas;
std::cin >> numConsultas;
int acessosInvalidos = 0;
bool autenticado = false; // false = deslogado, true = logado
for (int i = 0; i < numConsultas; ++i) {
std::string comando;
std::cin >> comando;
if (comando == "login") {
autenticado = true;
} else if (comando == "logout") {
autenticado = false;
} else if (comando == "private") {
if (!autenticado) { // Se não estiver logado
acessosInvalidos++;
}
}
}
std::cout << acessosInvalidos << "\n";
return 0;
}
Problema C: Soma Recorrente com Programação Dinâmica
Dado dois inteiros positivos $n$ e $k$, precisamos construir uma sequência $a$ de comprimento $n+1$ ($a_0, a_1, \ldots, a_n$) com as seguintes regras:
- Para $0 \le i < k$, $a_i = 1$.
- Para $i \ge k$, $a_i = a_{i-k} + a_{i-k+1} + \ldots + a_{i-1}$.
O objetivo é encontrar $a_n$ módulo $10^9$.
Solução
Esta é uma aplicação clássica de Programação Dinâmica. A recorrência $a_i = \sum_{j=i-k}^{i-1} a_j$ envolve a soma dos $k$ elementos anteriores. Uma soma direta a cada passo seria $O(k)$, levando a uma complexidade total de $O(nk)$, que pode ser muito lenta para $n$ de até $10^6$.
Para otimizar a soma, podemos usar somas de prefixo. Seja $P_i = \sum_{j=0}^{i} a_j$ a soma dos elementos de $a$ de $0$ até $i$. Então, a soma de um intervalo $a_x + \ldots + a_y$ pode ser calculada como $P_y - P_{x-1}$.
Aplicando isso à nossa recorrência:
$$a_i = P_{i-1} - P_{i-k-1}$$ É crucial lembrar que todas as operações devem ser realizadas módulo $10^9$. Ao subtrair, se o resultado intermediário for negativo, devemos adicionar o módulo para garantir um valor positivo antes de aplicar o opreador de módulo novamente: $(X - Y + \text{MOD}) \% \text{MOD}$.
Inicializamos $a_0 = 1$ e $P_0 = 1$. Em seguida, iteramos de $i=1$ até $n$:
- Para $i < k$, $a_i = 1$.
- Para $i \ge k$, $a_i = (P_{i-1} - P_{i-k-1} + \text{MOD}) \% \text{MOD}$.
Em cada passo, atualizamos $P_i = (P_{i-1} + a_i) \% \text{MOD}$.
// C++ para o Problema C
#include <iostream>
#include <vector>
const int MODULO = 1e9; // 10^9
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int n, k;
std::cin >> n >> k;
std::vector<long long> valores_seq(n + 1);
std::vector<long long> somas_prefixo(n + 1);
// Inicialização para i < k
valores_seq[0] = 1;
somas_prefixo[0] = 1;
for (int i = 1; i < k; ++i) {
valores_seq[i] = 1;
somas_prefixo[i] = (somas_prefixo[i-1] + valores_seq[i]) % MODULO;
}
// Cálculo para i >= k usando somas de prefixo
for (int i = k; i <= n; ++i) {
long long soma_anterior = (somas_prefixo[i-1] - somas_prefixo[i-k-1] + MODULO) % MODULO;
valores_seq[i] = soma_anterior;
somas_prefixo[i] = (somas_prefixo[i-1] + valores_seq[i]) % MODULO;
}
std::cout << valores_seq[n] << "\n";
return 0;
}
Problema D: Preenchimento de String com Restrições
Você recebe uma string $S$ de comprimento $n$, composta por caracteres '.', 'o', e '?'. O objetivo é substituir cada '?' por '.' ou 'o' de forma que a string resultante tenha exatamente $k$ caracteres 'o' e nenhum 'o' seja adjacente a outro 'o'. Se um '?' pode ser determinado como '.' ou 'o' de forma única, imprima o caractere. Caso contrário, imprima '?'.
Solução
Primeiro, precisamos processar os caracteres 'o' já existentes na string. Cada 'o' impede que seus vizinhos sejam 'o'. Portanto, se $S[i]$ for 'o', então $S[i-1]$ (se existir) e $S[i+1]$ (se existir) devem ser '.'. Podemos marcar essas posições como impossíveis de conter 'o' e decrementar $k$ pelo número de 'o's que já temos.
Após este pré-processamento, a string conterá '.', 'o' (com vizinhos já marcados como '.'), e '?'. Agora, $k$ representa o número de 'o's que ainda precisamos colocar nos caracteres '?'.
Para cada bloco contíguo de '?'s que não estão marcados como impossíveis de conter 'o', o número máximo de 'o's que podemos colocar é $\lceil \text{tamanho do bloco} / 2 \rceil$. Por exemplo, '???' pode ter 'o.o' (2 'o's), '????' pode ter 'o.o.' ou '.o.o' (2 'o's). Somamos esses máximos potanciais para obter max\_o\_possivel.
Com base nos valores de $k$ (o restante de 'o's a serem colocados) e max\_o\_possivel, podemos determinar o resultado:
- Caso 1: $k \le 0$: Não precisamos colocar mais 'o's (ou já colocamos demais, o que indicaria uma entrada inválida, mas para o problema, assumimos $k$ não será negativo). Todos os '?' restantes devem ser preenchidos com '.'.
- Caso 2: $k == \text{max_o_possivel}$: Estamos no estado de "saturação". Isso significa que precisamos colocar o número máximo possível de 'o's em todos os blocos de '?' válidos.
- Para blocos de '?' com comprimento ímpar (e.g., '???'), podemos determinar a posição dos 'o's de forma única (alternando 'o' e '.'). A escolha do primeiro caractere do bloco dependerá do seu vizinho à esquerda: se o vizinho é 'o', o '?' deve ser '.'; caso contrário, pode ser 'o'.
- Para blocos de '?' com comprimento par (e.g., '????'), ainda há ambiguidade nas posições. Por exemplo, 'o.o.' vs '.o.o'. Nesses casos, os '?' permanecem como '?'.
- Caso 3: $0 < k < \text{max_o_possivel}$: Temos flexibilidade. Não precisamos usar todos os espaços possíveis para 'o's, nem somos forçados a não usar nenhum. Portanto, nenhuma posição '?' pode ser determinada unicamente como '.' ou 'o'. Todos os '?' devem permanecer como '?'.
Ao final, qualquer '?' que foi marcado como impossível de conter 'o' (devido a um 'o' vizinho) e que ainda não foi preenchido, deve ser preenchido com '.'.
// C++ para o Problema D
#include <iostream>
#include <string>
#include <vector>
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int n, k;
std::cin >> n >> k;
std::string s_original;
std::cin >> s_original;
std::string resultado_str = s_original;
// Vetor para marcar posições que NÃO podem ser 'o'
std::vector<bool> posicao_proibida_o(n, false);
// 1. Processar 'o's existentes, decrementar k, e marcar vizinhos como proibidos
for (int i = 0; i < n; ++i) {
if (resultado_str[i] == 'o') {
k--;
if (i > 0) posicao_proibida_o[i-1] = true;
if (i < n - 1) posicao_proibida_o[i+1] = true;
}
}
// Ajustar k se for negativo, assumindo que a entrada é válida e apenas precisamos preencher '?'
// Em um cenário de concurso, k negativo aqui poderia indicar que a entrada original já violava as regras.
if (k < 0) k = 0;
// 2. Calcular o número máximo de 'o's que podem ser colocados nos '?' restantes
int max_o_possivel = 0;
for (int i = 0; i < n; ++i) {
if (resultado_str[i] == '?' && !posicao_proibida_o[i]) {
int inicio_bloco = i;
while (i < n && resultado_str[i] == '?' && !posicao_proibida_o[i]) {
i++;
}
int tamanho_bloco = i - inicio_bloco;
max_o_possivel += (tamanho_bloco + 1) / 2;
i--; // Ajusta o índice para o loop externo
}
}
// 3. Aplicar as regras de preenchimento com base em k e max_o_possivel
if (k <= 0) { // Caso 1: Nenhuma 'o' adicional necessária
for (int i = 0; i < n; ++i) {
if (resultado_str[i] == '?') {
resultado_str[i] = '.';
}
}
} else if (k == max_o_possivel) { // Caso 2: Estado de saturação
for (int i = 0; i < n; ++i) {
if (resultado_str[i] == '?' && !posicao_proibida_o[i]) {
int inicio_bloco = i;
while (i < n && resultado_str[i] == '?' && !posicao_proibida_o[i]) {
i++;
}
int tamanho_bloco = i - inicio_bloco;
if (tamanho_bloco % 2 != 0) { // Bloco de '?' de comprimento ímpar: 'o.o'
char char_anterior = (inicio_bloco == 0) ? '.' : resultado_str[inicio_bloco - 1];
char proximo_a_colocar = (char_anterior == 'o') ? '.' : 'o';
for (int j = inicio_bloco; j < inicio_bloco + tamanho_bloco; ++j) {
resultado_str[j] = proximo_a_colocar;
proximo_a_colocar = (proximo_a_colocar == 'o') ? '.' : 'o';
}
} // Bloco de comprimento par permanece '?'
i--; // Ajusta o índice
}
}
} else { // Caso 3: 0 < k < max_o_possivel, há flexibilidade. '?' permanecem como '?'
// Nenhuma ação é necessária, '?' permanecem.
}
// 4. Preencher quaisquer '?' que foram marcados como proibidos de serem 'o' com '.'
for (int i = 0; i < n; ++i) {
if (resultado_str[i] == '?' && posicao_proibida_o[i]) {
resultado_str[i] = '.';
}
}
std::cout << resultado_str << "\n";
return 0;
}