| 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
Considerăm N puncte pe axa OX având coordonate întregi. Se dau M relaţii de forma X Y D semnificând faptul că X se află la stânga lui Y cu D unitaţi. Se mai dau punctele speciale A şi B, care fac parte din cele N.
Cerinţa
Atribuiţi coordonate diferite celor N puncte astfel încat să se respecte cele M relaţii, iar distanţa între A şi B să fie cât mai mică.
Date de intrare
Fişierul de intrare harta3.in conţine pe prima linie numerele N şi M, cu semnificaţia din enunţ. Pe a doua linie se află punctele A şi B. Urmatoarele M linii conţin câte 3 numere X, Y şi D.
Date de iesire
Fişierul de ieşire harta3.out conţine pe prima linie N numere reprezentând coordonatele pe axa OX a celor N puncte.
Restricţii şi precizari
- 2 ≤ N ≤ 10 000
- 0 ≤ M ≤ 10 000
- Pentru fiecare X, Y, D, 1 ≤ D ≤ 100.
- Atenţie! Se garantează că distanţa minimă între A şi B ≤ 2 400.
- Coordonatele punctelor trebuie să aparţina intervalului [-1 000 000, 1 000 000].
- În cazul în care exista mai multe soluţii, se poate afişa oricare dintre acestea.
- Se garanteaza ca exista soluţie!
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
remote content
