Due sequenze

Correttore online – Intermedi

Siano date due sequenze così definite

• a₁=2, a₂=3, a₃=4, a₄=7, e (per n > 4) a_n=b_n-1+b_n-3
• b_n è una sequenza crescente di numeri non presenti in a_n.

Così, i numeri della successione a_n sono 2, 3, 4, 7, 13, 15, … e i numeri della successione b_n sono 1, 5, 6, 8, 9, 10, …
Dato un intero n, scrivete un programma per calcolare a_n e b_n.

Dati di input

Il file di input contiene il numero intero n (0 < n < 10001).

Dati di output

La prima riga del file di output deve contenere a_n, la seconda b_n.

Esempi di input/output

input.txt	output.txt
4	7 8
10	25 16

Autore/i: A.S. Stankevich, ACM ICPC Team St. Petersburg State University of Information technology, Mechanics and Optics.

/*
   Autore: Matteo Zappia
   Correttore online - Intermedi - Due sequenze
*/

#include
#include
#include
#define NMAX 10000

using namespace std;

int main()
{
	ifstream     fin ( "input.txt");
	ofstream     fout("output.txt");
	int          N;
    long         a[NMAX+1];
	vector b;

	fin >> N;
		
	a[0]=0;									// elemento di indice 0...
	a[1]=2; a[2]=3; a[3]=4; a[4]=7; a[5]=13;	
	b.push_back(0);							// elemento di indice 0...
	for(int i=1; i < 6; i++)
		for(int j=a[i-1]+1; j < a[i]; j++)
			b.push_back(j);
	
	for(int i=6; i <= N; i++)
	{
		a[i]=b[i-1]+b[i-3];
		for(int j=a[i-1]+1; j < a[i]; j++)
			b.push_back(j);
	}
		
	fout << a[N] << endl << b[N];
	return 0;
}