/* * SWERC'2016 * Problem H - HyperPyramids * C99 solution using memoization * Author: Pedro Vasconcelos */ #include #include #define MAX_DIM 32 #define MAX_HEIGHT 32 #define HASH_SIZE 1007 #define MAX_ANSWERS 10000 /* simple hash table implementation */ #define NOT_FOUND (-1) struct _node { int *key; long val; struct _node *next; }; typedef struct _node node; typedef node *list; list new_node(int[], long, list); int equals(int[], int[], size_t); int all_zeros(int[], size_t); void sort_ints(int[], size_t); list hashtable[HASH_SIZE]; /* array for collecting numbers at base */ long answers[MAX_ANSWERS]; int count = 0; size_t hashcode(int v[], size_t len) { size_t code = 0; for (int i=0; ikey, len)) return p->val; p = p->next; } return NOT_FOUND; } int equals(int x[], int y[], size_t len) { for(int i=0; i key = key; p -> val = val; p -> next = l; return p; } int *new_key(int key[]) { int *new = (int*)malloc(MAX_DIM*sizeof(int)); for (int i=0; i y) return 1; return 0; } void sort_ints(int *xs, size_t n) { qsort(xs, n, sizeof *xs, &compare_ints); } /* insert result in order into output list */ void output(long result) { // determine position answers[count] = result; int i = 0; while(answers[i] < result) i++; if (i=i; j--) answers[j+1] = answers[j]; answers[i] = result; count ++; } void print_vec(int xs[], size_t len) { printf("{ "); for(int i=0; i1) { for (int c = l; c<=h; c++) { xs[len] = c; asc_coeffs(n-1, c, h-c, xs, len+1); } } else if (l<=h) { xs[len] = h; output(memoized(xs, len+1)); } } int main(void) { int xs[MAX_DIM]; int n, h; if (scanf("%d %d\n", &n, &h) != 2) { exit(-1); } asc_coeffs(n, 0, h-1, xs, 0); for(int i= 0; i