Solutia problemei este realizata
prin metoda backtracking. Asezarea punctelor pe
axa
determina un arbore binar īn care se va face
cautarea solutiei. Punctul de
coordonate 0
si cel aflat la distanta maxima citita din
fisierul de intrare,
reprezinta
puncte figurate pe axa.
Tehnica
permite asezarea unui nou punct pe axa (simetric
fata de punctele
extreme)
daca toate celelalte distante pe care le genereaza
fata de punctele
deja
figurate exista. Vectorul a memoreaza distantele
(a[i] indica de cāte ori
apare
distanta i). Odata cu asezarea unui punct pe axa
se va face si
decrementarea elementelor
din a corespunzatoare.
Evident,
daca aceasta actiune nu este posibila se īncearca
pozitia simetrica,
sau se
revine pe un nivel anterior.
|