/* This program is explicitly in the public domain. */

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

#define NSTOP 8
#define NBUS 20
#define STOPRANGE 40
#define BUSRANGE 16

static unsigned int stops[NSTOP];
static unsigned int buses[NBUS];
static char stopsat[NSTOP][NBUS];
static unsigned int seed;

static void gen_testcase(void)
{
 int i;
 int j;
 unsigned int r;
 int nb;

 for (i=NSTOP-1;i>=0;i--) stops[i] = (random() % STOPRANGE) + 1;
 for (i=NBUS-1;i>=0;i--) buses[i] = (random() % BUSRANGE) + 1;
 nb = 0;
 for (i=NSTOP-1;i>=0;i--) for (j=NBUS-1;j>=0;j--)
  { if (nb < 1)
     { r = random();
       nb = 30;
     }
    stopsat[i][j] = r & 1;
    r >>= 1;
    nb --;
  }
}

static int try_seth(void)
{
 unsigned int v;
 unsigned int stopmask;
 unsigned int busmask;
 int i;
 int j;
 unsigned int stopsum;
 unsigned int bussum;

 for (v=1U<<NSTOP;v;v--)
  { stopmask = v - 1;
    stopsum = 0;
    bussum = 0;
    busmask = 0;
    for (i=NSTOP-1;i>=0;i--)
     { if ((stopmask >> i) & 1)
	{ stopsum += stops[i];
	  for (j=NBUS-1;j>=0;j--)
	   { if (stopsat[i][j])
	      { busmask |= 1U << j;
	      }
	   }
	}
     }
    for (i=NBUS-1;i>=0;i--) if ((busmask >> i) & 1) bussum += buses[i];
    if (bussum < stopsum) return(0);
  }
 return(1);
}

static void dump_testcase(void)
{
 int b;
 int s;

 printf("\nB  S");
 for (s=0;s<NSTOP;s++) printf(" %2d",stops[s]);
 printf("\n\n");
 for (b=0;b<NBUS;b++)
  { printf("%2d  ",buses[b]);
    for (s=0;s<NSTOP;s++) printf("  %c",stopsat[s][b]?'*':'-');
    printf("\n");
  }
}

int main(int, char **);
int main(int ac, char **av)
{
 if (ac == 1)
  { seed = time(0);
  }
 else
  { seed = strtoul(av[1],0,0);
  }
 printf("seed %u\n",seed);
 srandom(seed);
 do
  { gen_testcase();
  } while (! try_seth());
 dump_testcase();
 exit(0);
}