Problemele de la USACO '99 (USA Computers Olympiad) - Inapoi la ferma
			Traducere: Mihai Scortaru

Pentru toate problemele timpul de executie este de 1 secunda!!!

Problema 1: - Bessie, vino acasa!

	Vitele au iesit fiecare pe pasunea ei preferata (pasunile sunt distincte). E ora cinei. Farmer John suna clopotelul si toate vitele se indreapta spre hambar. Sarcina voastra este de a determina care dintre vite va ajunge prima la hambar. Pentru datele de test va exista intotdeauna o singura cea mai rapida vita.
	Intre mulgeri, fiecare vita  se afla pe propria ei pasune. Exista pasuni pe care nu se afla nici o vita. Pasunile sunt legate printr-un drum de una sau mai multe pasuni. Una sau mai multe pasuni sunt legate de hambar printr-un drum. Toate vitele pot ajunge la hambar si ele se deplaseaza intotdeauna pe cel mai scurt drum. Bineinteles vitele se pot deplasa pe un drum in orice directie si toate se deplaseaza cu aceeasi viteza.
	Pasunile sunt etichetate cu litere de la 'a' la 'z' si de la 'A' la 'Y'. Exista cate o vita in fiecare pasune etichetata cu majuscula. Eticheta hambarului este 'Z'; la inceput in hambar nu se afla nici o vita.

Intrare: -BESSIE.IN
* Pe prima linie se va afla un numar intreg P (1<=P<=10.000), numarul de drumuri care leaga pasunile (si hambarul) intre ele.
* Pe liniile 2..P-1 se afla doua litere si un intreg: etichetele pasunilor legate (eventual a hambarului) si distanta dintre ele:
* Pe prima coloana eticheta primei pasuni (sau a hambarului)
* Pe a doua coloana un spatiu
* Pe a treia coloana eticheta celei de-a doua pasuni (sau a hambarului)
* Pe a patra coloana un spatiu
* Incepand cu  a cincea coloana un intreg x (1<=x<=1000) care indica distanta dintre cele doua entitati (hambar sau pasuni) indicate anterior

Iesire: - BESSIE.OUT
* O singura linie care va contine eticheta pasunii din care pleaca cea mai rapida vita urmata de un spatiu si de lungimea totala a drumului parcurs de acea vita

Exemplu:

BESSIE.IN		BESSIE.OUT
5				B 11
A d 6
B d 3
C e 9
d Z 8
e Z 3









Problema 2: Masurarea laptelui

	Farmer John trebuie sa masoare Q litri de lapte si sa le trimita unui client intr-o sticla mare. El va umple acea sticla exact cu numarul de litri pe care i-a comandat clientul.
	Farmer John a fost intotdeauna chibzuit. El a mers la magazinul pentru vite pentru a cumpara mai multe galeti cu ajutorul carora sa masoare Q litri din enormul sau rezervor de lapte. Deoarece pretul tuturor galetilor este acelasi, sarcina voastra este de a determina galetile de care are nevoie Farmer John pentru a putea masura exact Q litri de lapte. Numarul galetilor trebuie sa fie minim.
	Pentru a masura laptele F.J. poate sa umple complet o galeata cu lapte din rezervor si sa verse laptele in sticla. Daca ar exista o galeata cu capacitatea de un litru atunci F.J. va avea nevoie doar de acea galeata pentru a pune in sticla orice cantitate de lapte. Alte combinatii de galeti nu sunt la fel de convenabile.
	Determinati numarul minim al galetilor care trebuie cumparate avand garantia ca exista cel putin o solutie posibila pentru toate datele de test.

Intrare: - LAPTE.IN
* Pe prima linie numarul intreg Q (1<=Q<=20000) de litri care trebuie masurati
* Pe a doua linie numarul P (1<=P<=100) ale galetilor care se afla in magazin
* Pe liniile 3..P+2 numere intregi indicand capacitatile galetilor din magazin, capacitatea unei galeti este un numar intreg cuprins intre 1 si 10000

Iesire: - LAPTE.OUT
* O singura linie care contine numarul minim al galetilor necesare pentru masurarea laptelui urmat de o lista ordonata crescator care contine capacitatile galetilor necesare

Exemplu:

LAPTE.IN			LAPTE.OUT
11					2 3 5
3
3
5
7

Problema 3: - Dieta sanatoasa

	Farmer John se mandreste cu faptul ca are cele mai sanatoase vite
        de lapte din lume. El stie continutul in vitamine al unei linguri
        din fiecare sortiment de hrana si necesarul minim de vitamine al
        vitelor. Scopul vostru este de a-l ajuta pe Farmer John sa-si
        hraneasca vitele astfel incat acestea sa ramana sanatoase minimizand
        numarul de linguri pe care trebuie sa le foloseasca pentru o vita.
	Dandu-se necesarul zilnic al fiecarui tip de vitamina pentru o vita,
        identificati combinatia de linguri de hrana pentru ca necesarul minim
        de vitamine sa fie indeplinit.
	Vitaminele sunt masurate in unitati intregi. Vitele pot fi hranite
        cu cel mult o lingura din fiecare tip de hrana. Se garanteaza
        existenta unei solutii pentru toate datele de test.

Intrare: - DIETA.IN
* Pe prima linie numarul V (1<=V<=25) al tipurilor de vitamine
* Pe a doua linie V intregi din intervalul [1,1000] reprezentand
minimul necesar din fiecare dintre cele V vitamine
* Pe a treia linie numarul G (1<=G<=15) al tipurilor de hrana disponibile
* Pe liniile 4..G+3 V intregi din intervalul [0,1000] cantitatea din
fiecare vitamina pe care o contine tipul de hrana respectiv. Prima
dintre cele G linii descrie tipul de hrana #1, a doua linie descrie
tipul #2 si asa mai departe.

Iesire: - DIETA.OUT
* O singura linie continand numarul minim de linguri necesare, urmat
de o lista ordonata crescator continand tipurile de hrana pe care le
va primi o vita

Exemplu:

DIETA.IN			DIETA.OUT
4					2 1 3
100 200 300 400
3
50 50 50 50
100 300 200 300
900 150 389 399


Problema 4: - Un hambar mare

	Farmer John doreste sa amplaseze un hambar mare de forma patrata
        pe terenul de forma patrata al fermei sale. Lui nu-i place sa taie
        copaci la ferma sa si vrea sa gaseasca o locatie pentru hambarul
        sau care sa-i permita sa-l construiasca numai pe teren care nu
        are copaci pe el. Pentru scopurile noastre, terenul lui a fost
        impartit in N*N parcele. Intrarea contine o lista cu parcelele
        care contin copaci. Sarcina voastra este de a determina cel mai
        mare hambar de forma patrata care poate fi amplasat pe teren fara
        sa fie nevoie ca unii copaci sa fie taiati. Laturile hambarului
        trebuie sa fie paralele cu axele orizontala si verticala.

Exemplu:

	Sa consideram urmatoarea reprezentare a terenului lui Farmer John
        unde '.' reprezinta o parcela care nu contine copaci, iar '#' o
        matrice care contine copaci.

	1	2	3	4	5	6	7	8
1	.	.	.	.	.	.	.	.
2	.	#	.	.	.	#	.	.
3	.	.	.	.	.	.	.	.
4	.	.	.	.	.	.	.	.
5	.	.	.	.	.	.	.	.
6	.	.	#	.	.	.	.	.
7	.	.	.	.	.	.	.	.
8	.	.	.	.	.	.	.	.

	Cel mai mare hambar are dimensiunea 5*5 si poate fi amplasat
        in oricare dintre cele doua locatii din partea din dreapta-jos
        a matricei.

Intrare: - HAMBAR.IN
* Pe prima linie doua numere intregi N (1<=N<=200) si T (1<=T<=500)
 reprezentand numarul de parcele de pe o latura, respectiv numarul
 parcelelor care contin copaci.
* Pe liniile 2..T+1 doua numere intregi din intervalul [1,n] indicand
linia si coloana unei parcele care contine copaci

Iesire: - HAMBAR.OUT
* O singura linie continand lungimea maxima a unei laturi a hambarului

Exemplu:

INPUT.TXT				OUTPUT.TXT
8 3					5
2 2
2 6
6 3









Problema 5: - Trasee ale vitelor

	Farmer John are un numar de pasuni pe ferma sa. Drumuri pentru vite
        leaga o pasune cu anumite alte pasuni. Dar, in prezent, exista cel
        putin doua pasuni care nu pot fi legate printr-o secventa de drumuri
        pentru vite.
	Farmer John ar dori sa creeze un drum pentru vite intre o noua
        pereche de pasuni pentru ca mai multe pasuni sa poata fi legate
        printr-o secventa de drumuri pentru vite.
	Intr-o multime de pasuni conectate, 'diametrul' este definit ca
        fiind cea mai mare distanta dintre cele mai scurte distante dintre
        toate perechile de pasuni. Sa consideram cele cinci pasuni de mai
        jos, cu drumurile pentru vite marcate printr-o linie:

	    15,15   20,15
		 D	    E
		 *-------*
		 |     _/|
		 |     _/  |
		 | _/    |
		 |/      |
   *-------*-------*
   A       B       C
 10,10   15,10   20,10

	7Diametrul acestei multimi de pasuni din ferma este aproximativ 12.07106, deoarece cel mai lung drum minim intre perechile de pasuni este cel de la A la E (care include multimea de puncte {A,B,E}). Oricare alte doua pasuni sunt mai apropiate daca sunt legate prin secvente optime de drumuri pentru vite.
	Sa presupunem ca o alta multime de pasuni sunt conectate dupa cum urmeaza:

	            20,15
		 	    F
		         *
		       _/|
		  	_/  |
		   _/    |
		  /      |
           *-------*
           G       H
         25,15   30,10

	In acest scenariu Farmer John ar trebui sa adauge un drum pentru vite intre o pasune din multimea {A,B,C,D,E} si una din multimea {F,G,H} astfel incat multimea rezultata de pasuni {A,B,C,D,E,F,G,H} sa aiba un diametru cat mai mic.
	Observati ca drumurile pentru vite nu se intersecteaza si nu sunt conectate prin intersectia unuia cu altul; ele sunt legate numai in punctele in care se afla pasunile.
	Intrarea contine pasunile, locatiile lor si o matrice simetrica de "adiacenta" care indica daca doua pasuni sunt legate printr-un drum pentru vite. Nu se considera ca o pasune este legata cu ea insasi. Iata o matrice de adiacenta pentru pasunile {A,B,C,D,E,F,G,H} descrise anterior:






		A	B	C	D	E	F	G	H
	A	0	1	0	0	0	0	0	0
	B	1	0	1	1	1	0	0	0
	C	0	1	0	0	1	0	0	0
	D	0	1	0	0	1	0	0	0
	E	0	1	1	1	0	0	0	0
	F	0	0	0	0	0	0	1	0
	G	0	0	0	0	0	1	0	1
	H	0	0	0	0	0	0	1	0

	Alte matrice de adiacenta pot permuta linii sau coloane folosind o alta ordine decat cea alfabetica pentru a arata legaturile intre pasuni. Datele de intrare nu contin nici o denumire pentru pasuni.
	Datele de intrare vor contine cel putin doua pasuni care nu sunt legate printr-o secventa de drumuri pentru vite.
	Determinati o modalitate de a conecta exact doua pasuni cu un drum pentru vite pentru ca noua configuratie obtinuta sa aiba cel mai mic diametru posibil. Furnizati ca iesire cel mai mic diametru posibil.

Intrare: - DRUM.IN
* Pe prima linie un intreg N (1<=N<=150) indicand numarul pasunilor
* Pe liniile 2..N+1 cate doi intregi X si Y (0<=X,Y<=100000) indicand coordonatele X si Y ale pasunilor; nu exista doua pasuni care sa aiba aceleasi coordonate
* Pe liniile N+2..2*N+1 cate N intregi (0 sau 1) separati printr-un spatiu care reprezinta  matricea de adiacenta asa cum a fost ea descrisa anterior.

Iesire: - DRUM.OUT
* O singura linie continand diametrul pasunilor unite. Tipariti rezultatul cu exact 6 cifre zecimale. Nu efectuati rotunjiri speciale asupra iesirii.

Exemplu:

DRUM.IN		DRUM.OUT
8				22.071068
10 10
15 10
20 10
15 15
20 15
30 15
25 10
30 10
0 1 0 0 0 0 0 0
1 0 1 1 1 0 0 0
0 1 0 0 1 0 0 0
0 1 0 0 1 0 0 0
0 1 1 1 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 0 0 1 0 1
0 0 0 0 0 0 1 0

[Rezultatul exact este apropiat de 22.071067811865475244 si ar putea fi afisat si ca 22.071067.]



O problema de la CIL'99 (Concours d'Informatique Louxembourgois)
Traducere: Gabriela Stroe
Problema 6: - Arbori  (Timp de executie: 1 secunda)

	Problema se ocupa de transportul arborilor taiati dintr-o padure. Sa consideram urmatorul ex:

		B	0	0	1	1
		B	0	0	0	0
		B	0	0	0	0
		1	1	0	0	0
		E	E	E	0	0

	Cele trei litere 'B' reprezinta un arbore taiat de "lungime" 3. Zerourile reprezinta un spatiu liber, iar cifrele 1 indica un copac netaiat inca. Literele 'E' indica pozitia finala a copacului 'BBB'. Numarul literelor 'B' si 'E' este intotdeauna impar.
	Trebuie transportat arborele 'BBB' in pozitia finala 'EEE'. Transportul se face cu ajutorul urmatoarelor instructiuni:
* U - deplasarea arborelui cu o pozitie in sus (up)
* D - deplasarea arborelui cu o pozitie in jos (down)
* R - deplasarea arborelui cu o pozitie spre dreapta (right)
* L - deplasarea arborelui cu o pozitie spre stanga (left)
* T - rotatia arborelui cu 90 in jurul centrului sau; rotatia se face in sensul acelor de ceasornic (turn)

	Diferitele deplasari nu se pot face daca un arbore netaiat inca obstructioneaza drumul. De exemplu in urmatoarea configuratie
	
	0	0	0	1	1
	0	0	B	0	0
	0	0	B	0	0
	1	1	B	0	0
	E	E	E	0	0

sunt permise miscarile U, D si R, dar L si T sunt imposibile datorita faptului ca exista un copac care obstructioneaza drumul.

Intrare: - ARBORE.IN
* Pe prima linie dimensiunea N a padurii (1<=N<=100)
* Urmatoarele linii prezinta starea padurii

Iesire: - ARBORE.OUT
* Pe o singura linie o secventa de miscari prin care arborele poate ajunge in pozitia finala

Exemplu:

ARBORE.IN			ARBORE.OUT
5					RRDDRTDLL
B 0 0 1 1
B 0 0 0 0
B 0 0 0 0
1 1 0 0 0
E E E 0 0

Exista si alte solutii posibile.
