Comentário Noic OBI 2019 - Fase 3 - Programação Nível 1

Comentário por Pedro Racchetti

Para conferir a prova na íntegra, clique aqui.

Coleção de Upas

Conhecimentos prévios necessários:

• Vetores
• Algoritmos Gulosos

Para resolver esse problema, temos que ter uma observação essencial: para qualquer $k$, temos que $2^0 + 2^1 +$ ... $2^{k-2} + 2^{k-1}$ $< 2^k$. Isso é facilmente compreendido, ao se entender o conceito de representação binária de um número, onde pode se ver que $2^0 + 2^1 +$ ... $2^{k-2} + 2^{k-1} = 2^k - 1$.

Portanto, podemos iterar pelas upas, da direita para a esquerda, e na $i$-ésima upa, marcamos todas as upas que não combinam com ela e somamos um ao total de upas que Mayuri deve manter na coleção, a menos que ela já esteja marcada já que com certeza, os valores somados de todas as que não combinam com ela, ao serem somadas, não ultrapassarão o valor da atual.

No final, basta imprimir o total, e iterar, agora da esquerda para a direita, pelo vetor de marcação, imprimindo todas que não estão marcadas.

Complexidade: $O(N + M)$

Segue o código, comentado, para melhor compreensão da solução:

Linhas de Ônibus

Conhecimentos prévios necessários:

• BFS 0 - 1

Para esse problema, representaremos o sistema de ônibus da grande cidade na China como um grafo, com as vértices representando os pontos de ônibus, e as arestas representarão as ligações de uma linha, armazenando as duas vértices que ela liga, e também em qual linha ela está.

Iremos então usar um algoritmo de menor caminho para achar o menor número de linhas usadas entre a origem e o destino, caminhando pelo grafo da seguinte maneira:

• Quando passarmos para uma aresta que muda a linha que estamos atualmente, somamos $1$ à distância.
• Quando passarmos para uma aresta que não muda a linha que estamos atualmente, somamos $0$ à distância

Note porém, que uma simples $BFS$ não funciona, já que para trocar de uma linha para outra, temos peso $1$, e na mesma linha, temos peso $0$, portanto, teremos que usar uma $BFS 0 - 1$.

Complexidade: Como cada vértice pode se conectar a duas vezes o número de linhas, teremos $O(T + TL)$ ou simplesmente $O(TL)$.

Segue o código, comentado, para melhor compreensão da solução:

Parcelamento Sem Juros

Conhecimento prévio necessário:

• Estruturas Condicionais
• Loops
• Entrada e Saída

Para esse problema, cada parcela terá como preço base $V/P$, e então nas parcelas $i$, tal que $i \leq Vmod(P)$, ou seja o resto da divisão de $V$ por $P$, somamos $1$.

Complexidade: $O(P)$

Segue o código, comentado, para melhor compreensão da solução:

Manchas de Pele

Conteúdos prévios necessários:

• Conceitos de Grafo
• Flood-Fill

Para esse problema, iremos representar a imagem dada como um grafo, usando a idéia de Dx Dy, onde ao invés de guardarmos os vizinhos, usaremos dois vetores, que guardam em qual direção deve-se ir na matriz, economizando memória. Como a OBI não recomenda uma implementação recursiva para esse problema, usaremos uma BFS para atravessar o grafo, guardando uma matriz de marcação, e sempre que encontrarmos um ponto não marcado que faz parte de uma mancha, aumentaremos 1 na resposta.

Complexidade: $$O(N*M)

Segue o código, comentado, para melhor compreensão da solução: