Soluții trimise

Rezumat problemă

#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ă.

ID   Utilizator Problema Data încărcării Stare
Jula Diana (magicninja) cmin 24 Decembrie 2024, 17:50 Evaluare finalizată 100
Jula Diana (magicninja) cmin 24 Decembrie 2024, 17:46 Evaluare finalizată 36
Jula Diana (magicninja) cmin 24 Decembrie 2024, 17:45 Evaluare finalizată 36
POPESCU ANDREI (andreip99) cmin 15 Septembrie 2024, 16:18 Evaluare finalizată 100
Diaconu Andreea (Andreea0210) cmin 08 Iulie 2024, 19:10 Evaluare finalizată 0
Mr Teddy (MrTeddy) cmin 05 Aprilie 2024, 23:13 Evaluare finalizată 100
Raileanu Alexandru (AlexandruR2008) cmin 04 Aprilie 2024, 06:58 Evaluare finalizată 100
Toncea Andrei (andrei170) cmin 20 Ianuarie 2024, 19:05 Evaluare finalizată 100
Moldovan Robert (use KN) (moldovan_robert_lol) cmin 08 August 2023, 01:05 Evaluare finalizată 100
​ ​ (TERRAFXRM) cmin 08 August 2023, 01:05 Evaluare finalizată 100
​ ​ (TERRAFXRM) cmin 08 August 2023, 00:52 Evaluare finalizată 69
Dracea Andora (Andora_fan) cmin 07 August 2023, 18:37 Evaluare finalizată 100
Adrian Statescu (thinkphp) cmin 04 Iulie 2023, 15:23 Evaluare finalizată 100
Maftei Tudor (TudorMaf) cmin 28 Iunie 2023, 15:30 Evaluare finalizată 100
Maftei Tudor (TudorMaf) cmin 28 Iunie 2023, 15:29 Evaluare finalizată E.C
Moiceanu David (codrinelul) cmin 19 Mai 2023, 15:26 Evaluare finalizată 100
Moiceanu David (codrinelul) cmin 19 Mai 2023, 15:25 Evaluare finalizată 0
Szabo Eva Maria (eva1_618) cmin 12 Mai 2023, 15:58 Evaluare finalizată E.C
Andrei Simion (andrei0simion) cmin 12 Mai 2023, 15:43 Evaluare finalizată 100
Coman Andrei (A_C) cmin 12 Mai 2023, 15:38 Evaluare finalizată 100
Gagea Andrei (Andrei_Gagea08) cmin 12 Mai 2023, 15:33 Evaluare finalizată 100
ilie alexandru (ROSES_ARE_RED_VIOLETS_ARE_BLUE) cmin 12 Mai 2023, 15:30 Evaluare finalizată 0
ilie alexandru (ROSES_ARE_RED_VIOLETS_ARE_BLUE) cmin 12 Mai 2023, 15:29 Evaluare finalizată 0
Thomas Paturan (Thomas_Paturan114) cmin 10 Mai 2023, 08:44 Evaluare finalizată 100
Gheorghe Ruxandra (Ruxxi7) cmin 10 Mai 2023, 01:09 Evaluare finalizată 100
Gheorghe Ruxandra (Ruxxi7) cmin 10 Mai 2023, 01:07 Evaluare finalizată 67
Gheorghe Ruxandra (Ruxxi7) cmin 10 Mai 2023, 00:49 Evaluare finalizată 3
Jula Diana (magicninja) cmin 09 Mai 2023, 23:52 Evaluare finalizată 6
e r i c (Eric_Paturan) cmin 09 Mai 2023, 23:42 Evaluare finalizată 100
Costache Andrada (andrac2) cmin 09 Mai 2023, 21:54 Evaluare finalizată 100
Rosu Dragos (Dragos_Rosu1) cmin 09 Mai 2023, 20:55 Evaluare finalizată 100
Virtopeanu Andrei (Torna3o) cmin 09 Mai 2023, 17:10 Evaluare finalizată 13
Virtopeanu Andrei (Torna3o) cmin 09 Mai 2023, 15:27 Evaluare finalizată 33
Ionica David (Ionica_David) cmin 09 Mai 2023, 10:49 Evaluare finalizată 79
Ionica David (Ionica_David) cmin 09 Mai 2023, 10:49 Evaluare finalizată 0
Ionica David (Ionica_David) cmin 09 Mai 2023, 10:48 Evaluare finalizată 100
Ionica David (Ionica_David) cmin 09 Mai 2023, 10:40 Evaluare finalizată 36
Ionica David (Ionica_David) cmin 09 Mai 2023, 00:17 Evaluare finalizată 30
Ionica David (Ionica_David) cmin 09 Mai 2023, 00:17 Evaluare finalizată 0
Ionica David (Ionica_David) cmin 09 Mai 2023, 00:16 Evaluare finalizată 30
Matei Balaur (mateiUNU) cmin 05 Mai 2023, 17:49 Evaluare finalizată 100
Matei Balaur (mateiUNU) cmin 05 Mai 2023, 17:48 Evaluare finalizată 36
Matei Balaur (mateiUNU) cmin 05 Mai 2023, 17:47 Evaluare finalizată 36
Gorgan Maria (MariaGorgan) cmin 05 Mai 2023, 17:31 Evaluare finalizată 100
Pislaru Luca (Luca_Pislaru) cmin 04 Mai 2023, 10:45 Evaluare finalizată 100
Pislaru Luca (Luca_Pislaru) cmin 04 Mai 2023, 10:44 Evaluare finalizată 36
Pislaru Luca (Luca_Pislaru) cmin 04 Mai 2023, 10:42 Evaluare finalizată 81
Petrescu Victor Gabriel (ito726) cmin 03 Mai 2023, 22:27 Evaluare finalizată 27
Petrescu Victor Gabriel (ito726) cmin 03 Mai 2023, 15:34 Evaluare finalizată 0
Trâmbițaș Alexandru-Luca (Alex_Tr123) cmin 03 Mai 2023, 15:33 Evaluare finalizată E.C