== include(page="template/taskheader" task_id="joc9") ==
Trei copii au inventat un joc nou. Ei au desenat pe asfalt un triunghi echilateral $ABC$ şi l-au împărţit în $N*N$ triunghiuri echilaterale congruente. Pornind din vârful $A$ al triunghiului $ABC$ către latura opusă $BC$, au desenat cercuri identice, câte unul în fiecare vârf al triunghiurilor formate, iar în interiorul fiecărui cerc au scris câte un număr natural nenul reprezentând valoarea cercului, ca în figura alăturată desenată pentru $N$=3.
Trei copii au inventat un joc nou. Ei au desenat pe asfalt un triunghi echilateral $ABC$ şi l-au împărţit în $N*N$ triunghiuri echilaterale congruente. Pornind din vârful $A$ al triunghiului $ABC$ către latura opusă $BC$, au desenat cercuri identice, câte unul în fiecare vârf al triunghiurilor formate, iar în interiorul fiecărui cerc au scris câte un număr natural nenul reprezentând valoarea cercului, ca în figura alăturată desenată pentru $N$=3.
Copiii au stabilit regulamentul de desfăşurare a jocului:
!problema/joc9/?01.jpg!
Copiii au stabilit regulamentul de desfăşurare a jocului:
* la joc pot participa doar trei concurenţi;
* fiecare concurent se aşează într-unul din cercurile situate în vârfurile $A$, $B$ sau $C$ ale triunghiului, denumite cercuri iniţiale;
* fiecare concurent trebuie să ajungă într-unul din cele n+1 cercuri situate pe latura opusă vârfului din care a plecat, în triunghiul $ABC$, şi poate să se deplasaze doar în direcţia acestei laturi; de exemplu, dacă un concurent se află în cercul iniţial din vârful $C$, el trebuie să ajungă într-unul din cercurile cu valorile: $x1$, $x2$, $x4$ sau $x7$ de pe latura opusă, $AB$;
* fiecare concurent trebuie să ajungă într-unul din cele $n$+1 cercuri situate pe latura opusă vârfului din care a plecat, în triunghiul $ABC$, şi poate să se deplasaze doar în direcţia acestei laturi; de exemplu, dacă un concurent se află în cercul iniţial din vârful $C$, el trebuie să ajungă într-unul din cercurile cu valorile: $x1$, $x2$, $x4$ sau $x7$ de pe latura opusă, $AB$;
* concurenţii se vor deplasa sărind dintr-un cerc în altul, fără a trece de mai multe ori prin acelaşi cerc;
* este permis ca într-un cerc să se afle mai mulţi concurenţi;
* la fiecare secundă, simultan, concurenţii trebuie să sară într-unul din cercurile situate la cea mai mică distanţă de cel în care se află, în direcţia laturii opuse corespunzătoare; de exemplu, un concurent, care a plecat din cercul iniţial situat în vârful $B$ şi care se află în cercul cu valoarea $x5$, poate sări doar în unul din cercurile cu valorile $x3$ sau $x6$;
* la fiecare secundă, simultan, concurenţii trebuie să sară într-unul din cercurile situate la cea mai mică distanţă de cel în care se află, în direcţia laturii opuse corespunzătoare; de exemplu, un concurent, care a plecat din cercul iniţial situat în vârful $B$ şi care se află în cercul cu valoarea $x5$, poate sări doar în unul din cercurile cu valorile $x3$ sau $x6$;
* concurenţii nu au voie să sară într-un cerc care nu se află în direcţia laturii opuse corespunzătoare;
* jocul se termină atunci când concurenţii ajung într-unul din cele n+1 cercuri situate pe latura cerută din triunghiul $ABC$, prin efectuarea a câte n sărituri, fiecare;
* pentru fiecare concurent, se va calcula punctajul obţinut prin adunarea valorii cercului iniţial cu valorile celor n cercuri, în care a sărit în timpul deplasării;
* jocul se termină atunci când concurenţii ajung într-unul din cele $n$+1 cercuri situate pe latura cerută din triunghiul $ABC$, prin efectuarea a câte n sărituri, fiecare;
* pentru fiecare concurent, se va calcula punctajul obţinut prin adunarea valorii cercului iniţial cu valorile celor $N$ cercuri, în care a sărit în timpul deplasării;
* câştigătorul jocului este concurentul cu cel mai mare punctaj; pot fi mai mulţi câştigători dacă sunt mai mulţi concurenţi care au obţinut un punctaj egal cu cel mai mare punctaj obţinut la finalul jocului.
Cerinţe.
h2. Cerinta
Să se scrie un program care să determine:
a) punctajul maxim pe care îl poate obţine un concurent la finalul jocului;
b) valoarea cercului iniţial din care un concurent ar trebui să înceapă jocul pentru a obţine punctajul maxim.
# punctajul maxim pe care îl poate obţine un concurent la finalul jocului;
# valoarea cercului iniţial din care un concurent ar trebui să înceapă jocul pentru a obţine punctajul maxim.
h2. Date de intrare
Fişierul de intrare $joc9.in$ conţine două linii. Pe prima linie este scris numărul natural nenul n. Pe a doua linie sunt scrise numere naturale nenule: x1,x2,...,x(n+1)*(n+2)/2, separate prin câte un spaţiu, reprezentând valorile cercurilor din joc, în ordinea din enunţ
Fişierul de intrare $joc9.in$ conţine două linii. Pe prima linie este scris numărul natural nenul $N$. Pe a doua linie sunt scrise numere naturale nenule: x{~1~}, x{~2~} ,…, x{~(n+1)*(n+2)/2~} separate prin câte un spaţiu, reprezentând valorile cercurilor din joc, în ordinea din enunţ
h2. Date de ieşire
h3. Explicaţie
Dacă concurentul pleacă din cercul iniţial din vârful:
- A, cel mai mare punctaj pe care îl poate obţine este 34 (=10+4+11+9)
- B, cel mai mare punctaj pe care îl poate obţine este 37 (=9+11+14+3)
- C, cel mai mare punctaj pe care îl poate obţine este 37 (=7+5+14+11).
Astfel, punctajul maxim este 37 şi se poate obţine dacă concurentul pleacă din cercurile iniţiale din B şi C. Cercul din B are valoarea 9, iar cel din C are valoarea 7<9. Pe prima linie a fişierului joc.out se va scrie valoarea 37 (punctajul maxim), iar pe a doua linie se va scrie valoarea 7 (cercul iniţial din C are valoarea mai mică decât cel din B)
* $A$, cel mai mare punctaj pe care îl poate obţine este $34$ (={$10$} + {$4$} + {$11$} + {$9$})
* $B$, cel mai mare punctaj pe care îl poate obţine este $37$ (={$9$} + {$11$} + {$14$} + {$3$})
* $C$, cel mai mare punctaj pe care îl poate obţine este $37$ (={$7$} + {$5$} + {$14$} + {$11$}).
Astfel, punctajul maxim este $37$ şi se poate obţine dacă concurentul pleacă din cercurile iniţiale din $B$ şi $C$. Cercul din $B$ are valoarea $9$, iar cel din $C$ are valoarea {$7$}<{$9$}. Pe prima linie a fişierului joc.out se va scrie valoarea $37$ (punctajul maxim), iar pe a doua linie se va scrie valoarea $7$ (cercul iniţial din $C$ are valoarea mai mică decât cel din $B$)
!problema/joc9?02.jpg!
== include(page="template/taskfooter" task_id="joc9") ==
