Fişierul intrare/ieşire:bombon.in, bombon.outSursăOlimpiada locala 2012, Clasa a 10-a
AutorAutor NecunoscutAdăugată deioanabIoana Bica ioanab
Timp execuţie pe test0.1 secLimită de memorie2048 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise

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.inbombon.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 sa te autentifici pentru a trimite solutii. Click aici