Aliniere
Limbajele de programare acceptate: Pascal, C și C++
Compilatoarele utilizate: Borland Pascal 7.0 și Borland C++ 3.1
Descrierea problemei
Un grup de n războinici elfi stau
aliniați în linie dreaptă în fața conducătorului lor. Acesta nu e
mulțumit de ceea ce vede; războinicii nu sunt așezați în ordinea
înălțimii.
Căpitanul cere câtorva războinici să iasă din
rând, astfel ca cei rămași, fără a-și schimba locurile, doar
apropiindu-se unul de altul (pentru a nu rămâne spații mari între ei)
să formeze un șir în care fiecare războinic vede privind de-a lungul
șirului, cel puțin una din extremități (stânga sau dreapta).
Un războinic vede o extremitate dacă între el
și capătul respectiv nu există un alt războinic cu înălțimea mai mare
sau egală cu a lui.
Așadar, trebuie determinat numărul minim de
războinici care trebuie să părăsească formația, astfel încât șirul
rămas să respecte condiția impusă de conducător.
Date de intrare
Prima linie a fișierului de intrare INPUT.TXT conține numărul n al războinicilor din șir.
Fiecare dintre următoarele n linii va conține înălțimea unui războinic din șir. Aceste linii vor respecta ordinea amplasării inițiale a războinicilor.
Date de ieșire
Fișierul de ieșire OUTPUT.TXT trebuie să conțină pe prima linie numărul k al războinicilor care trebuie să părăsească șirul.
Pe fiecare dintre următoarele k linii se va afla numărul de ordine al unui războinic care trebuie să părăsească șirul.
Aceste numere vor fi scrise în ordine crescătoare.
Restricții și precizări
numărul războinicilor din șir este cuprins între 2 și 1000;
înălțimile războinicilor sunt numere reale, cu cel mult 5 zecimale, cuprinse între 1 și 10;
dacă există mai multe soluții va putea fi aleasă oricare dintre ele.
Exemplu
INPUT.TXT
8
1.86
1.86
1.30621
2
1.4
1
1.97
2.2
OUTPUT.TXT
4
1
3
7
8
Timp de execuție: 2 secunde/test
|