#include<stdio.h>
#include<assert.h>

#define MAX_N 10000
#define UNKNOWN -1



long long int memof[MAX_N +1];
int timeStamp[MAX_N +1], time;

void initMemoTable (){
	int i;
	for(i=0; i <= MAX_N; i++)  memof[i] = UNKNOWN; 
        memof[0]=memof[1]=1;
        timeStamp[0]=timeStamp[1]=time=0;
}

long long int fibonacci(int n){
	assert(n>=0);
	printf("sono stato chiamato con n=%d \n", n);
	if( memof[n] != UNKNOWN) return memof[n];

        // scrivo in tabella, e mi tengo traccia di quando ho scritto
        memof[n]=fibonacci(n-2)+fibonacci(n-1);
        timeStamp[n] = ++time;

	return memof[n]%MAX_N;
}

int main() {
	int n; 
	printf("Inserire n = "); scanf("%d", &n);
        initMemoTable();
	printf("\nfibonacci di %d %lld\n", n, fibonacci(n));
	int i;
        for(i = 0; i <= n; i++)
           printf("problema %d risolto in istante%d\n", i, timeStamp[i]);
}