== include(page="template/taskheader" task_id="ture-impiedicate") ==
Poveste şi cerinţă...
Miruna învaţă şah. Ea a ajuns la piesa tură şi a înţeles că aceasta se poate deplasa doar pe orizontală sau pe verticală. De asemenea, ştie deja că dacă o altă piesă se află în calea unei ture aceasta poate fi atacată.
Miruna i s-a părut că este prea simplă teoria mutării unei ture şi şi-a imaginat următoarea problemă:
Pe o tablă de şah $N * N$ ea aşază la întâmplare $K$ ture. Ea doreşte să mute turele astfel încât, la finalul mutărilor, nicio tură să nu poată ataca altă tură.
După mai multe încercări fetiţa şi-a propus să determine numărul minim de mutări necesare pentru a obţine aşezarea finală a turelor.
Întrucât turele Mirunei sunt mai vechi şi cam împiedicate, ele se pot deplasa doar cu câte o căsuţă (la stânga, dreapta, în sus sau în jos) la fiecare mutare. O tură nu poate sări peste o altă tură şi nici nu poate părăsi tabla de şah.
h2. Date de intrare
Fişierul de intrare $ture-impiedicate.in$ ...
În fişierul de intrare $ture-impiedicate.in$, prima linie va conţine valorile $N$ şi $K$ cu semnificaţia din enunţ.
Pe următoarele $K$ linii se vor afla câte $2$ valori, $l{~i~}$ şi $c{~i~}$, separate printr-un spaţiu, care reprezintă linia şi, respectiv, coloana la care se află tura iniţial.
h2. Date de ieşire
În fişierul de ieşire $ture-impiedicate.out$ ...
În fişierul de ieşire $ture-impiedicate.out$, pe prima linie, se va afişa numărul minim de mutări (valide) pentru a obţine o configuraţie în care nicio tură nu poate ataca o altă tură.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $K ≤ N$
* $1 ≤ c{~i~}, l{~i~} ≤ N$ oricare ar fi $i$ din ${1, 2, ..., K}$
h2. Subtaskuri
table(subtask-uri). |_. Indice |_. Punctaj |_. Restricţii |
| $1$ | $15$ puncte | $N ≤ 9$ |
| $2$ | $15$ puncte | $N ≤ 100$ |
| $3$ | $20$ puncte | $N ≤ 2 000$ |
| $4$ | $50$ puncte | $N ≤ 100 000, K ≤ 2 000$ |
h2. Exemplu
table(example). |_. ture-impiedicate.in |_. ture-impiedicate.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 10 5
2 9
2 8
3 10
10 2
2 9
| 5
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="ture-impiedicate") ==
