Fișierul intrare/ieșire coins1.in, coins1.out Sursă Concurs de incalzire 2004 (Infoarena)
Autor Adrian Vladu Adăugată de avatar teodor94 Teodor Plop teodor94
Timp de execuție pe test 1.8 sec Limită de memorie 65536 KB
Scorul tău N/A Dificultate N/A
open book Poți vedea testele pentru această problemă accesând atașamentele .

Coins1 (clasa a 10-a)

Capitanul Paftenie este un batran lup de mare. A trecut prin numeroase aventuri si a cutreierat lumea intreaga. Ajuns insa la batranete, isi petrece majoritatea timpului jucand un joc de strategie cu secundul sau. Jocul consta dintr-o tabla orizontala cu 22 de patratele, pe care sunt asezati galbeni (maxim unul in fiecare patratel, reprezentand nave de razboi). Fiecare muta pe rand. O mutare consta din alegerea unui galben si deplasarea sa in primul patratel liber din stanga sa. Daca la un pas Paftenie nu mai poate muta nici o piesa (toti galbenii sunt aliniati pe pozitii consecutive, incepand cu primul patratel), atunci castiga toti galbenii de pe tabla. Paftenie muta intotdeauna primul. Are probleme financiare si din acest motiv ar vrea sa stie numarul maxim de galbeni care ii poate castiga dupa un numar de jocuri.

Cerinta

Ajutati-l pe Paftenie sa afle rezultatul!

Date de Intrare

Pe prima linie a fisierului de intrare coins1.in este dat numarul N al jocurilor. Pe urmatoarele N linii se afla cate 22 de numere (0 sau 10 reprezinta patratel liber, 1 patratel cu galben pe el). Numerele sunt separate prin cate un spatiu.

Date de Iesire

Fisierul coins1.out va contine pe prima linie un numar intreg M: valoarea maxima gasita.

Restrictii si precizari

  • 1 ≤ N ≤ 100.000
  • secundul joaca intotdeauna optim

Exemplu

coins1.in coins1.out
4
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
5

Explicatie

Paftenie castiga primul si al treilea joc. Astfel, el strange 5 galbeni.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii