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

#define ENDOFREC -1
#define P1 3
#define P2 5
#define P3 7
#define NOT_FOUND 0
#define FOUND 1

typedef struct _node {
   int k;
   int u;
   int v;
   struct _node *next;
} node;

typedef node **htbl;

int *genlen ( int n )
{
   int *A, i;

   printf("    ");
   A = (int *)malloc(n * sizeof(int));
   for (i=0; i<n; ++i) {
      A[i] = 1 + rand() % 9;
      printf("%d ", A[i]);
   }
   printf("\n");
   return A;
}

/* Recursive function */
int esearchrec ( int L, int *A, int n, int k, int u, int v )
{
   int k1, k2;

   if (k == n) return k;
   k1 = k2 = ENDOFREC;
   if (u+A[k] <= L) k1 = esearchrec(L,A,n,k+1,u+A[k],v);
   if (v+A[k] <= L) k2 = esearchrec(L,A,n,k+1,u,v+A[k]);
   if ((k1 == ENDOFREC) && (k2 == ENDOFREC)) return k;
   return (k1 >= k2) ? k1 : k2;
}

/* Wrapper function */
int exhsearch ( int L, int *A, int n )
{
   return esearchrec(L,A,n,0,0,0);
}

int H ( int k, int u, int v, int s )
{
   return (P3 * k + P1 * u + P2 * v) % s;
}

htbl init ( int s )
{
   htbl T;

   T = (node **)malloc(s * sizeof(node));
   while (--s >= 0) T[s] = NULL;
   return T;
}

int search ( htbl T, int s, int k, int u, int v )
{
   int h;
   node *p;

   h = H(k,u,v,s);
   p = T[h];
   while (p) {
      if ((p -> k == k) && (p -> u == u) && (p -> v == v)) return FOUND;
      p = p -> next;
   }
   return NOT_FOUND;
}

void insert ( htbl T, int s, int k, int u, int v )
{
   int h;
   node *p;

   h = H(k,u,v,s);

   /* Search */
   p = T[h];
   while (p) {
      if ((p -> k == k) && (p -> u == u) && (p -> v == v)) return;
      p = p -> next;
   }

   /* If search is unsuccessful */
   p = (node *)malloc(sizeof(node));
   p -> k = k; p -> u = u; p -> v = v;
   p -> next = T[h]; T[h] = p;
}

void freetbl ( htbl T, int s )
{
   node *p, *q;

   while (--s >= 0) {
      p = T[s];
      while (p) {
         q = p;
         p = p -> next;
         free(q);
      }
   }
   free(T);
}


/* Recursive function */
int hsearchrec ( int L, int *A, int n, int k, int u, int v, htbl T, int s )
{
   int k1, k2;

   if (k == n) return k;
   insert(T,s,k,u,v);
   k1 = k2 = ENDOFREC;
   if ((u+A[k] <= L) && (search(T,s,k+1,u+A[k],v) == NOT_FOUND))
       k1 = hsearchrec(L,A,n,k+1,u+A[k],v,T,s);
   if ((v+A[k] <= L) && (search(T,s,k+1,v,v+A[k]) == NOT_FOUND))
      k2 = hsearchrec(L,A,n,k+1,u,v+A[k],T,s);
   if ((k1 == ENDOFREC) && (k2 == ENDOFREC)) return k;
   return (k1 >= k2) ? k1 : k2;
}

/* Wrapper function */
int hashsearch ( int L, int *A, int n )
{
   htbl T;
   int kmax, s;

   s = n * L;
   T = init(s);
   printf("    Hash table of size %d initialized\n", s);
   kmax = hsearchrec(L,A,n,0,0,0,T,s);
   freetbl(T,s);
   return kmax;
}

int main ( int argc, char *argv[] )
{
   int n, L, *A, k;
   clock_t c1, c2;

   if (argc > 1) L = atoi(argv[1]); else scanf("%d", &L);
   if (argc > 2) n = atoi(argv[2]); else scanf("%d", &n);
   printf("    %d %d\n", L, n);
   srand((unsigned int)time(NULL));

   A = genlen(n);

   printf("\n+++ Exhaustive search\n");
   c1 = clock(); k = exhsearch(L,A,n); c2 = clock();
   printf("    k = %d\n", k);
   printf("    Search time = %lf sec\n", (double)(c2-c1)/(double)CLOCKS_PER_SEC);

   printf("\n+++ Hash-based search\n"); fflush(stdout);
   c1 = clock(); k = hashsearch(L,A,n); c2 = clock();
   printf("    k = %d\n", k);
   printf("    Search time = %lf sec\n", (double)(c2-c1)/(double)CLOCKS_PER_SEC);

   free(A);

   exit(0);
}