Fişierul intrare/ieşire:harta3.in, harta3.outSursă.com 2009, runda 2
AutorTeodor Anton PripoaeAdăugată deraduzerRadu Zernoveanu raduzer
Timp execuţie pe test0.1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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 B2 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.inharta3.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

Cum se trimit solutii?

remote content