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:
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:
https://gist.github.com/rogerioagjr/a6293b700e292f7611f1642e5c14de79
Chaves
Conhecimento prévio necessário:
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:
https://gist.github.com/rogerioagjr/3cb20e7a136c7410ebadfda7cc4dc69c
Chuva
Conhecimento prévio necessário:
- Entrada e saída (Aula 1)
- Estruturas condicionais (Aula 2)
- Estruturas de repetição (Aula 2)
- 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:
https://gist.github.com/rogerioagjr/fa392e814b74e79edb0bd63da82aff2b
Toca do Saci
Conhecimento prévio necessário:
- 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:
https://gist.github.com/rogerioagjr/ead7a3e5644ad2daf56e997b0aaa9780
Sanduíche
Conhecimento prévio necessário:
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.
https://gist.github.com/rogerioagjr/3739042e929ba6417214578f689964c7
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$$.
https://gist.github.com/rogerioagjr/9a13e84dfca18e1d88af43e7ae00dd89
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:
https://gist.github.com/rogerioagjr/d907adad480b841ec0b89448e7ecea38