Cod sursa(job #2899618)

Utilizator miruna_georgescuMiruna Georgescu miruna_georgescu Data 8 mai 2022 23:29:54
Problema Planeta Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <fstream>
using namespace std; 

ifstream fin("planeta.in"); 
ofstream fout("planeta.out"); 

long long nrArbori[31]; 

void numarareArbori(int nrNoduri, long long nrArbori[31])
{
	nrArbori[0] = nrArbori[1] = 1; 
	
	for(int i = 2; i <= nrNoduri; i++)
		for (int j = 1; j <= i; j++)
			nrArbori[i] = nrArbori[i] + nrArbori[i - j] * nrArbori[j - 1]; 
}

void cautaArbore(int inceput, int sfarsit, long long indiceleK)
{
	int radacinaCrt; 
	for (radacinaCrt = inceput; radacinaCrt < sfarsit; radacinaCrt++)
	{
		long long subarboriSt = radacinaCrt - inceput, subarboriDr = sfarsit - radacinaCrt;

		if (nrArbori[subarboriSt] * nrArbori[subarboriDr] <= indiceleK)
			indiceleK = indiceleK - nrArbori[subarboriSt] * nrArbori[subarboriDr];
		else
			break;
	}

	fout << radacinaCrt << ' '; 
	
	if (radacinaCrt > inceput)
		cautaArbore(inceput, radacinaCrt - 1, indiceleK / nrArbori[sfarsit - radacinaCrt]);
	if (radacinaCrt < sfarsit)
		cautaArbore(radacinaCrt + 1, sfarsit, indiceleK % nrArbori[sfarsit - radacinaCrt]); 

}

int main()
{
	long long  nrNoduri, indiceleK; fin >> nrNoduri >> indiceleK; 
	numarareArbori(nrNoduri, nrArbori); 
	cautaArbore(1, nrNoduri, indiceleK-1); 

}