6_1.c

// uloha-6-1.c -- Tyzden 6 - Uloha 1
// Laszlo Nagy, 2.11.2013 01:44:21

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

unsigned long long values[5001];
unsigned long long heap[100001];

int size = 0;
int actual = 0;

//funkcie na orientovanie sa v halde
int parent(int n)
{
	return n/2;
}

int leftLeaf(int n)
{
	return 2*n;
}

int rightLeaf(int n)
{
	return 2*n + 1;
}

unsigned long top()
{
	return size>0 ? heap[0] : -1;
}

unsigned long long pop()
{
	unsigned long long target = top();
	heap[0] = heap[--size];
	heapify(0);
	return target;
}


//funkcia na vymenu prvkov
void swapElement(unsigned long long *a, unsigned long long *b)
{
	unsigned long long pom = *a;
	*a = *b;
	*b = pom;
}

void heapInsert(unsigned long long key)
{
	size++; // velkost heapu
	int act = size-1;
	while(heap[parent(act)] > key  && act > 0)
	{
		heap[act] = heap[parent(act)];
		act = parent(act);
	}
	heap[act] = key;
}

void heapify(int act)
{
	int left = leftLeaf(act);
	int right = rightLeaf(act);
	int largest = 0;
	if(left < size && heap[left] < heap[act])
	{
		largest = left;
	}
	else
	{
		largest = act;
	}
	if(right < size && heap[right] < heap[largest])
	{
		largest = right;
	}
	if(largest != act)
	{
		swapElement(&heap[act], &heap[largest]);
		heapify(largest);
	}
}

//funkcia ktora nam predpocita jednotlive prvky
void precalc()
{
	if(actual > 5000)
		return;
	unsigned long actVal = pop();
	if(actVal > values[actual-1])
	{
		values[actual++] = actVal;
		heapInsert(actVal * 3LL);
		heapInsert(actVal * 5LL);
		heapInsert(actVal * 7LL);
	}
	precalc();
}

int main()
{
	int n;
	heapInsert(1);
	precalc();
	while(scanf("%d",&n) == 1)
	{
		printf("%llu\n", values[n-1]);
	}
	return 0;
}