h2. Restricţii

* $3 ≤ N, M ≤ 1000$
* $1 ≤ T ≤ N*M$
* Pentru teste în valoare de 20 de puncte, $N, M ≤ 10$ şi $T ≤ 15$.
* Pentru teste în valoare de 50 de puncte, $N, M ≤ 100$ şi $T ≤ 2000$.
* Problema va fi evaluată pe teste în valoare de 90 de puncte.
* Exemplul va reprezenta teste în valoare de 10 ("puncte din oficiu") şi vor fi cu feedback.
 

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. aiacusarpe.in |_. aiacusarpe.out |

| 3 4 6
ESSENV
| 6

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|
h3. Explicaţie

...
 
== include(page="template/taskfooter" task_id="aiacusarpe") ==
 
 
 
 
Restricţii şi precizări
3 ≤ N, M ≤ 1000
1 ≤ T ≤ N * M
 
Exemplu
 
aiacusarpe.in
aiacusarpe.out
3 5 6
ESSENV
6
Explicaţie
 

Analizăm două scenarii posibile:

După prima mutare a şarpelui, plasăm un singur măr la coordonatele (2, 2). Şarpele execută toate mutările din secvenţa dată şi termină jocul având lungimea 2.
Plasăm mere la coordonatele (1, 2), (2, 2), (3, 2), (3, 3), (2, 3). Putem face acest lucru la începutul jocului, sau secvenţial, câte un măr o dată. Ambele abordări duc la terminarea jocului atunci când şarpele se loveşte de el însuşi la ultima mutare, având lungimea 6. Acesta este scorul maxim care poate fi obţinut.

# După prima mutare a şarpelui, plasăm un singur măr la coordonatele $(2, 2)$. Şarpele execută toate mutările din secvenţa dată şi termină jocul având lungimea 2.
# Plasăm mere la coordonatele $(1, 2), (2, 2), (3, 2), (3, 3), (2, 3)$. Putem face acest lucru la începutul jocului, sau secvenţial, câte un măr o dată.
!problema/aiacusarpe?exemplu.png!

Mutarea următoare
E
S
S
E
N
V
 
 
Scenariul 1
Scenariul 2
Şarpele se loveşte de el însuşi.
Jocul se termină
 

Ambele abordări duc la terminarea jocului atunci când şarpele se loveşte de el însuşi la ultima mutare, având lungimea 6. Acesta este scorul maxim care poate fi obţinut.
== include(page="template/taskfooter" task_id="aiacusarpe") ==