| Fişierul intrare/ieşire: | mission.in, mission.out | Sursă | Algoritmiada 2014, Runda 1 |
| Autor | Andrei Heidelbacher | Adăugată de |  Heidelbacher Andrei •a_h1926 |
| Timp execuţie pe test | 0.025 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Mission
Zeratul a primit de la Tassadar o misiune foarte importantă: trebuie să distrugă N centre de comandă ale terranilor, numerotate de la 0 la N – 1, cunoscând coordonatele x şi y din plan ale acestora. Iniţial, Zeratul este teleportat în centrul de comandă cu numărul 0, unde va trebui să se întoarcă după ce îşi îndeplineşte misiunea şi distruge toate celelalte centre de comandă. Zeratul se poate deplasa între două centre de comandă numai în linie dreaptă. Terranii sunt prevăzători şi au minat terenul corespunzător întregului plan XOY. Ca urmare, el poate să treacă printr-un punct din plan cel mult odată (cu excepţia centrului de comandă 0, de unde va fi recuperat la finalul misiunii).
Zeratul vă promite o recompensă de 100 de puncte, dacă îi spuneţi în ce ordine să distrugă cele N centre de comandă, astfel încât la final să se întoarcă în centrul de comandă cu indicele 0 şi să nu treacă prin acelaşi punct de mai multe ori.
Date de intrare
Fişierul de intrare mission.in conţine pe prima linie numărul întreg N, semnificând numărul de centre de comandă pe care trebuie să le distrugă Zeratul. Pe următoarele N linii se află câte două numere întregi xi şi yi, reprezentând coordonatele celor N centre de comandă.
Date de ieşire
În fişierul de ieşire mission.out veţi afişa pe prima linie o permutare de lungime N, reprezentând ordinea în care vor fi distruse cele N centre de comandă.
Restricţii
- 3 ≤ N ≤ 1000
- -1.000.000 ≤ xi, yi ≤ 1.000.000
- dacă Zeratul trece printr-un centru de comandă, el este obligat să-l distrugă (deoarece nu mai poate trece a doua oară prin acel centru şi nu şi-ar îndeplini misiunea); acest lucru este valabil inclusiv pentru centrul de comandă 0
- după ce distruge al N-lea centru de comandă din traseul indicat de voi, el se va întoarce în centrul de comandă 0, tot în linie dreaptă
- Zeratul nu poate trece printr-un punct de mai multe ori, chiar dacă a distrus toate centrele de comandă
- dacă există mai multe soluţii, se poate afişa oricare
- oricare trei centre de comandă sunt necoliniare
Exemplu
| mission.in | mission.out |
|---|---|
| 5 0 0 1 1 2 0 0 3 2 3 | 0 3 4 1 2 |
Explicaţie
Un exemplu de permutare care nu respectă cerinţele este {0, 4, 3, 2, 1}, deoarece Zeratul trece prin punctul (1, 1.5) de două ori.
Un alt exemplu de permutare care nu respectă cerinţele este {2, 1, 4, 3, 0}, deoarece Zeratul trece, iniţial, prin centrul de comandă 0 fără să-l distrugă.
