== include(page="template/taskheader" task_id="antitero") ==
Poveste si cerinta...
Cei $N$ membri ai unei echipe speciale de lupta antitero au fost trimisi intr-o misiune. Prima faza a acesteia implica deplasarea lor in anumite pozitii. Astfel, fiecare membru are o pozitie initiala si trebuie sa ajunga intr-o pozitie finala, eventual trecand prin pozitii intermediare. Dificultatea principala consta in faptul ca in zona respectiva se afla amplasati $P$ soldati ai unei grupari teroriste. Acestia nu se deplaseaza, dar pot ameninta anumite pozitii; un soldat din echipa speciala nu poate trece printr-o pozitie amenintata sau printr-o pozitie in care se afla un terorist (viu). Solutia poate fi eliminarea unora dintre teroristi.
Daca este posibil, sa se elaboreze un plan pentru terminarea misiunii.
h2. Date de intrare
...
Fisierul de intrare $antitero.in$ contine:
* pe prima linie $3$ numere $X N P$, unde $X$ reprezinta numarul de pozitii din zona respectiva, iar $N$ si $P$ au semnificatiile de mai sus
* pe urmatoarele $X$ linii, o matrice $X*X$, care precizeaza pozitiile conectate intre ele (drumurile sunt cu dublu sens)
* pe urmatoarele $N$ linii sunt precizate, pentru fiecare soldat din echipa speciala, punctul de plecare si destinatia
* pe linia urmatoare se dau pozitiile celor $P$ soldati inamici
* pe urmatoarele linii pana la sfarsitul fisierului se dau perechi $i j$ cu semnificatia ca un soldat aflat in punctul $i$ poate impusca un inamic aflat in punctul $j$. Perechile $i j$ si $j i$ nu vor exista concomitent in fisierul de intrare.
h2. Date de iesire
...
Fisierul de iesire $antitero.out$ va contine planul misiunii. Liniile acestuia au urmatorul format:
* $"Success"$ - prima linie
* $M i j$ - soldatul $i$ al echipei antitero se deplaseaza in pozitia $j$ (fara a se preciza pozitiile intermediare)
* $E i j$ - soldatul $i$ il elimina pe teroristul $j$.
Actiunea trebuie prezentata cronologic. In cazul in care misiunea nu poate fi terminata se va afisa doar mesajul $"Mission aborted"$.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $1 ≤ X ≤ 100$
* $1 ≤ N ≤ 10$
* $1 ≤ P ≤ 20$
* In punctele initiale nu se gasesc teroristi si ele nu sunt amenintate de acestia.
* Mai multi soldati pot fi in aceeasi pozitie simultan. Afirmatia este valabila si pentru teroristi.
* Un test pentru care exista solutie este picat daca:
** cel putin una din liniile din fisierul de iesire nu respecta formatul anterior
** o linie $M$ trimite un soldat intr-un punct care nu ii este accesibil, sau
** o linie $E$ 'elimina' un terorist care nu este plasat intr-un punct in care soldatul respectiv poate trage, sau care a fost eliminat anterior, sau
** dupa terminarea mutarilor precizate cel putin un soldat nu se afla in pozitia sa finala.
h2. Exemplu
table(example). |_. antitero.in |_. antitero.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|8 2 2
0 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0
1 0 0 0 1 0 0 0
0 1 0 0 0 1 0 0
0 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
1 5
2 6
7 8
7 3
4 7
|Success
M 2 4
E 2 1
M 1 5
M 2 6
|
h3. Explicatie
...
Teroristii se afla amplasati in $7$ si $8$, unul din soldati trebuie sa ajunga din $1$ in $5$ iar celalalt din $2$ in $6$. Din punctul $7$ se poate elimina un inamic aflat in $3$, iar din $4$ un inamic aflat in $7$.
Soldatul $2$ se deplaseaza in pozitia $4$. Soldatul $2$ il elimina pe teroristul $1$. Soldatul $1$ ajunge in $5$. Soldatul $2$ ajunge in $6$.
== include(page="template/taskfooter" task_id="antitero") ==
