Baraj I

			Olimpiada Nationala de Informatica
			   Timisoara, 23-30 martie 1997
 
 				BARAJ	Ziua 1, 
				Problema 1
 
BEDUINI

  Doua oaze A si B se gasesc in desert la distanta de n zile de mers una de 
cealalta. O caravana formata din k beduini si un emir trebuie sa traverseze 
desertul de la oaza A la oaza B. In desert emirul si beduinii beau zilnic 
cate 1 litru de apa fiecare. Fiecare beduin poate sa transporte cel mult x 
litri de apa. Emirul nu transporta apa.
  In oaza A exista apa in cantitate suficient de mare.
  Deplasarea caravanei se va face pe baza urmatoarelor reguli:
- pe traseu se pot crea depozite de apa; fiecare depozit trebuie pazit de un 
  singur beduin (cat timp in depozit se gaseste apa);
- membrii caravanei se deplaseaza intr-un singur grup impreuna cu emirul, 
  exceptand cei care stau de paza;
- toti membrii caravanei initiale trebuie sa ajunga impreuna (in aceeasi zi) 
  in oaza B; 
- apa poate fi transportata doar din oaza A; din oaza B nu se va lua apa 
  (chiar daca astfel s-ar minimiza numarul de zile);
* in oaza B fiecare beduin trebuie sa ajunga cu 0 litri de apa.
* pentru a asigura in depozitul Di cantitatea de apa necesara avansarii, 
  membrii caravanei se pot intoarce in depozitul Di-1 (sau oaza A, dupa caz), 
  respectand regulile de deplasare enuntate mai sus;
  - miscarile caravanei pot avea loc conform urmatoarei scheme:

  A   D1
  [<->]
       
      D2   D3
      [<->]
              D2   D3
              [<->]
                     D2   D3
                     [<->]

 
  Sa se planifice modul in care se va traversa desertul pentru a ajunge din 
A in B intr-un numar minim de zile.
 
DATE DE INTRARE:
  Fisierul de intrare INPUT.TXT contine trei numere, separate printr-un 
spatiu reprezentand numarul de beduini (k), distanta in zile n (1<=n<=50) 
dintre cele doua oaze si cantitatea maxima de apa (x) care poate fi 
transportata de un beduin la un moment dat. Aceste date vor avea asemenea 
valori incat rezultatele se vor putea reprezenta pe 4 octeti.

DATE DE IESIRE:
  Rezultatul se scrie in fisierul OUTPUT.TXT care va avea urmatoarea structura:
- pe prima linie se va scrie un numar intreg, reprezentand numarul minim de 
  zile in care se va traversa desertul;
- pe a doua linie se va scrie cantitatea totala de apa care se va lua din 
  oaza A;
- pe a treia linie se va scrie numarul depozitelor nr create in desert;
Daca nr<=0, atunci:
- pe urmatoarea linie se va scrie distanta de la oaza A pana la primul 
  depozit si cantitatea de apa existenta in acesta in ziua in care se incepe 
  deplasarea spre urmatorul depozit; cele doua numere se despart printr-un 
  spatiu;
- pe urmatoarele nr-1 linii se va scrie distanta de la depozitul anterior pana
  la cel curent, si cantitatea de apa existenta in acesta in ziua in care se 
  incepe deplasarea spre urmatorul depozit; (cele doua numere se despart 
  printr-un spatiu); corespunzator ultimului depozit, aceasta cantitate 
  reprezinta apa necesara traversarii drumului pana la oaza B; 
- pe ultima linie se va scrie distanta intre ultimul depozit si oaza B.
Daca nr=0, atunci in fisierul de iesire vor apare doar primele trei linii, 
avand continutul precizat mai sus.
 
Observatii:
- in cazul in care nu se poate traversa desertul, in fisierul de iesire se 
va scrie: 'Imposibil'
 
Exemple:
 
Exemplul1	Exemplul 2	Exemplul 3
 
INPUT.TXT
OUTPUT.TXT
INPUT.TXT
OUTPUT.TXT
INPUT.TXT
OUTPUT.TXT
2 7 10
9
2 8 8
Imposibil
2 5 10
5
 
27
 
 
 
15
 
1
 
 
 
0
 
1 18
 
 
 
 
 
6
 
 
 
 

 
Timp maxim de executare pentru un test: 5 secunde
 
Punctaj: 50 puncte . 

				  BARAJ I
				 PROBLEMA 2
PROINFO							Punctaj:  50 puncte.

  Postul de televiziune ProInfo are posibilitatea sa-si infiinteze posturi 
locale in n (1<=n<=200) localitati, ale caror coordonate, specificate 
relativ la un sistem de coordonate ortogonal cu centrul in coltul stanga jos 
al unei harti de dimensiuni L x H (1<=L, H<=30000), sunt cunoscute. 
Cum orice intentie trebuie realizata cu cheltuieli minime, trebuie calculata
cu precizie mai buna decat 0.01 puterea minima necesara pentru fiecare statie 
de emisie, astfel incat sa acopere intreaga zona arondata postului local 
corespunzator. Mai exact, zona arondata postului local Pi este formata din 
totalitatea punctelor din planul hartii care sunt mai apropiate de postul 
local Pi decat de orice alt post, iar puterea necesara statiei de emisie este 
direct proportionala cu suprafata zonei arondate postului, factorul de 
proportionalitate fiind egal cu 1 (unu) indiferent de conditiile de relief, 
clima, etc. 
Restrictii de intrare / iesire:
Din fisierul de intrare cu numele INPUT.TXT  se citesc:
* de pe prima linie un numar natural n, care reprezinta numarul de posturi;
* de pe urmatoarele n linii, cate o pereche de numere reale, care reprezinta
  coordonatele localitatilor in care se pot infiinta posturi locale 
  (abscisa si ordonata, separate prin spatiu);
* de pe ultima linie numerele naturale  L si H,  care  reprezinta 
  dimensiunile hartii.
In fisierul de iesire OUTPUT.TXT  veti afisa in ordinea localitatilor din 
fisierul de intrare ariile celor n zone, fiecare pe cate o linie, cu 2 
zecimale exacte.

Exemplu:
Pentru fisierul de intrare:
3
2 2
6 2
4 4
10 5
Fisierul de iesire va fi:
15.50
25.50
9.00


	NOTA:
	Problema trebuie citita de cel putin 3 ori pentru a putea fi 
	inteleasa corect  (macar o data ! )
	Timp de executie: maxim 15 secunde / test.