ONI 1997, Finala, Timisoara
Clasa XII
Ziua 2, Problema 2

Conducerea Liceului de Informatica "Grigore Moisil" din Timisoara intentioneaza
sa organizeze o excursie la Sherbrooke in Canada. Deoarece sunt multi amatori, 
a fost initiata o triere pe baza unui joc Timtris.
Jocul consta in  construirea unui zid dreptunghiular, compact (fara gauri) din 
piese care apar intr-o anumita ordine impusa.
Regulile jocului: 
 Exista 5 piese de forme diferite; acestea pot fi rotite cu 0, 90, 180, 270 grade. 
In tabelul de mai jos sunt prezentate piesele si orientarile lor posibile.

		Orientare1   	Orientare 2  	Orientare 3  Orientare 4
		---------
Piesa 1		|   |   |
		|-------|
		|   |   |
		---------
		 -----	   -----------------
		 |   |     |   |   |   |   |
		 -----	   -----------------
Piesa 2		 |   |
		 -----
		 |   |
		 -----
		 |   |
		 -----

		---------	       -----
		|   |   |	       |   |
Piesa 3		-------------	   ---------
		    |   |   |	   |   |   |
		    ---------	   ---------
				   |   |
				   -----

		    ---------	  -----
		    |   |   |	  |   |
Piesa 4		-------------	  ---------
		|   |   |	  |   |   |
		---------	  ---------
				      |   |
				      -----

	          -----		  -----		-------------	     -----
Piesa 5	          |   |		  |   |		|   |   |   |	     |   |
	      -------------	  ---------	-------------	 ---------
	      |   |   |   |	  |   |   |	    |   |	 |   |   |
	      -------------	  ---------	    -----	 ---------
				  |   |				     |   |
				  -----				     -----

 La construirea zidului trebuie sa plasati rand pe rand toate piesele, in 
   ordinea aparitiei lor. Odata aleasa orientarea piesei si coloana in care o 
veti plasa, se lasa sa cada (de sus in jos). Odata ce o piesa atinge baza sau a 
cazut pe o alta piesa din zid ea este plasata in acel loc. Piesele trebuie 
plasate astfel incat sa nu creeze nici o gaura in zid. Fiecare piesa trebuie 
plasata astfel incat sa nu depaseasca latimea impusa a zidului.
Un rand de zid completat (fara gauri) nu dispare.
Intrare:
Fisierul de intrare input.txt va contine:
- pe prima linie, latimea L (1<=L<=15) a zidului de construit;
- pe a doua linie, numarul N (1<=N<=50) de piese;
- pe fiecare din urmatoarele N linii, numarul piesei care urmeaza sa fie plasata. 
Tabelul anterior asociaza fiecarei piese un numar. Lista impune in acest fel 
ordinea de sosire.
Iesire:
Fisierul de iesire  output.txt trebuie sa contina:
- daca nu poate fi construit un zid compact, in fisier se va afisa NU;
- daca zidul poate fi construit, fisierul trebuie sa contina N linii cu 
urmatoarea structura: 
a b
unde a reprezinta orientare piesei, iar b reprezinta coloana in care este 
plasata extremitatea stanga a piesei.
Exemple:
1. pentru fisierul de intrare:		fisierul de iesire contine:
6
12					2	1
2					1	5
1					2	4
3					1	1
5					1	1
2					3	2
5					1	6
2					1	2
5					2	4
4					3	1
5					1	5
1					2	1
2

2. pentru fisierul de intrare:	fisierul de iesire trebuie sa contina:
	5			NU
	3
	5
	5
	5
Timp de executie: 30 secunde
Punctaj: 50 puncte
===============================
Program de evaluare al solutiei:
program eval;
uses graph,crt;
type piesat=array[1..4,1..4] of byte;
     piesa=record
       l,h:byte;
       p:piesat;
     end;
const p:array[1..5,1..4] of piesa=(
         ((l:2;h:2;p:((1,1,0,0),
                      (1,1,0,0),
                      (0,0,0,0),
                      (0,0,0,0))),
                 (l:2;h:2;p:((1,1,0,0),
                             (1,1,0,0),
                             (0,0,0,0),
                             (0,0,0,0))),
                 (l:2;h:2;p:((1,1,0,0),
                             (1,1,0,0),
                             (0,0,0,0),
                             (0,0,0,0))),
                 (l:2;h:2;p:((1,1,0,0),
                             (1,1,0,0),
                             (0,0,0,0),
                             (0,0,0,0)))),
         ((l:1;h:4;p:((1,0,0,0),
                      (1,0,0,0),
                      (1,0,0,0),
                      (1,0,0,0))),
         (l:4;h:1;p:((1,1,1,1),
                    (0,0,0,0),
                    (0,0,0,0),
                    (0,0,0,0))),
                    (l:4;h:1;p:((1,1,1,1),
                                (0,0,0,0),
                                (0,0,0,0),
                                (0,0,0,0))),
                    (l:4;h:1;p:((1,1,1,1),
                                (0,0,0,0),
                                (0,0,0,0),
                                (0,0,0,0)))),
         ((l:3;h:2;p:((1,1,0,0),
                      (0,1,1,0),
                      (0,0,0,0),
                      (0,0,0,0))),
         (l:2;h:3;p:((0,1,0,0),
                     (1,1,0,0),
                     (1,0,0,0),
                     (0,0,0,0))),
                    (l:4;h:1;p:((1,1,1,1),
                                (0,0,0,0),
                                (0,0,0,0),
                                (0,0,0,0))),
                    (l:4;h:1;p:((1,1,1,1),
                                (0,0,0,0),
                                (0,0,0,0),
                                (0,0,0,0)))),
         ((l:3;h:2;p:((0,1,1,0),
                      (1,1,0,0),
                      (0,0,0,0),
                      (0,0,0,0))),
         (l:2;h:3;p:((1,0,0,0),
                     (1,1,0,0),
                     (0,1,0,0),
                     (0,0,0,0))),
                    (l:4;h:1;p:((1,1,1,1),
                                (0,0,0,0),
                                (0,0,0,0),
                                (0,0,0,0))),
                    (l:4;h:1;p:((1,1,1,1),
                                (0,0,0,0),
                                (0,0,0,0),
                                (0,0,0,0)))),
         ((l:3;h:2;p:((0,1,0,0),
                      (1,1,1,0),
                      (0,0,0,0),
                      (0,0,0,0))),
         (l:2;h:3;p:((1,0,0,0),
                     (1,1,0,0),
                     (1,0,0,0),
                     (0,0,0,0))),
         (l:3;h:2;p:((1,1,1,0),
                     (0,1,0,0),
                     (0,0,0,0),
                     (0,0,0,0))),
         (l:2;h:3;p:((0,1,0,0),
                     (1,1,0,0),
                     (0,1,0,0),
                     (0,0,0,0)))));
      np:array[1..5] of byte=(1,2,2,2,4);
procedure iesire(s:string);
begin
  writeln(s);
  halt;
end;
{$l egavga.obj}
procedure egavga;external;
const lmax=15;hmax=80;
var fo,fi:text;
    i,j,k,l,n,h:integer;
    a,b,c:array[1..50] of integer;
    d:array[1..hmax,1..lmax] of integer;
    s:string;
    lat:integer;
    gd,gm:integer;

function pune_piesa(x,cu:integer):boolean;
var i,j,k,l:integer;t:boolean;
begin
  pune_piesa:=false;
  for i:=p[a[x],b[x]].h to hmax do  begin
    j:=c[x];;
    t:=true;
    for k:=1 to p[a[x],b[x]].h do for l:=1 to p[a[x],b[x]].l do
      if (d[i-k+1,j-1+l]<>0)and(p[a[x],b[x]].p[k,l]<>0) then t:=false;
    if t then begin
      for k:=1 to p[a[x],b[x]].h do for l:=1 to p[a[x],b[x]].l do
        if (p[a[x],b[x]].p[k,l]<>0) then
          d[i-k+1,j-1+l]:=p[a[x],b[x]].p[k,l]*cu;
      pune_piesa:=true;
      i:=hmax;
    end;
  end;
end;
{$i-}
begin
  Writeln('Programul DOAR afiseaza pozitionarea pieselor, si NU corectitudinea solutiei!');
  assign(fi,'input.txt');reset(fi);if ioresult<>0 then iesire('Nu exista input.txt');
  assign(fo,'output.txt');reset(fo);if ioresult<>0 then iesire('Nu exista output.txt');
  read(fi,l,n);if ioresult<>0 then iesire('Intrare gresita');
  for i:=1 to n do begin
    read(fi, a[i]);if ioresult<>0 then iesire('Intrare gresita');
  end;close(fi);
  for i:=1 to n do begin
    str(i,s);
    read(fo, b[i], c[i]);if ioresult<>0 then iesire('Iesire gresita');
    if (a[i]>5)or(b[i]>np[a[i]])or(c[i]+p[a[i],b[i]].l-1>l)
       then iesire('Iesire sau intrare gresita - piesa '+s);
  end;
  for i:=1 to hmax do for j:=1 to lmax do d[i,j]:=0;
  k:=1;
  while (k<=n)and pune_piesa(k,1+k mod 15) do inc(k);
  h:=0;
  for i:=1 to hmax do for j:=1 to lmax do if d[i,j]<>0 then h:=i;
  if (400 div h)>(600 div l) then lat:=600 div j else lat:=400 div h;
  gd:=DETECT;
  gm:=vgahi;
  registerBGIdriver(addr(egavga));
  initgraph(gd,gm,'');
  setcolor(white);
  line(0,0,0,479);
  line(0,479,l*lat+2,479);
  line(l*lat+2,0,l*lat+2,479);
  for i:=0 to h-1 do for j:=0 to l-1 do begin
    setfillstyle(solidfill, d[i+1,j+1]);
    if d[i+1,j+1]<>0 then bar(j*lat+1,478-i*lat,j*lat+lat,478-i*lat-lat);
  end;
  readln;
  closegraph;
end.
================================
Teste (Intrare)
Test 1:
6
12
2
1
3
5
2
5
2
5
4
5
1
2
-----------------------
test 2:
12
3
2
2
2
----------------------
test 3:
6
9
2
3
1
5
1
4
2
5
2
-----------------------
Test 4:
15
15
5
5
5
5
1
2
5
1
4
2
4
4
4
4
5
-----------------------
test 5:
12
42
5
4
2
5
3
5
5
5
5
5
1
1
1
1
5
4
2
5
3
5
5
5
5
5
1
1
1
1
5
4
2
5
3
5
5
5
5
5
1
1
1
1
----------------------
test 6:
6
21
4
5
1
1
3
5
2
4
2
3
2
5
2
3
1
2
1
2
3
2
1
----------------------------
test 7:
14
5
5
1
1
1
1
-----------------------
test 8:
8
6
2
5
5
5
5
4
==============================================
