Comentário NOIC OBI 2021 – Fase 3 – Programação Nível Júnior

OBI 2021 – Fase 3 – Programação Nível Júnior

Para se preparar para a OBI, confira o nosso Roteiro de Estudos, nele você vai encontrar um direcionamento completo de como estudar!

Comentário escrito por Lúcio Figueiredo, Leonardo Paes e Pedro Racchetti

Para conferir a prova na íntegra, clique aqui.

Ogro

Conhecimento prévio necessário:

Note que como $$n$$ é bastante baixo e existe apenas uma resposta para cada $$n$$, bastaria fazer uma sequência de 11 $$ifs$$. No entanto, isso tornaria o código longo, e aumentaria a chances de erros de digitação, as vezes difíceis de serem corrigidos – lembre-se, tempo é um recurso valioso na OBI! Portanto, ao invés de dividir o problema em vários casos, iremos calcular, a partir de $$n$$, quantos dedos cada mão irá mostrar, dividindo o problema em apenas três casos:

  • $$n = 0$$, haverá 0 dedos sendo mostrados em cada mão;
  • $$0 < n \leq 5$$ haverá $$n$$ dedos na mão esquerda, e 0 na direita;
  • $$5 < n \leq 10$$ Haverá 5 dedos na mão esquerda, e $$n-5$$ na direita.

Sabendo a quantidade exata de dedos em cada mão, podemos fazer dois $$fors$$, um para cada mão, para imprimir o número apropriado de dedos, devidamente tratando os casos em que uma mão não mostra dedos.

A complexidade da solução é $$O(n)$$, já que entre os dois $$fors$$, haverão no máximo $$n$$ operações. Segue o código, para melhor compreensão.

Casamento de inteiros

Conhecimento prévio necessário:

Inicialmente, leremos $$A$$ e $$B$$ como strings e ajustaremos seus tamanhos adicionando zeros à esquerda até que o tamanho de $$A$$ seja igual ao tamanho de $$B$$. Em seguida, vamos delcarar duas strings $$ans_A$$ e $$ans_B$$ que guardarão os valores $$A$$ e $$B$$ após o casamento. Após isso, iteraremos por cada dígito (ou caractere) de $$A$$ e $$B$$ e iremos compará-los assim como indicado no enunciado do problema, adicionando os dígitos resultantes do casamento em $$ans_A$$ ou $$ans_B$$. Por fim, precisamos remover quaisquer zeros à esquerda restantes em $$ans_A$$ e $$ans_B$$; para isso, usaremos a função $$stoi()$$, que transforma strings em inteiros e remove zeros à esquerda.

A complexidade da solução é $$O(max(digitos_A, digitos_B))$$. Confira o código abaixo para melhor compreensão:

Sr. Sapo

Conhecimento prévio necessário:

Para resolvemos esse problema, podemos visualizar a matriz dada como um grafo. Cada célula $$(i, j)$$ da matriz será um vértice do grafo. Haverá uma aresta entre dois vértices se, e somente se,  as três condições a seguir forem verdadeiras:

  1. Ambos os vértices são pedras;
  2. O pulo que o Sapo dá para ir de uma pedra para a outra é paralelo a um dos lados do lago;
  3. A distância do pulo é menor ou igual a $$3$$.

Segue uma imagem mostando todas as arestas partindo de um vértice arbitrário $$(i, j)$$, supondo que todos os vértices sejam pedras:

Após criado tal grafo, basta utilizar algum algoritmo de busca em grafos, como por exemplo uma DFS ou uma BFS. Iniciamos o algoritmo na posicão inicial do Sapo. Se em qualquer momento visitarmos a posição final, sabemos que é possível para o Sapo chegar lá; caso contrário, é impossível!

A complexidade da solução é $$O(N \cdot M)$$. Confia o código abaixo para melhor compreensão:

Plano de estacionamento

Conhecimento prévio necessário:

Para resolver este problema, usaremos a seguinte estratégia gulosa:

  1. Para o $$i$$-ésimo cliente, encontre a maior vaga não-ocupada menor ou igual a $$V_i$$;
  2. Caso não exista nenhuma vaga não-ocupada menor ou igual a $$V_i$$, termine o programa;
  3. Caso contrário, marque a vaga encontrada como ocupada e repita o algoritmo para o cliente seguinte.

A intuição por trás do funcionamento desta estratégia é que, para cada cliente, sempre selecionaremos a sua “pior” vaga possível. Em outras palavras, ao escolhermos a maior vaga possível para um cliente, tornamos o conjunto de vagas não-ocupadas melhor possível para clientes futuros (já que uma vaga de menor índice acomoda todos os clientes que uma vaga maior também acomodaria).

Para implementar o algoritmo acima, basta utilizarmos um set: Inicialmente, inserimos no set todas as $$N$$ vagas; em seguida, podemos encontrar a maior vaga menor ou igual a $$V_i$$ utilizando a função upper_bound implementada no set (mais detalhes no código abaixo); por fim, removemos a vaga encontrada (se existir) utilizando a função erase.

Como as operações realizadas no set possuem complexidade $$O(\log_{} N)$$, a complexidade da solução é $$O(M \cdot \log_{} N)$$. Confira o código abaixo para melhor compreensão: