Solução Informática - Nível Intermediário - Semana 34

Solução escrita por Enzo Dantas

Conhecimento prévio necessário:

• Estruturas Condicionais
• Loops
• Algoritmo Guloso

A solução desse problema se baseia em duas principais observações - as partes de implementação e conhecimento teórico prévio são pouquíssimo relevantes.

Observação 1: primeiramente, se o menor número é maior que 1, é impossível formar o número 1 e essa é a resposta. Se, depois de utilizar o número 1, o menor número que temos é o 3, é impossível formar o número 2 e essa é a resposta. Generalizando, se o menor número que não conseguimos formar é $X$ e o menor número ainda não utilizado é maior que $X$, então é impossível formar $X$ e essa é a resposta.

Observação 2: se eu consigo formar todos os número até 4, por exemplo, e o menor número não utilizado é 3, então conseguimos formar todos os números até 4+3=7. É fácil ver que, se temos um número $X$ e é possível formar todos os números no intervalo $[l, r]$, então é possível adicionar $X$ a essas somas e formar todos os números no intervalo $[l+x, r+x]$. Perceba que, ao percorrer o array em ordem crescente, o intervalo de somas alcançáveis é sempre contínuo, e no momento que ele fica descontínuo então achamos a resposta, como é visto na observação 1. $l$ e $r$ são inicialmente 0, e o $r$ vai crescendo até achar a resposta enquanto o $l$ fica fixo no 0.

A complexidade desse código é $O(N*log_N)$ ($O(Nlog)$ para ordenar o array e $O(N)$ para percorrê-lo).

Recomendamos que você tente implementar o problema antes de ver o código.Veja a implementação nesse link.