ciocolata

Doi oameni se joacă pe o tablă de șah $5 \times 5$. Pe fiecare pătrat există un număr nenul de bomboane de ciocolată. Un pătrat se consideră blocat dacă pe toate cele patru direcții se învecinează cu pătrate ce conțin bomboane. Începe primul jucător. Cei doi jucători mută alternativ. La o mutare se alege un pătrat care nu este blocat și se iau toate bomboanele din acel pătrat. În urma unei mutări este posibil ca anumite pătrate care erau blocate să se deblocheze. Scopul fiecărui jucător este să ia cât mai multe bomboane. Ambii jucători joacă optim.

Implementare

Programul vostru va implementa funcția

int solve_test (int *x)

Prin intermediul parametrului $x$ vor fi transmise elementele unui șir indexat de la $0$, conținând cele $25$ de numere de pe tabla de șah. Funcția trebuie să returneze numărul maxim de bomboane pe care primul jucător le va lua de pe tablă.

Grader-ul va apela alternativ funcția voastră și o funcție similară implementată de comisie, pe diverse teste, de mai multe ori în cadrul aceleiași rulări, și va măsura suma timpilor necesari apelurilor pentru cele două funcții. Punctajul pe care îl veți obține se va acorda în funcție de raportul între cei doi timpi totali (timpul vostru și timpul comisiei).

Pe lângă funcția pe care o veți implementa, puteți declara variabile locale sau globale și puteți implementa alte funcții ajutătoare. Se recomandă ca variabilele globale și funcțiile să fie declarate cu modificatorul static.

Restricții si precizări

• Numerele de pe tablă sunt pozitive, nenule, distincte și nu depășesc $35 \ 000$.
• Dacă în urma unui apel răspunsul returnat de funcția voastră este incorect veți obține $0$ puncte.
• Funcția voastră va fi apelată de mai multe ori în cadrul aceleiași rulări. Atenție la eventualele reinițializări de variabile !!!

Exemplu

Tabla trimisă prin parametru:

1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25

Valorea returnată:

169

Explicație

Primul jucător va lua in ordine descrescătoare numerele impare de pe tablă. Al doilea va lua în ordine descrescătoare numerele pare.

Mod de punctare

Modul de punctare diferă de cel din timpul concursului!
Punctajul concurentului se va calcula astfel:
Fie $r$ - raportul de timp per test dintre sursa concurentului și sursa comisiei

• Dacă $r > 50$, punctajul acordat va fi $0$
• Dacă $40 < r ≤ 50$, punctajul acordat va fi $30$
• Dacă $15 < r ≤ 40$ punctajul acordat va fi $((40 - r) \times 70 + (r - 15) \times 30) / 25$
• Dacă $10 < r ≤ 15$, punctajul acordat va fi $70$
• Dacă $5 < r ≤ 10$ punctajul acordat va fi $((10 - r) \times 100 + (r - 5) \times 70) / 5$
• Dacă $0 < r ≤ 5$, punctajul acordat va fi $100$