Fișierul intrare/ieșire bombon.in, bombon.out Sursă Olimpiada locala 2012, Clasa a 10-a
Autor autor necunoscut Adăugată de avatar ioanab 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
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 2 categorii