/* ----------------------------------------
 * Usage: nacci [term] [n]
 *
 * Program will return the [term]th term of
 * the [n]-acci sequence.
 *
 * Author: Nathan Lasseter
 * Date:   Tue 29th May 2012
 * Ack:    James Grime (@jamesgrime)
 --------------------------------------- */

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

// Left-shifts an array of size n
// leaving 0 at location n
void shiftup(int **array, int n) {
	int i;
	for (i=0; i<n; i++) (*array)[i] = (*array)[i+1];
	(*array)[n] = 0;
}

// Sums up all the terms from 0 to n-1
// and puts a 0 at location n
void sum(int **array, int n) {
	int i;
	for (i=0; i<n; i++) (*array)[n] += (*array)[i];
}

// Iterates to calculate the final value
int nacci(int term, int n) {
	int i, *a = calloc(n+1, sizeof(int));
	for (i=0; i < n; i++) a[i] = 0;
	a[n] = 1;

	for (i = term; i > 0; i--) {
		shiftup(&a, n);
		sum(&a, n);
	}

	i = a[n];
	free(a);
	return i;
}

int main(int argc, char** argv) {
	if (argc != 3) {
		printf("USAGE: nacci [term] [n]\n");
		return 1;
	}

	int term = atoi(argv[1]);
	int n = atoi(argv[2]);

	// Handle the obvious ones
	if (term < 0) {
		// Illegal
		printf("Term must be > or = to 0\n");
		return 1;
	} else if (term < (n-1)) {
		// Will always be 0
		printf("0\n");
		return 0;
	} else if (term < (n+1)) {
		// Will always be 1
		printf("1\n");
		return 0;
	} else {
		// Anything else we calculate
		printf("%d\n", nacci(term - (n-1), n));
		return 0;
	}
}