Concurs



Se consideră un joc care se desfășoară pe o tablă sub formă de triunghi echilateral cu latura n. În figura alăturată este prezentată o tablă cu latura 7. Se observă că pe tabla de joc se află n * (n + 1) / 2 puncte de intersecție în care se află scobituri. La început, în unele dintre scobiturile de pe tabla de joc se vor afla bile. Scobiturile vor fi numerotate de la 1 la n * (n + 1) / 2 de sus în jos și de la stânga la dreapta. Jocul constă din mai multe mutări și pentru fiecare mutare există o singură regulă: o bilă de pe poziția i poate sări peste o bilă de pe poziția j și va ajunge într-o locație liberă k vecină poziției j, dacă poziția i este vecină cu poziția j; pozițiile i, j și k se află pe același segment. După efectuarea unei astfel de mutări bila de pe poziția j va fi eliminată de pe tabla de joc. Procedeul continuă până în momentul în care nu se mai pot efectua mutări. Ideea jocului este aceea de a rămâne cu cât mai puține bile pe tabla de joc. Cunoscând latura n a tablei de joc și amplasamentul inițial al bilelor, se cere să se determine mutările care trebuie efectuate astfel încât să se ajungă într-o configurație care conține cât mai puține bile.

Fișierul de intrare GAME.IN conține pe prima linie două numere întregi strict pozitive n și m separate printr-un singur spațiu, care reprezintă latura tablei de joc, respectiv numărul de scobituri de pe tabla de joc în care se află bile. Pe următoarea linie se află m numere întregi strict pozitive separate prin câte un spațiu, care reprezintă numerele de ordine ale scobiturilor care conțin bile.

Fișierul de ieșire GAME.OUT va conține cel mult m - 1 linii. Pentru fiecare mutare se va se afla pe câte o linie, o pereche formată din două numere naturale strict pozitive i și j, separate prin spațiu, care reprezintă numărul de ordine al scobiturii din care se ia o bilă și numărul de ordine al scobiturii care conține bila peste care se sare. Mutările se vor trece în fișier în ordinea în care se efectuează.

4 <= N <= 20;
1 <= m < n * (n + 1) / 2;
fișierul de ieșire va conține cel mult m - 1 linii.

GAME.IN
4 5
4 5 6 7 8

GAME.OUT
8 5
7 4
6 3
1 2
Vom considera că pentru fiecare test, se vor putea obține cel mult X puncte.     Concurenții care vor găsi cea mai mică valoare NrMin pentru numărul de bile rămase, vor primi X puncte pentru testul respectiv.
    Ceilalți concurenți, care au efectuat mutări corecte, dar numărul total al bilelor rămase pe tablă este Nr > NrMin, vor obține X * NrMin / Nr puncte pentru testul respectiv. Această valoare va fi aproximată cu două zecimale exacte.
    Punctajul final va fi obținut prin adunarea punctajelor de la fiecare test și rotunjirea acestuia la cel mai apropiat număr întreg.
    Dacă mutările efectuate nu sunt corecte, concurenții nu vor primi nici un punct pentru testul respectiv.
    De exemplu, dacă pentru un test se pot obține cel mult 5 puncte, cel mai bun rezultat obținut de un concurent constă într-o succesiune de mutări în urma cărora pe tablă rămân 2 bile, iar un alt concurent obține o succesiune de mutări în urma cărora pe tablă rămân 4 bile, atunci, pentru testul respectiv, punctajul concurentului va fi de 5 * 2 / 4 = 2.5 puncte.