Se você quiser se preparar para a OBI, não deixe de conferir o Roteiro de estudos de informática, e também a página de informática do NOIC, com todos nossos materiais.
Ogro
Escrito por Caique Paiva
Conhecimentos Prévios Necessários:
Vamos fazer o que o problema pediu, Crie um if que vê:
- Caso $$E > D$$, imprima $$E+D$$.
- Caso contrário, imprima $$2(D-E)$$
Bactérias
Escrito por João Pedro Castro
Conhecimentos Prévios Necessários:
Esse é um caso clássico de um loop $$while$$, já que sabendo a quantidade de bactérias do dia anterior e o fator multiplicativo $$P$$ podemos calcular a quantidade do próximo dia. Tem diversas maneiras de se implementar, mas a mais comum seria você criar um contador de dias, e uma variável que diz a quantidade de bactérias no dia atual (algo como $$qtdB$$). E a condição do while seria algo como $$(qtdB \cdot P) \leq N$$, e dentro do loop você incrementa tanto o contador de dias quanto a $$qtdB$$.
Extra: é possível fazer essa questão sem o uso de loops, e com só 14 ifs! O motivo disso é que a resposta é no máximo 14, já que $$N \leq 30000$$ e $$log2(30000) < 15$$!
Concurso
Escrito por João Pedro Castro
Conhecimentos Prévios Necessários:
Quem fez essa questão foi muito generoso, pois existe várias maneiras de resolver ela. A mais comum eu imagino que tenha sido ordenar o vetor de maneira decrescente (maior para o menor), e imprimir a K-ésima posição. Essa é opção mais rápida, e acredito que a maioria tenha resolvido assim (incluindo eu). Mas, eu preferi tratar uma solução alternativa que não usa sort, e ela é bem legal também!
Perceba que para uma nota fixa é fácil checar se ela é uma nota válida ou não (possui no mínimo $$K$$ candidatos com a nota maior ou igual à ela). A complexidade disso, sem nenhuma otimização com outras técnicas, é $$O(N)$$. Só que perceba também que $$1 \leq A_i \leq 100$$ pelas restrições do enunciado, ou seja a resposta com certeza é uma dentre 100. Por tanto, tem como você só assumir que a resposta é $$x$$, começando com $$x = 100$$, e toda vez que der errado você diminui $$x$$ em 1; e quando der certo você pode encerrar o loop e imprimir $$x$$. E em no máximo 100 repetições você consegue uma resposta! Logo a complexidade final seria $$O(N \cdot 100)$$ ou $$O(N \cdot max(A_i))$$ que são iguais no pior caso.