// 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;
}
Comments
0 B
|👍
/👎
0 B
|0 👍
/0 👎
0 B
|👍
/👎