Cod sursa(job #2752161)

Utilizator izotova_dIzotova Daria izotova_d Data 16 mai 2021 22:03:56
Problema Planeta Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.97 kb

#include<fstream>
#include <iostream>
using namespace std;
ifstream fin("planeta.in");
ofstream fout("planeta.out");
int permutations[32];


void countNumberOfBTS(int n)
{
	permutations[0] = 1;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= 1; j++)
		{
			permutations[i] += permutations[i - j] * permutations[j - 1];
		}
	}
}


void KthTraversal(int n, int k, int beginning)
{
	if (n == 1) {
		fout << beginning + 1 << " ";
		return;
	}

	if (n == 0)
	{
		return;
	}

	for (int i = 1; i <= n; i++)
	{
		int left = permutations[i - 1];
		int right = permutations[n - i];
		int total = left * right;

		if (total < k)
		{
			k -= total;
		}
		else
		{
			fout << beginning + i << " ";

			KthTraversal(i - 1, (k - 1) / right + 1, beginning);

			
			KthTraversal(n - i, (k - 1) % right + 1, beginning + i);
			return;
		}
	}
}

int main()
{
	int n, k;
	fin >> n >> k;

	countNumberOfBTS(n);
	KthTraversal(n, k, 0);

}