harta3

Harta3

== include(page="template/taskheader" task_id="harta3") ==

Poveste şi cerinţă...

Consideram $N$ puncte pe axa $OX$ avand coordonate intregi. Se dau $M$ relatii de forma $X Y D$ semnificand faptul ca $X$ se afla la stanga lui $Y$ cu $D$ unitati. Se mai dau punctele speciale $A$ si $B$.
 
h2. Cerinta
 
Atribuiti coordonate celor $N$ puncte astfel incat sa se respecte cele $M$ relatii, iar distanta intre $A$ si $B$ sa fie cat mai mica.

h2. Date de intrare

Fişierul de intrare $harta3.in$ ...

Fisierul de intrare $harta3.in$ contine pe prima linie numerele $N$ si $M$, cu semnificatia din enunt. Urmatoarele $M$ linii contin cate 3 numere X, Y si D. Pe ultima linie a fisierului de intrare se afla cele 2 puncte $A$ si $B$.

h2. Date de ieşire

h2. Date de iesire

În fişierul de ieşire $harta3.out$ ...

Fisierul de iesire $harta3.out$ contine pe prima linie $N$ numere reprezentand coordonatele pe axa $OX$ a celor $N$ puncte.

h2. Restricţii

h2. Restrictii si precizari

* $... ≤ ... ≤ ...$

* $2 ≤ N ≤ 1.000$
* $0 ≤ M ≤ 10.000$
* Pentru fiecare X, Y, D, $1 &le; X < Y &le; N$ si $1 &le; D &le; 1.000$.
* **Atentie!** Se garanteaza ca distanta intre $A$ si $B$ &le; $1.000$.
* Coordonatele punctelor trebuie sa apartina intervalului $[-100.000, 100.000]$.
* In cazul in care exista mai multe solutii, se poate afisa oricare dintre acestea.

h2. Exemplu
table(example). |_. harta3.in |_. harta3.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 5 3
  1 2 3
  2 4 1
  1 5 6
  1 3
| 0 3 1 4 6

|
h3. Explicaţie