Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2010-03-03 12:44:20.
Revizia anterioară Revizia următoare

Fişierul intrare/ieşire:	harta3.in, harta3.out	Sursă	.com 2009, runda 2
Autor	Teodor Anton Pripoae	Adăugată de	Radu Zernoveanu •raduzer
Timp execuţie pe test	0.05 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Harta3

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, care fac parte din cele N.

Cerinta

Atribuiti coordonate diferite celor N puncte astfel incat sa se respecte cele M relatii, iar distanta intre A si B sa fie cat mai mica.

Date de intrare

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

Date de iesire

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

Restrictii si precizari

2 ≤ N ≤ 10.000
0 ≤ M ≤ 10.000
Pentru fiecare X, Y, D, 1 ≤ D ≤ 100.
Atentie! Se garanteaza ca distanta minima intre A si B ≤ 10.000.
Coordonatele punctelor trebuie sa apartina intervalului [-1.000.000, 1.000.000].
In cazul in care exista mai multe solutii, se poate afisa oricare dintre acestea.
Se garanteaza ca exista solutie!