/*

Deposito (IOI 2001)
Copyright (C) 2001 Alessandro Maconi

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA


(Come per tutti i problemi del 2001, è utile leggere il libretto distribuito
dagli organizzatori, e disponibile nella sezione "Materiale didattico" della
home page http://ioi.dsi.unimi.it/.)

Il programma si basa sul fatto che l'ultima cassa immessa risulterà sulla
prima riga. Inoltre la cassa eventualmente passata alla riga successiva avrà
valore maggiore (se non ne è stata spostata nessuna la cassa in questione sarà
l'ultima della riga).

Bisogna quindi mantenere "l'armonia" tra le casse, cioè non ci devono essere
che rompono l'ordine sequenziale all'interno di una stessa riga.

Per valutare il caso in cui la cassa sia l'ultima della fila tutti gli spazi
vuoti sono denominati come casse speciali di valore maggiore a tutte le altre
(100).

Il programma è formato da una sola funzione ricorsiva che prova a togliere una
cassa per volta (quella indicata nei parametri), sostituendola con una della
riga successiva, senza rompere "l'armonia" nella riga, scaricando poi
ricorsivamente l'eliminazione della cassa scelta per la sostituzione nella
riga successiva.

Naturalmente la ricorsione termina quando si incontra una cassa "speciale"
(spazio vuoto), caso in cui si continua a togliere casse dalla prima riga,
quando non ci sono più casse nel deposito (e scrive la soluzione in output),
oppure quando non si può effettuare la sostituzione di una cassa, caso in cui
si rientra dalla ricorsione

P.S.: ci potrebbero essere dei problemi a capire i nomi delle variabile, ma
basta sapere che le casse le ho chiamate scatole per capire un po' di più

*/

#include <stdio.h>

#define MXN 13 /* costante per il numero massimo delle casse */
#define MXC 100 /* valore degli spazi vuoti */

/* funzione per la rimozione dell'ultima cassa inserita */

void rimuovi(int riga,int ele,int sol[MXN],int disp[MXN+1][MXN+1],int scat);

int ns;                   /* numero delle casse nel deposito */
FILE *fout;

int main()
{
  FILE *fin;
  int disp[MXN+1][MXN+1]; /* disposizione totale */
  int sol[MXN];           /* soluzione parziale */
  int nscat[MXN];         /* numero delle casse per ogni riga */
  int r;                  /* numero delle righe */
  int i,j;

  for(i=0;i<MXN+1;i++)
    for(j=0;j<MXN+1;j++)
      disp[i][j]=MXC;

  fout=fopen("depot.out","w");
  fin=fopen("depot.in","r");
  fscanf(fin,"%d",&r);
  /* lettura input */
  for(i=0;i<r;i++)
    {
      fscanf(fin,"%d",&nscat[i]);
      ns+=nscat[i];
      for(j=0;j<nscat[i];j++)
	fscanf(fin,"%d",&disp[i][j]);
    }
  /* ciclo per togliere ogni singola cassa della prima riga */
  for(i=0;i<nscat[0];i++)
    {
      sol[ns-1]=disp[0][i]; /* salvo la cassa che provo a togliere nella soluzione in fondo (inserita per ultima) */
      rimuovi(0,i,sol,disp,ns-1);
    }
  return 0;
}

/* parametri: riga in cui togliere una cassa, cassa da togliere, soluzione
provvisoria, disposizione attuale, numero di casse rimaste */

void rimuovi(int riga,int ele,int sol[MXN],int disp[MXN+1][MXN+1],int scat)
{
  int i,j,t;
  /*  caso in cui non ci sono più casse nel deposito: scrivo l'output */
  if(scat==0)
    {
      for(j=0;j<ns;j++)
	fprintf(fout,"%d ",sol[j]);
      fprintf(fout,"\n");
      return;
    }
  
  /* caso in cui la cassa da togliere non è uno spazio vuoto */

  if(disp[riga][ele]!=MXC)
    {
      /* cerco tra le casse della riga successiva se ce n'è qualcuna che non
      rompe "l'armonia" */

      for(i=0;i<=ele+1&&disp[riga+1][i]!=MXC;i++)
	{
	  if(disp[riga+1][i]>disp[riga][ele]&&disp[riga+1][i]<=disp[riga][ele+1]&&disp[riga+1][i]<=disp[riga+1][ele])
	    {
	      /* in quel caso sostituisco e scarico ricorsivamente sistemando
	      al rientro dalla ricorsione */

	      t=disp[riga][ele];
	      disp[riga][ele]=disp[riga+1][i];
	      rimuovi(riga+1,i,sol,disp,scat);
	      disp[riga][ele]=t;
	    }
	}
      /* provo la sostituzione con uno spazio vuoto con stesso metodo delle
      altre casse */

      if(disp[riga+1][i]==MXC)
	{
	  if(disp[riga+1][i]>disp[riga][ele]&&disp[riga+1][i]<=disp[riga][ele+1]&&disp[riga+1][i]<=disp[riga+1][ele])
	    {
	      t=disp[riga][ele];
	      disp[riga][ele]=disp[riga+1][i];
	      rimuovi(riga+1,i,sol,disp,scat);
	      disp[riga][ele]=t;
	    }
	}
    }
  else
    {
      /* caso la cassa con cui ho sostituito è uno spazio vuoto: riparto dalle
      casse della prima riga ottenuta dalla sostituzione (prima riga
      attuale!=prima riga originale) */

      riga=0;
      for(i=0;disp[riga][i]<MXC;i++)
	{
	  sol[scat-1]=disp[riga][i]; /* salvo la cassa nella soluzione */
	  rimuovi(riga,i,sol,disp,scat-1);
	}
    }
}