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:
| // Noic – Iniciante – Semana 55 – Problema 2 | |
| // O(N) | |
| #include <bits/stdc++.h> | |
| using namespace std; | |
| int main(){ | |
| //um representa a quantidade de 1's, e dois a quantidade de 2's | |
| int n, um=0, dois=0; | |
| cin >> n; | |
| for(int i=1; i<=n; i++){ | |
| int x; | |
| cin >> x; | |
| if(x==1)um++; | |
| else dois++; | |
| } | |
| if(dois==0){ | |
| for(int i=1; i<=n; i++){ | |
| cout << 1 << " "; | |
| } | |
| return 0; | |
| } | |
| else if(um==0){ | |
| for(int i=1; i<=n; i++){ | |
| cout << 2 << " "; | |
| } | |
| return 0; | |
| } | |
| for(int i=1; i<=n; i++){ | |
| if(i==1){ | |
| cout << 2 << " "; | |
| dois–; | |
| } | |
| if(i==2){ | |
| cout << 1 << " "; | |
| um–; | |
| } | |
| if(i>=3){ | |
| if(dois>=1){ | |
| cout << 2 << " "; | |
| dois–; | |
| } | |
| else{ | |
| if(um>=1){ | |
| cout << 1 << " "; | |
| um–; | |
| } | |
| } | |
| } | |
| } | |
| return 0; | |
| } |

Comente