Comentário NOIC OBI 2016 - Fase 1 - Programação Nível 2

Comentário por Rogério Júnior

Para ver o caderno de tarefas da primeira fase da Programação Nível 2 da OBI 2016, clique aqui.

Lâmpadas do hotel

Conhecimento prévio necessário:

1. Entrada e saída (Aula 1)
2. Estruturas condicionais (Aula 2)

Vamos ler a entrada e guardá-la nos inteiros ia, ib, fa  e fb. Vamos declarar também um inteiro resp, que guardará a resposta. Observe que só há uma maneira de alterar a lâmpada B: usando o interruptor $2$, logo, se ib for diferente de fb, então devemos usar o interruptor $2$, logo adicionamos um a resp e trocamos o estado da lâmpada A.

Feito isso, se os estados inicial e final da lâmpada A forem diferentes, então ainda precisamos apertar o interruptor $1$ uma vez, logo adicionamos mais um a resp. Por fim, basta imprimir o valor de resp. Segue o código para melhor entendimento:

Chaves

Conhecimento prévio necessário:

1. Entrada e saída (Aula 1)
2. Estruturas condicionais (Aula 2)

Note que, neste problema, os únicos caracteres que nos interessam são as chaves ('{' e '}'), logo, enquanto houver entrada, vamos ler cada um dos caracteres dela. Note que o número dado no começo não interfere pois ele não contêm nenhuma chave. Vamos salvar um inteiro qtd que guarda quantas chaves estão abertas no momento e uma variável booleana erro, que começa como falsa e fica verdadeira se em algum momento fecharmos uma chave que não foi previamente aberta.

Para cada caractere lido, se ele for uma chave abrindo ('{'), vamos apenas incrementar o valor de qtd em uma unidade. Se, entretanto, for uma chave fechando ('}'), vamos antes checar se há chaves abertas, pois se não houver, haverá erro de compilação no código ("if(qtd<1) erro=true;").

Após lermos a entrada, só precisamos checar duas coisas: se em algum momento fechamos uma chave que não havia sido aberta, erro será verdadeira e haverá erro de compilação. Além disso, se ainda houver chaves abertas, então qtd será diferente de zero e, novamente, haverá erro de compilação. Caso nenhum dos dois ocorra, não há problema nas chaves do código. Segue o código para melhor entendimento:

Chuva

Conhecimento prévio necessário:

1. Entrada e saída (Aula 1)
2. Estruturas condicionais (Aula 2)
3. Estruturas de repetição (Aula 2)
4. Vetores (Aula 3)

Observe uma seção $i$ qualquer da piscina, com altura $h_i$. Note que, se existem $j$ e $k$ tal que $j<i<k$ e $h_j>h_i$ e $h_k>h_i$, então a seção $i$ da piscina ficará coberta de água, pois há paredes mais altas para acumulá-la. Deste modo, seja $prefix_x$ a maior altura entre $h_1, h_2, h_3, ..., h_x$ e $suffix_x$ a maior entre $h_x, h_{x+1}, h_{x+2}, ..., h_n$. Deste modo, para saber se há seções da piscina anteriores e posteriores a $i$ que são mais altas que $h_i$, basta checarmos se $h_i<prefix_{i-1}$ e $h_i<suffix_{i+1}$.

Para fazermos isso de maneira rápida, basta precalcularmos os valores de $prefix_i$ e $suffix_i$ para todo $i$ e salvarmos em um vetor. Depois iremos percorrer todas as alturas (que também estarão salvas em um vetor) e verificaremos se cada seção estará coberta de água. Para cada seção coberta incrementaremos o valor da resposta em uma unidade. Para o precálculo, basta percorrermos todas as alturas observando a seguinte recursão: $prefix_0=0$ e $prefix_i=max(h_i,prefix_{i-1}) \forall i\geq 1$. De maneira análoga, $suffix_{n+1}=0$ e $suffix_i=max(h_i,suffix{i+1}) \forall i\leq n$.

Por fim, basta imprimirmos o valor da resposta. Segue o código para melhor entendimento:

Toca do Saci

Conhecimento prévio necessário:

1. Flood Fill (Aula 9)

Pela descrição do problema, há um único caminho que leva da casa $2$ à casa $3$. Logo, basta encontrarmos as casas com número $2$ e $3$ no tabuleiro e executarmos uma DFS de origem na casa 3, calculando as distâncias como calcularíamos em uma árvore (a distância até $u$ é a distância até seu pai $v$ mais $1$. Segue o código para melhor entendimento:

Sanduíche

Conhecimento prévio necessário:

1. Estruturas de repetição (Aula 2)
2. Vetores (Aula 3)

Note, primeiramente, que se o tamanho de todo o sanduíche não alcançar o valor de $D$, não há como satisfazer às exigências do problema, logo, imprimimos zero e fechamos o programa.

Agora, vamos reduzir o problema a algo mais simples: note que se duplicarmos o sanduíche ($C_{i+N}=C_i \forall i \leq n$), podemos ignorar a segunda operação (a de retirar das pontas), pois, no caso, retirar os segmentos de $1$ a $C_i$ e de $C_j$ a $N$ seria o mesmo que retirar o segmento contínuo de $C_j$ a $C_{i+N}$. Note ainda, que só precisamos testar todos os intervalos que começam em $i \leq N$, pois qualquer intervalo $(C_i,C_j), N<i<j$ pode ser representado no intervalo $(C_{i-N},C_{j-N})$.

Basta agora procurarmos os modos de escolhermos um sequência contínua de pedaços no sanduíche duplicado que tenha tamanho $D$. Para cada $i$, vamos encontrar o valor $f_i$ de modo que ele seja o fim da maior sequência contínua de pedaços que começa no pedaço $i$ e cujo tamanho não supera $D$ ($\sum\limits_{k=i}^{f_i}C_k \leq D$ e $\sum\limits_{k=i}^{f_i+1}C_k > D$). Note que $f_i$ é único que, se existe $j$ tal que $\sum\limits_{k=i}^{j}C_k =D$, então $j=f_i$. Note também que, se $j>i$, então $f_j \geq f_i$, pois $\sum\limits_{k=i}^{f_i}C_k \leq D \Rightarrow\sum\limits_{k=i}^{j-1}C_k+\sum\limits_{k=j}^{f_i}C_k \leq D \Rightarrow\sum\limits_{k=j}^{f_i}C_k \leq D \Rightarrow f_i \leq f_j$.

Deste modo, para cada $i \leq N$, basta encontrarmos $f_i$ e testarmos se a soma do segmento de $i$ a $f_i$ é exatamente $D$. Se for, incrementamos a resposta em uma unidade. Seja $prefix_i =\sum\limits_{k=1}^{i}C_k$. Deste modo, a soma do intervalo contínuo $(i,j)$ é exatamente $prefix_j-prefix_{i-1}$.

Assim, uma possível solução quadrática para o problema seria, para cada $i$, procurarmos dentre todos os $j$ tal que  $2N \geq j \geq i$ o $f_i$, incrementando o valor de $j$ enquanto $prefix_j-prefix_{i-1} \leq D$. Quando enfim encontrarmos $j=f_i$, bastaria verificar se a soma do intervalo contínuo de $i$ a $f_i$ é $D$. Se fosse incrementaríamos $1$ na resposta.

Porém, estamos esquecendo o fato provado de que $f_{i+1} \geq f_i$, logo não precisamos procurar $f_i$ em todos os possíveis $j$ tal que $i \leq j \leq 2N$, mas apenas entre os valores maiores ou iguais a $f_i$, ou seja, 0s $j$ tal que $f_i \leq j \leq 2N$. Para isso, basta declararmos o $j$ fora do segundo for para que ele continue com seu valor salvo, e quando calcularmos o valor de $f_{i+1}$ já começarmos de $f_i$.

Note que a complexidade deste loop é linear, pois alteramos o valor de $i$ no máximo $N$ vezes e o valor de $j$ no máximo $2N$ vezes. Por fim, basta imprimirmos a resposta. Segue o código para melhor entendimento: