Comentário por Pedro Racchetti
Para conferir a prova na íntegra, clique aqui.
Coleção de Upas
Conhecimentos prévios necessários:
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:
https://gist.github.com/PedroRacchetti/140603a21b5bca5ebbca75e0bc2a4de2
Linhas de Ônibus
Conhecimentos prévios necessários:
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:
https://gist.github.com/PedroRacchetti/c803a796fc696981d293a15228706680
Parcelamento Sem Juros
Conhecimento prévio necessário:
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:
https://gist.github.com/PedroRacchetti/2e6557a0f84923b9fb7dee4ba1106541
Manchas de Pele
Conteúdos prévios necessários:
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:
https://gist.github.com/PedroRacchetti/1c2138abf28fb4877c53955a4110e39e