Solução Informática Iniciante - Semana 55 - Problema 2

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;
	}

view raw

Soma de Prefixos: Primos.cpp

hosted with ❤ by GitHub