Solução por Leonardo Paes
Para esse problema usaremos a ideia de soma de prefixos, ou soma acumulada, do vetor $$v$$. A ideia é, guardamos um vetor $$pref[N]$$, onde $$pref[i]$$ significa a soma de todas as posições de $$v$$ de $$1$$ até $$i$$. Por exemplo, se $$v = {1, 2, 3, 4, 5}$$ então $$pref[3] = 1 + 2 + 3$$. Note que a soma do intervalo $$[a, b]$$ pode ser escrita como $$pref[b] – pref[a – 1]$$. Para a solução descrita abaixo, somente a ideia será utilizada, então não criaremos tal vetor $$pref$$.
Vamos considerar, inicialmente, que a quantidade de números $$1$$ é $$0$$. Então, a resposta é uma sequência de $$N$$ números $$2$$. Analogamente, se o número $$2$$ não estiver presente em nenhum papel, a resposta é uma sequência que contém $$N$$ números $$1$$ escritos. Agora, garantimos que, tanto a quantidade de números $$1$$, como a de números $$2$$, é maior que $$0$$. Então, nesses casos, sempre é possível obtermos os números $$2$$ e $$3$$ como soma de prefixos da nossa sequência, utilizando, para isso, um número $$2$$ seguido por um $$1$$, já que $$2+1=3$$.
Por fim, a observação final é: Todos os números primos maiores que $$3$$ são ímpares, já que todo número par maior que $$2$$ possui pelo menos três divisores: $$1, 2$$ e ele mesmo! Como o $$3$$ já é ímpar, ao somarmos uma quantidade $$x$$ de números pares a ele, continuaremos com um número ímpar.
Prova: $$3 + 2x = (2 + 1) + 2x = 1 + 2(x+1) $$. Todo o número, ao ser múltiplicado por $$2$$, se torna par. Neste caso, $$2(x+1)$$ é par. Um par somado com $$1$$ é um ímpar, então, $$3 + 2x$$ é ímpar.
Como $$2$$ é o menor par maior que 0, ao escrevermos todos os $$2$$ consecutivamente, estaremos, obrigatoriamente, obtendo todos os primos como somas de prefixos de tal sequência, pois estaremos somando $$3$$ com uma quantidade $$x$$ de números $$2$$. Após terem acabadas as quantidades de pedacinhos de papel contendo o número $$2$$, basta finalizarmos a resposta com todos os $$1$$ restantes.
A complexidade final será $$O(N)$$.
Código da Solução:
https://gist.github.com/Rockbet/685c2f14f104d2c27cc5881d7088e102
Deixe um comentário