OLIMPIADA DE INFORMATICA
FAZA JUDETEANA
CLASA A XII-A
08.03.1998
Problema 1 (Grila)
Se da o grila cu n linii si m coloane (nxm<=100). Patratele grilei sunt "arse", 
libere sau pot  contine numere. 
Sa se completeze patratele libere cu numere existente in grila astfel incat:
numarul i sa apara pe grila in total de i ori;
patratele continand acelasi numar trebuie sa se invecineze intre ele cel putin 
de-a lungul unei laturi, constituind impreuna un singur sector.
Fisierul de intrare, IN.TXT, contine:
pe prima linie n si m;
pe urmatoarele n linii grila, avand spatiile libere reprezentate prin 0, 
iar patratele arse prin valori negative.
Fisierul de iesire, OUT.TXT, contine 
grila completata. 
Obs. Pentru fisierele de test solutia este unica.
Exemplu:
IN.TXT:
4 4
2 0 4 0
0 5 0 0 
0 3 0 -1
-1 0 0 5
OUT.TXT:
2 4 4 4
2 5 5 4
3 3 5 -1
-1 3 5 5
Timp de executie:1 min/test
Problema 2 (Prefix)
Structura unor compusi biologici este reprezentata prin succesiunea 
constituentilor lor. Acesti constituenti sunt notati cu litere mari. 
Biologii sunt interesati sa descompuna o secventa lunga in alte mai 
scurte, numite primitive. Spunem ca o secventa S poate fi descompusa
 intr-un set de primitive P daca exista N primitive p1, ..., pN in 
P, astfel incat concatenarea p1p2...pN a primitivelor sa fie egala 
cu S. Aceeasi primitiva poate interveni de mai multe ori in 
concatenare  si nu trebuie neaparat ca toate primitivele sa fie 
prezente.
Primele M caractere din S se numesc prefixul lui S de lungime M. 
Scrieti un program care primeste la intrare un set de primitive P 
si o secventa de constituenti T. Programul trebuie sa afle lungimea 
celui mai lung prefix al lui T care se poate compune din primitive 
din P.
Datele de intrare apar in doua fisiere. Fisierul INPUT.TXT descrie 
setul de primitive P, iar fisierul DATA.TXT contine secventa de 
examinat. Pe prima linie din INPUT.TXT se afla N, numarul de 
primitive din P (1 <=N<=100). Fiecare primitiva se da pe o linie 
ce contine un sir de litere mari de lungime L (1<=L<=20).
Toate cele n primitive sunt distincte. Fiecare linie din fisierul 
DATA.TXT contine o litera mare pe prima pozitite. El se termina cu
o linie continand un punct. Lungimea secventei este cuprinsa intre
1 si 500 000.
Iesire: Pe ecran se va tipari lungimea celui mai lung prefix din T 
care poate fi compus din primitive din P.
	Timp maxim de rulare: 30
Exemplu:
INPUT.TXT			DATA.TXT
5				A
A				B
AB				A
BBC				B
CA				A
BA				C
				A
				B
				A
 				A
				B
				C
				B
				.
Pe ecran se va tipari numarul 11
