/*1:*/
#line 6 "penta_virus.w"


#include <sys/time.h>
#include <sys/resource.h>
#include <stdio.h>

int Backtracks, Solution;
/*3:*/
#line 54 "penta_virus.w"

int Pentomino[12][5] = {
  {1, 10, 11, 12, 22},
  {0, 1, 2, 3, 4},
  {0, 1, 2, 3, 13},
  {0, 1, 2, 11, 12},
  {0, 1, 2, 12, 13},
  {2, 10, 11, 12, 22},
  {0, 1, 10, 20, 21},
  {0, 1, 2, 10, 20},
  {1, 2, 10, 11, 20},
  {1, 10, 11, 12, 21},
  {0, 1, 2, 3, 12},
  {0, 1, 11, 21, 22}
};

char Lettre[] = "# FILPNTUVWXYZ";

/*:3*//*4: */
#line 80 "penta_virus.w"

int Volume[1000];
int a, b, c;


/*:4*//*5: */
#line 94 "penta_virus.w"

int Orientation[288][6];

int IndexO[15];


/*:5*//*6: */
#line 111 "penta_virus.w"

int Ordre[14];


/*:6*/
#line 13 "penta_virus.w"

/*2:*/
#line 21 "penta_virus.w"

struct rusage t1, t2;

long
cputime ()
{
  getrusage (RUSAGE_SELF, &t2);
  return (long) 1000 *(t2.ru_utime.tv_sec - t1.ru_utime.tv_sec)
    + (t2.ru_utime.tv_usec - t1.ru_utime.tv_usec) / 1000;
}

void
initcputime ()
{
  getrusage (RUSAGE_SELF, &t1);
}


/*:2*//*11: */
#line 265 "penta_virus.w"


static void
affsol ()
{
  int i, j, k;

  Solution++;
  printf ("Solution no %d en %d backtracks, %ld msecs",
	  Solution, Backtracks, cputime ());
  if (cputime () / 1000 != 0)
    printf (" (%f solutions/sec)", 1000.0 * Solution / cputime ());
  printf (".\n");

  for (i = 0; i < a; i++)
    {
      for (j = 0; j < b; j++)
	{
	  for (k = 0; k < i; k++)
	    printf ("  ");
	  for (k = 0; k < 2 * c; k += 2)
	    printf ("%c",
		    Lettre[Volume[i + j * (a + 1) + k * (a + 1) * b] + 1]);
	  printf ("\n");
	}
      printf ("\n");
    }
  Backtracks++;
}


static void
pentominos (int *vol)
{
  static int i = 0;
  register int j;
  int k;
  register int *ptr;
  int im;

  while (*vol)
    vol++;

  im = i++;
  k = Ordre[im];
  for (j = im; j < 12;)
    {
      for (ptr = Orientation[IndexO[k]]; *ptr == k; ptr += 6)
	if (!vol[ptr[2]] && !vol[ptr[3]] && !vol[ptr[4]] && !vol[ptr[5]])
	  {
	    vol[ptr[1]] = k;
	    vol[ptr[2]] = k;
	    vol[ptr[3]] = k;
	    vol[ptr[4]] = k;
	    vol[ptr[5]] = k;

	    if (i != 12)
	      pentominos (vol + 1);
	    else
	      affsol ();

	    vol[ptr[1]] = 0;
	    vol[ptr[2]] = 0;
	    vol[ptr[3]] = 0;
	    vol[ptr[4]] = 0;
	    vol[ptr[5]] = 0;
	  }
      k = Ordre[++j];
      Ordre[j] = Ordre[im];
      Ordre[im] = k;
    }
  ptr = Ordre + im;
  switch (12 - im)
    {
    case 12:
      *(ptr++) = *(ptr + 1);
    case 11:
      *(ptr++) = *(ptr + 1);
    case 10:
      *(ptr++) = *(ptr + 1);
    case 9:
      *(ptr++) = *(ptr + 1);
    case 8:
      *(ptr++) = *(ptr + 1);
    case 7:
      *(ptr++) = *(ptr + 1);
    case 6:
      *(ptr++) = *(ptr + 1);
    case 5:
      *(ptr++) = *(ptr + 1);
    case 4:
      *(ptr++) = *(ptr + 1);
    case 3:
      *(ptr++) = *(ptr + 1);
    case 2:
      *(ptr++) = *(ptr + 1);
    case 1:
      *(ptr++) = *(ptr + 1);
    }
  i = im;
  Backtracks++;
}


/*:11*//*13: */
#line 387 "penta_virus.w"

int
main (void)
{
  int i, j, k;
  int u, v;

  puts ("Les pentominos - algorithme de force brute");

  printf ("Longueur du volume ? ");
  scanf ("%d", &a);
  printf ("Largeur du volume ? ");
  scanf ("%d", &b);
  if (a > b)
    {
      i = a;
      a = b;
      b = i;
    }
  if (a * b < 60)
    {
      printf ("Hauteur du volume ? ");
      scanf ("%d", &c);
    }
  else
    c = 1;
  if (b > c)
    {
      i = b;
      b = c;
      c = i;
    }
  if (a > b)
    {
      i = a;
      a = b;
      b = i;
    }

/*7:*/
#line 123 "penta_virus.w"

  {
    for (i = 0; i < 12; i++)
      {

	for (j = 0; j < 24; j++)
	  Orientation[i * 24 + j][0] = i + 1;

	for (j = 0; j < 5; j++)
	  {

	    u = Pentomino[i][j] % 10;
	    v = Pentomino[i][j] / 10;

	    Orientation[i * 24][j + 1] = u + (a + 1) * v;
	    Orientation[i * 24 + 1][j + 1] = v + (a + 1) * u;
	    Orientation[i * 24 + 2][j + 1] = u + 2 * (a + 1) * b * v;
	    Orientation[i * 24 + 3][j + 1] = v + 2 * (a + 1) * b * u;
	    Orientation[i * 24 + 4][j + 1] =
	      (a + 1) * v + 2 * (a + 1) * b * u;
	    Orientation[i * 24 + 5][j + 1] =
	      (a + 1) * u + 2 * (a + 1) * b * v;

	    if (i != 0)
	      {

		Orientation[i * 24 + 6][j + 1] = u - (a + 1) * v;
		Orientation[i * 24 + 7][j + 1] = -u + (a + 1) * v;
		Orientation[i * 24 + 8][j + 1] = -u - (a + 1) * v;

		Orientation[i * 24 + 9][j + 1] = v - (a + 1) * u;
		Orientation[i * 24 + 10][j + 1] = -v + (a + 1) * u;
		Orientation[i * 24 + 11][j + 1] = -v - (a + 1) * u;

		Orientation[i * 24 + 12][j + 1] = u - 2 * (a + 1) * b * v;
		Orientation[i * 24 + 13][j + 1] = -u + 2 * (a + 1) * b * v;
		Orientation[i * 24 + 14][j + 1] = -u - 2 * (a + 1) * b * v;

		Orientation[i * 24 + 15][j + 1] = v - 2 * (a + 1) * b * u;
		Orientation[i * 24 + 16][j + 1] = -v + 2 * (a + 1) * b * u;
		Orientation[i * 24 + 17][j + 1] = -v - 2 * (a + 1) * b * u;

		Orientation[i * 24 + 18][j + 1] =
		  (a + 1) * u - 2 * (a + 1) * b * v;
		Orientation[i * 24 + 19][j + 1] =
		  -(a + 1) * u + 2 * (a + 1) * b * v;
		Orientation[i * 24 + 20][j + 1] =
		  -(a + 1) * u - 2 * (a + 1) * b * v;

		Orientation[i * 24 + 21][j + 1] =
		  (a + 1) * v - 2 * (a + 1) * b * u;
		Orientation[i * 24 + 22][j + 1] =
		  -(a + 1) * v + 2 * (a + 1) * b * u;
		Orientation[i * 24 + 23][j + 1] =
		  -(a + 1) * v - 2 * (a + 1) * b * u;
	      }
	    else
	      {
		for (k = 6; k < 24; k++)
		  Orientation[i * 24 + k][j + 1] = u + (a + 1) * v;
	      }
	  }
      }
  }


/*:7*/
#line 415 "penta_virus.w"
  ;
/*8:*/
#line 183 "penta_virus.w"

  {
    for (i = 0; i < 288; i++)
      {
	u = 32000;
	for (j = 1; j < 6; j++)
	  if (Orientation[i][j] < u)
	    u = Orientation[i][j];
	for (j = 1; j < 6; j++)
	  Orientation[i][j] -= u;
	for (j = 1; j < 6; j++)
	  for (k = j + 1; k < 6; k++)
	    if (Orientation[i][k] < Orientation[i][j])
	      {
		u = Orientation[i][j];
		Orientation[i][j] = Orientation[i][k];
		Orientation[i][k] = u;
	      }
      }
  }


/*:8*/
#line 416 "penta_virus.w"
  ;
/*9:*/
#line 210 "penta_virus.w"

  {
    for (i = 0; i < 288; i++)
      if (Orientation[i][0] != -1)
	for (k = i + 1; k < 288; k++)
	  {
	    u = -1;
	    for (j = 0; j < 6 && u; j++)
	      if (Orientation[i][j] != Orientation[k][j])
		u = 0;
	    if (u)
	      Orientation[k][0] = -1;
	  }
    k = 0;
    for (i = 0; i < 288; i++)
      if (Orientation[i][0] != -1)
	{
	  for (j = 0; j < 6; j++)
	    Orientation[k][j] = Orientation[i][j];
	  k++;
	}
    Orientation[k][0] = Orientation[k][1] = -1;
  }


/*:9*/
#line 417 "penta_virus.w"
  ;

/*10:*/
#line 238 "penta_virus.w"

  {
    u = 0;
    for (k = 0; k < c; k++)
      {
	for (j = 0; j < b; j++)
	  {
	    for (i = 0; i < a; i++)
	      Volume[u++] = 0;
	    Volume[u++] = -1;
	  }
	for (j = 0; j < b; j++)
	  {
	    for (i = 0; i <= a; i++)
	      Volume[u++] = -1;
	  }
      }
    while (u < 1000)
      Volume[u++] = -1;
    Volume[999] = 0;
  }


/*:10*/
#line 419 "penta_virus.w"
  ;

/*12:*/
#line 357 "penta_virus.w"

  {
    int l;
    for (i = 0; i < 12; i++)
      Ordre[i] = i + 1;
    Ordre[i] = 0;
    Solution = Backtracks = 0;

    for (i = 0; i < 12; i++)
      for (l = 0; Orientation[l][0] != -1; l++)
	if (Orientation[l][0] == i + 1)
	  {
	    IndexO[i + 1] = l;
	    break;
	  }


    initcputime ();
    pentominos (Volume);

    if (Solution == 0)
      puts ("Pas de solution");
    printf ("Total : %d backtracks, %ld usecs.\n", Backtracks, cputime ());
  }


/*:12*/
#line 421 "penta_virus.w"
  ;

  return 0;
}


/*:13*/
#line 14 "penta_virus.w"



/*:1*/