Enunț
La un târg, Mara și Dinu împart un șir de cutii cu jetoane. Cutiile sunt prinse într-un suport și pot fi scoase numai de la unul dintre cele două capete. Mara începe, apoi cei doi mută alternativ, până când nu mai rămâne nicio cutie. Jetoanele din cutia luată se adaugă la scorul jucătorului.
Cerință
Ambii jucători își aleg mutările optim, cunoscând toate valorile. Determină diferența finală dintre scorul primului jucător și scorul celui de-al doilea. Primul urmărește să maximizeze această diferență, iar al doilea să o minimizeze. Rezultatul poate fi negativ.
Date de intrare
Se citește n, apoi cele n valori ale cutiilor, în ordinea din suport.
Date de ieșire
Afișează un singur număr întreg: scorul primului jucător minus scorul celui de-al doilea, în cazul jocului optim.
Restricții
1 ≤ n ≤ 12; 1 ≤ fiecare valoare ≤ 10. La o mutare se ia exact o cutie dintr-un capăt al șirului rămas. Niciun jucător nu poate sări peste tură.
Explicație
În primul exemplu, ambii jucători pot obține câte 6 jetoane, deci diferența este 0. Un șir de mutări optime este: Mara ia 3 din dreapta, Dinu ia 2 din stânga, Mara ia 1 din stânga, Dinu ia 4 din stânga, Mara ia ultimul 2. În al doilea exemplu există o singură cutie, luată de Mara.
Observații
Selecție Algo25 pentru pregătirea interviurilor: programare dinamică.
Reper tematic pentru pregătire: https://www.hackerrank.com/interview/interview-preparation-kit
Exemple
2 EXEMPLEExemplul 1
Exemplul 1, reprezentat vizual. La o mutare se poate lua numai valoarea din capătul stâng sau din capătul drept al șirului rămas.Mărește schema ↗Date de intrare
5
2 1 4 2 3
Date de ieșire
0
Exemplul 2
Date de intrare
1
1
Date de ieșire
1
Ai nevoie de un indiciu?
Descoperă doar cât îți trebuie. Indiciile nu scad punctajul.
Trimite o soluție
Se verifică autentificarea…
Deschide atelierul cu sugestii și teste locale în 4 limbaje →