OBI 2024 - Fase 1 - Programação Nível 2

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)

Clique aqui para ver o código

Relógio

Escrito por Caique Paiva

Conhecimentos Prévios Necessários:

Primeiro, adicione todos os t segundos em s, e então, enquanto s \ge 60, ou seja, não caber no relógio, tire 60 segundos de s e adicione 1 minuto em M. Feito isso, agora pode acontecer de M \ge 60, então faça o mesmo raciocínio, enquanto M \ge 60 tire 60 minutos de M e adicione 1 hora em H. Terminando, pode acontecer de H \ge 24, então, basta pegar o resto de H por 24.

Clique aqui para ver o código

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.

Clique aqui para ver o código

Jogo da vida

Escrito por Caique Paiva

Conhecimentos Prévios Necessários:

Vamos criar duas matrizes, uma chamada m que vai ser a original, e outra chamada nx, que vai ser a matriz depois de feito uma rodada do jogo. Vamos fazer a seguinte interação q vezes:

  • Para cada casinha, veja quem são os vizinhos dele, conte quanto estão vivos e quanto estão mortos, e então, cheque com um if else cada uma das condições. Suponha que estamos vendo a casinha (i, j):
    • Se m[i][j] == 0
      • Se ele tem 3 casas vizinhas vivas, então faça nx[i][j] = 1.
      • Caso contrário, faça nx[i][j] = 0
    • Caso contrário:
      • Se ele tem 2 ou 3 vizinhas vivas, faça nx[i][j] = 1.
      • Caso contrário, faça nx[i][j] = 0.
  • Feito isso, faça m[i][j] = nx[i][j], atualizando a matriz depois de uma rodada, e volte para o começo da interação

Clique aqui para ver o código