Revizia anterioară Revizia următoare
| Fișierul intrare/ieșire | jbb.in, jbb.out | Sursă | ONI 2018 baraj gimnaziu |
|---|---|---|---|
| Autor | Emanuela Cerchez | Adăugată de |
Cristian Frâncu
•
francu
|
| Timp de execuție pe test | 0.15 sec | Limită de memorie | 8192 KB |
| Scorul tău | N/A | Dificultate |
  4.25
|
Poți vedea testele pentru această problemă accesând
atașamentele
.
Vezi soluțiile trimise | Statistici
Jbb (baraj gimnaziu)
Ana și Bogdan joacă un nou joc – JBB (Jocul „Borcane cu Bomboane”). Pe tabla de joc sunt plasate N borcane cu bomboane. Se știe câte bomboane se află în fiecare borcan: în borcanul i sunt Bi bomboane (1 ≤ i ≤ N).
Ca de obicei, Ana începe jocul, iar apoi cei doi jucători mută alternativ. Fiind prima la mutare, Ana alege un borcan din care va lua toate bomboanele. Pe tabla de joc sunt trasate săgeți care unesc borcanele. Mai exact, de la fiecare borcan i pleacă o singură săgeată către un alt borcan j. Săgețile indică modul în care jucătorii se deplasează pe tabla de joc. Dacă există săgeată de la borcanul i la borcanul j, iar un jucător a luat bomboanele din borcanul i, atunci adversarul său e obligat să se deplaseze la borcanul j. Dacă în borcanul j va găsi bomboane, este obligat să le ia pe toate. Dacă borcanul j este gol, atunci adversarul poate să aleagă un alt borcan care conține bomboane și continuă jocul.
Evident, scopul fiecărui jucător este să aibă, la finalul jocului (atunci când toate borcanele au fost golite) cât mai multe bomboane.
Cerință
Determinați numărul maxim de bomboane pe care Ana le-ar putea obține respectând regulile jocului. Bineînțeles, atât Ana, cât și Bogdan joacă optim (adică la orice pas, fiecare jucător va face cea mai bună mutare pe care poate să o facă).
Date de intrare
Fișierul de intrare jbb.in conține pe prima linie numărul natural N, reprezentând numărul de borcane. Pe cea de a doua linie sunt N numere naturale nenule separate prin câte un spațiu B1 B2 ... BN reprezentând numărul de bomboane din fiecare borcan. Pe cea de a treia linie se află N numere naturale separate prin spațiu S1 S2 ... SN, unde Si reprezintă borcanul indicat de săgeata care plecă de la borcanul i (1 ≤ i ≤ N).
Date de ieșire
Fișierul de ieșire jbb.out va conține o singură linie pe care va fi scris un număr natural reprezentând numărul maxim de bomboane pe care Ana le poate obține.
Restricții
- 1 ≤ N ≤ 10000
- 1 ≤ Bi ≤ 1000, pentru orice 1 ≤ i ≤ N
- 1 ≤ Si ≤ N, Si ≠ Sj, pentru orice 1 ≤ i < j ≤ N
Exemplu
| jbb.in | jbb.out |
|---|---|
| This is some text written on multiple lines. |
This is another text written on multiple lines. |
Explicație
...
