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:
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // 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