Fişierul intrare/ieşire:joc9.in, joc9.outSursăOLI 2009, Bucuresti, clasele 11-12
AutorCarmen MincaAdăugată deandrei-alphaAndrei-Bogdan Antonescu andrei-alpha
Timp execuţie pe test0.025 secLimită de memorie6048 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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.

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;
  • 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;
  • 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;
  • 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.

Cerinta

Să se scrie un program care să determine:

  1. punctajul maxim pe care îl poate obţine un concurent la finalul jocului;
  2. valoarea cercului iniţial din care un concurent ar trebui să înceapă jocul pentru a obţine punctajul maxim.

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ţ

Date de ieşire

Fişierul de ieşire joc9.out va conţine două linii. Pe prima linie se va scrie un număr natural reprezentând punctajul maxim pe care îl poate obţine un concurent la finalul jocului. Pe a doua linie se va scrie un număr natural reprezentând valoarea cercului iniţial din care un concurent ar trebui să înceapă jocul pentru a obţine punctajul maxim.

Restricţii

  • 2N135
  • 1 ≤ x1, x2 ,…, x(n+1)*(n+2)/2 ≤ 215
  • Dacă există mai multe variante de alegere a cercului iniţial, se va scrie în fişier cea mai mică dintre valorile acestor cercuri iniţiale din care se obţine punctajul maxim.
  • Pentru rezolvarea cerinţei 1 se acordă 30% din punctaj şi pentru cerinţa 2 70% din punctaj.

Exemplu

joc9.injoc9.out
3
10 4 3 11 14 2 9 6 5 7
37
7

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)

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content