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

/* program to generate all cutting-sticks problems for a given n */

#ifdef DEBUG
#define DEBUG_P1(S,P1) printf(S, P1)
#define DEBUG_P4(S,P1,P2,P3,P4) printf(S, P1, P2, P3, P4)
#else
#define DEBUG_P1(S,P1) 
#define DEBUG_P4(S,P1,P2,P3,P4) 
#endif

#define K_ALL  1
#define K_LIM  2
#define K_PART 3

#define MAX_K 100
#define MAX_N 50

int option_p_a_sol = 0;

int g_n;
int g_a[MAX_K];
int g_lb;
int g_k;
void (*g_doit)();

void fill_sol(int i, int tl, int h)
{
   DEBUG_P4("%*s fill_sol tl: %d h: %d\n", i, "", tl, h);
   if (i == g_k - 1)
   {   if (tl <= h && tl >= g_lb)
       {   g_a[i] = tl;
           (*g_doit)();
       }
   }
   else if (tl >= g_lb * (g_k - i))
   {   int t;

       for (t = h; t >= g_lb; t--)
       {   g_a[i] = t;
           fill_sol(i + 1, tl - t, t);
       }
   }    
}

void gen_all_l(int k, int kind, void (*doit)())
{ 
   DEBUG_P1("gen_all_k %d\n", k);

   if (k > MAX_K)
   {   printf("nr sticks > %d\n", MAX_K);
       return;
   }
   g_k = k;
   g_doit = doit;
   switch(kind)
   {   case K_PART :
           g_lb = 1;
           fill_sol(0, g_n * (g_n + 1)/2, g_n * (g_n + 1)/2);
           break;      
       case K_ALL : 
           g_lb = g_n;
           fill_sol(0, g_n * (g_n + 1)/2, g_n * (g_n + 1)/2);
           break;
       case K_LIM :
           g_lb = g_n + 1;
           fill_sol(0, g_n * (g_n + 1)/2, 2 * g_n - 2);
           break;
   }
}

void gen_all(int n, int kind, void (*doit)())
{  int k;
   int max_k = (kind == K_PART) ? n * (n + 1) / 2 : (n+1)/2;

   g_n = n;
   for (k = 1; k <= max_k; k++)
       gen_all_l(k, kind, doit);
}    

void print_sol()
{  int i;

   for (i = 0; i < g_k; i++)
      printf("%d ", g_a[i]);
   printf("\n");
}

int total = 0;

void count_sol()
{  total ++;
}

int g_a_eq[MAX_K];
char g_c[MAX_K][MAX_N + 1];
int nr_sol;
int low_nr_sol;

void select(int up, int low)
{ 
/***** 
    printf("%*sselect(%d, %d) : ", g_n - up + low, "", up, low);
    {   int i;

        for (i = 0; i < g_k; i++)
            printf("%d ", g_a[i]);
        printf("\n");
    } 
*****/
    if (up < low)
    {   nr_sol++;
        if (option_p_a_sol)
        {   int i, j;
            printf("  ");
            for (i = 0; i < g_k; i++)
            {   int first = 1;
    
                for (j = g_n; j > 0; j--)
                    if (g_c[i][j] == 1)
                    {   printf("%s%d", first ? "  " : "+", j);
                        first = 0;
                    }
            }
            printf("\n");
        }
    }
    else
    {   int i, nlow = 0, p;

        for (i = 0; i < g_k; i++)
            if (g_a[i] == low)
                if (++nlow > 1)
                    return;
                else
                    p = i;
       if (nlow == 1)
       {   g_c[p][low] = 1;
           g_a[p] -= low;
           select(up, low + 1);
           g_a[p] += low;
           g_c[p][low] = 0;
       }
       else
           for (i = 0; i < g_k; i++)
               if (  (   g_a[i] == up
                      || g_a[i] >= up + low)
                   && g_a_eq[i] == 0)
               {   int eq = g_a_eq[i+1];
                   g_a_eq[i+1] = 0;
                   g_c[i][up] = 1;
                   g_a[i] -= up;
                   select(up - 1, low);
                   g_a[i] += up;
                   g_c[i][up] = 0;
                   g_a_eq[i+1] = eq;
               }
    }
}
    

void test_sol()
{   int i, j, nr_perm;

    for (i = 0; i < g_k; i++)
        for (j = 0; j < g_n; j++)
            g_c[i][j] = 0;

    nr_perm = 1;
    j = 1;
    g_a_eq[0] = 0;
    for (i = 1; i < g_k; i++)
        if (g_a[i - 1] == g_a[i])
        {   nr_perm *= ++j;
            g_a_eq[i] = 1;
        }
        else
        {   j = 1;
            g_a_eq[i] = 0;
        }
    nr_sol = 0;
    for (i = 0; i < g_k; i++)
        printf("%d ", g_a[i]);
    if (option_p_a_sol)
        printf("\n");
    select(g_n, 1);

    if (low_nr_sol == 0 || nr_perm * nr_sol < low_nr_sol)
        low_nr_sol = nr_perm * nr_sol;
    printf(" sol: %d * %d = %d\n", nr_perm, nr_sol, nr_perm * nr_sol);
}

  

void main(int argc, char *argv[])
{  int option_count = 0;
   int option_find = 0;
   int kind = K_LIM;
   int i;

   if (argc == 1)
   {   printf("Usage: %s [-all | -part] [-count | -find [-print]] <nr>\n",
              argv[0]);
       printf("\n");
       printf("The program tries all sets of sticks:\n");
       printf("  -all   : larger equal n.\n");
       printf("  -part  : with no limitation\n");
       printf("  <none> : between n and 2n-1\n");
       printf("\n");
       printf("  -count : count possible sets of sticks\n");
       printf("  -find  : find solutions for each set of sticks\n");
       printf("     -print : also print the solutions\n");
       printf("  <none> : just print sets of sticks\n");
       printf("\n");
   }
   option_p_a_sol = 0; 
   for (i = 1; i < argc; i++)
   {   char *arg =argv[i];

       if (!strcmp(arg, "-all"))
           kind = K_ALL;
       else if (!strcmp(arg, "-part"))
           kind = K_PART;
       else if (!strcmp(arg, "-count"))
           option_count = 1;
       else if (!strcmp(arg, "-find"))
           option_find = 1;
       else if (!strcmp(arg, "-print"))
           option_p_a_sol = 1;
       else if (atoi(arg) > 0)
       {   total = 0;
           low_nr_sol = 0;
           gen_all(atoi(arg), kind, 
                     option_find
                   ? test_sol
                   : option_count
                   ? count_sol 
                   : print_sol);
           if (option_count || option_find)
               printf("number solutions: %d\n", total);
           if (option_find)
               printf("low nr solution per set sticks: %d\n", low_nr_sol);
       }
       else 
           printf("Error: ignored: `%s'\n", arg);
   }
   

}