#716
cmin
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ă.
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ă.
Lot Juniori, Resita, 2012
Problema | cmin | Operații I/O |
![]() cmin.in /cmin.out
|
---|---|---|---|
Limita timp | 0.5 secunde | Limita memorie |
Total: 64 MB
/
Stivă 8 MB
|
Id soluție | #43733131 | Utilizator | |
Fișier | cmin.cpp | Dimensiune | 2.21 KB |
Data încărcării | 12 Mai 2023, 15:58 | Scor / rezultat | Eroare de compilare |
cmin.cpp: In function 'int main()': cmin.cpp:10:51: error: storage size of 'v' isn't known int n,i,j,x[101][101],k,sum1=0,sum2=0,sum=0,v[]; ^ cmin.cpp:44:25: error: 'i2' was not declared in this scope for(i2=n/2+1;i2<=n&&!okk;i2++) ^ cmin.cpp:59:21: error: 'cmin' was not declared in this scope cmin+=i; ^ cmin.cpp:72:29: error: 'i2' was not declared in this scope for(i2=n/2;i2>=1&&!okk;i2--) ^ cmin.cpp:89:21: error: 'cmin' was not declared in this scope cmin+=i; ^ cmin.cpp:94:10: error: 'cmin' was not declared in this scope else cmin=0; ^ cmin.cpp:10:27: warning: unused variable 'k' [-Wunused-variable] int n,i,j,x[101][101],k,sum1=0,sum2=0,sum=0,v[]; ^
www.pbinfo.ro permite evaluarea a două tipuri de probleme:
Problema cmin face parte din prima categorie. Soluția propusă de tine va fi evaluată astfel:
Suma punctajelor acordate pe testele utilizate pentru verificare este 100. Astfel, soluția ta poate obține cel mult 100 de puncte, caz în care se poate considera corectă.