Candale Silviu (silviu) Jocul cmin constă în a găsi o strategie pentru a deplasa un anumit număr de jetoane identice pe o tablă pătratică, în scopul obţinerii unei configuraţii finale, cu un cost minim.
Tabla are n*n celule, aflate la intersecţia a n rânduri numerotate de la 1 la n de sus în jos şi a n coloane, numerotate de la 1 la n de la stânga spre dreapta. Numărul n este întotdeauna par.
La momentul iniţial al jocului, pe tablă se găsesc k jetoane în poziţii cunoscute. Fiecare jeton poate fi deplasat doar pe verticală, din celula iniţială într-o celulă finală neocupată de un alt jeton. Un jeton poate fi deplasat chiar dacă între poziţia sa iniţială şi cea finală există celule ocupate de către alte jetoane.
Costul deplasării unui jeton pe verticală, din celula curentă într-o celulă adiacentă este 1 (o unitate). Un jeton poate fi mutat de mai multe ori. Jucătorul decide ordinea deplasării jetoanelor. Acesta poate să mute 0, 1 sau chiar toate jetoanele pentru a termina jocul cu un cost total minim. Costul total este suma costurilor deplasării tuturor jetoanelor.
Jocul cmin se termină când diferenţa în valoare absolută dintre numărul de jetoane care se află pe primele n/2 rânduri (cele de sus) şi numărul de jetoane care se găsesc pe ultimele n/2 rânduri (cele de jos), este minimă.
Cerința
Cunoscând numărul n de rânduri şi de coloane ale tablei şi poziţiile iniţiale ale jetoanelor, determinaţi costul total minim necesar pentru deplasarea acestora, astfel încât diferenţa în valoare absolută dintre numărul jetoanelor care se vor găsi în final pe primele n/2 rânduri şi numărul jetoanelor care se vor găsi pe ultimele n/2 rânduri, să fie minimă.
Date de intrare
Fișierul de intrare cmin.in conține pe prima linie un număr natural n, par, cu semnificaţia descrisă anterior.
Următoarele n linii descriu configuraţia iniţială a tablei. Fiecare linie conţine câte n valori 1 sau 0, separate prin câte un spaţiu. Valoarea 1 reprezintă o celulă ocupată cu un jeton, iar 0 o celulă liberă.
Date de ieșire
Fișierul de ieșire cmin.out va conține pe prima linie un singur număr natural c, reprezentând costul minim cerut, cu respectarea regulilor jocului cmin.
Restricții și precizări
2 ≤ n ≤ 100(n– număr par)1 ≤ k ≤ n * n
Exemplu:
cmin.in
2 0 0 1 0
cmin.out
0
Explicație
Nu este necesară mutarea nici unui jeton.
Exemplu:
cmin.in
4 1 1 1 1 1 1 0 0 1 0 0 0 0 0 0 0
cmin.out
3
Explicație
O variantă posibilă: Se mută jetonul din celula (2,1) în celula (4,1). Costul este 2. Apoi se mută jetonul din celula (2,2) în celula (3,2). Costul este 1. Suma costurilor este 3.
Altă variantă: se mută jetoanele din celulele (3,1), (2,1), şi (2,2) cu câte o poziţie. Se ajunge în aceeaşi stare finală ca în prima variantă.
Altă variantă: din celula (2,2) în (3,2) şi din celula (1,3) în (3,3).