Lista de probleme 2

O firmă producătoare de software organizează un interviu pentru ocuparea unui post de programator, la care s-au prezentat N candidaţi. Aceştia sunt ordonaţi în funcţie de momentul la care şi-au trimis CV-ul şi numerotaţi cu numere consecutive de la 1 la N. Fiecărui candidat i-a fost realizat în prealabil un profil psihologic şi i s-a determinat nivelul de agitaţie provocat de interviul care urmează să aibă loc, precum şi un sens (crescător sau descrescător) de modificare a acestui nivel. Astfel, la ora la care s-a anunţat începerea interviului (pe care o vom considera momentul 0), fiecare candidat are un nivel de agitaţie iniţial. Pentru fiecare unitate de timp după momentul 0 şi până în momentul în care candidatul este invitat pentru interviu (până atunci el trebuind să aştepte), nivelul său de agitaţie se modifică cu 1: pentru o parte din candidaţi nivelul creşte cu 1 unitate, iar pentru ceilalţi nivelul scade cu 1 unitate. Dacă nivelul de agitaţie a unui candidat ajunge la 0, din acel moment, pentru fiecare unitate de timp următoare, nivelul de agitaţie va creşte cu 1 (se schimbă sensul de modificare a nivelului de agitaţie).

Să se scrie un program care să determine suma totală minimă a nivelelor de agitaţie a candidaţilor la sfârşitul interviului dacă aceștia sunt împărțiți optimal în grupuri.

Pe asfalt este desenat cu cretă un şotron, caroiaj format din n*n căsuţe având aceleaşi dimensiuni (câte n căsuţe pe fiecare din cele n rânduri).

În fiecare căsuţă este scris câte un număr întreg din intervalul [-100, 100]. Fiecare jucător are câte o piatră pe care o aruncă într-o căsuţă a şotronului, şi sărind într-un picior, împinge piatra din căsuţă în căsuţă, pe un anumit traseu astfel încât punctajul obţinut din suma numerelor de pe traseul parcurs să fie cât mai mare.

Numerele din căsuţele şotronului sunt scrise cu două culori albastru şi alb, astfel încât să nu existe două căsuţe alăturate (pe cele patru direcţii Nord, Est, Sud, Vest) având numere scrise cu aceeaşi culoare. Întotdeauna, prima căsuţă din primul rând al şotronului are înscris un număr de culoare albastră.

Se stabilesc apoi, următoarele reguli ale jocului:

• la începutul jocului, piatra poate fi aruncată în oricare căsuţă a şotronului. Din poziţia respectivă jucătorul îşi conduce piatra până la sfârşitul traseului stabilit de el;
• dintr-o căsuţă în care numărul este scris cu albastru, piatra poate fi deplasată doar în căsuţa vecină pe direcţia Nord;
• dintr-o căsuţă în care numărul este scris cu alb, piatra poate fi deplasată doar în căsuţa vecină pe direcţia Est;
• jucătorul poate alege orice căsuţă (inclusiv cea în care a aruncat piatra) pentru a încheia jocul, atâta timp cât piatra nu iese din şotron.

Să se scrie un program care să determine cel mai mare punctaj care se poate obţine jucând şotron după regulile stabilite.