Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2010-03-03 11:06:10.
Revizia anterioară Revizia următoare
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 |
Vezi solutiile trimise | Statistici
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 ≤ X < Y ≤ N si 1 ≤ D ≤ 1.000.
- Atentie! Se garanteaza ca distanta minima intre A si B ≤ 200.
- 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!
Exemplu
| harta3.in | harta3.out |
|---|---|
| 5 3 1 3 1 2 3 2 4 1 1 5 6 | 0 3 1 4 6 |
Trebuie sa te autentifici pentru a trimite solutii. Click aici
