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:

• Entrada e Saída
• Estruturas Condicionais
• Loops

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:

• Strings e Vetores

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:

• DFS ou BFS

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:

• Set
• Algoritmos Gulosos

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: