Fișierul intrare/ieșire | bombon.in, bombon.out | Sursă | Olimpiada locala 2012, Clasa a 10-a |
---|---|---|---|
Autor | autor necunoscut | Adăugată de | Ioana Bica • ioanab |
Timp de execuție pe test | 0.1 sec | Limită de memorie | 2048 KB |
Scorul tău | N/A | Dificultate | N/A |
Vezi soluțiile trimise | Statistici
Bombon
Într-o cutie de bomboane sunt dispuse pe n linii cu câte m bomboane pe fiecare linie, n*m bomboane de tipuri diferite numerotate de la 1 la n*m. Andreea observă că bomboanele nu sunt dispuse pe linii în ordinea crescătoare a numerelor lor, și dorește să le rearanjeze astfel încât pe prima linie să se afle, în ordine, bomboanele 1, 2, ..., m, pe linia a doua să se afle, în ordine, bomboanele m+1, m+2, ..., 2*m și așa mai departe până pe ultima linie, unde să se afle, în ordine, ultimele m bomboane.
Andreea își propune să aducă bomboanele la ordinea dorită având voie să facă următoarele mutări:
- Să ia în orice moment o singură bomboană și să o țină în mână;
- Să mute orice bomboană de pe poziția pe care se află pe o altă poziție liberă (neocupată de altă bomboană) din cutie;
- Să pună în orice moment bomboana din mână pe o poziție liberă din cutie.
Andreea dorește să facă rearanjarea bomboanelor în cutie cu cât mai putine mutari.
Cerinta
Cunoscându-se numărul de linii și de coloane cu bomboane și dispoziția inițială a bomboanelor în cutie, să se determine numărul minim de mutări necesare pentru a rearanja bomboanele în cutie.
Date de intrare
Prima linie bombon.in conține numerele n și m de linii și respectiv de coloane ale cutiei.
Liniile 2, 3, ..., n+1 conțin câte m numere naturale, separate prin câte un spațiu, reprezentând numerele de ordine ale bomboanelor conform dispunerii inițiale a bomboanelor în cutie.
Date de ieșire
În fișierul bombon.out se va scrie numărul minim de mutări prin care bomboanele pot fi rearanjate în ordinea crescătoare a numerelor lor de ordine.
Restricții
- 1 ≤ n, m ≤ 200
- Cele n*m numere sunt valori distincte din mulțimea {1, 2, ..., n*m}
Exemplu
bombon.in | bombon.out |
---|---|
3 4 1 2 4 12 5 6 7 8 3 10 11 9 |
5 |
Explicație
Datele corespund desenului. Cele 5 mutări pot fi:
1) se ia bomboana 9;
2) se mută bomboana 12 la locul ei;
3) se mută bomboana 4 la locul ei;
4) se mută bomboana 3 la locul ei;
5) se pune bomboana 9 (din mână) la locul ei.