| Fişierul intrare/ieşire: | aiacusarpe.in, aiacusarpe.out | Sursă | Grigore Moisil 2017, 10 |
| Autor | Sergiu Puscas | Adăugată de |  Grigore Moisil •grigore.moisil |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Aiacusarpe
Recent, Bulănel a descoperit o nouă activitate cu care să îşi ocupe timpul: o variaţie a clasicului joc Snake.
Jocul are la bază un grid cu N linii şi M coloane. Iniţial, şarpele ocupă o singură celulă, aflată la cordonatele (1, 1), adică în colţul stânga-sus. În orice moment, şarpele se poate deplasa cu o unitate în una din direcţiile Nord, Est, Sud, Vest. La începutul jocului, Bulănel stabileşte o secvenţă formată din T mutări pe care şarpele trebuie să le efectueze. Această secvenţă este fixă, nu poate fi modificată ulterior, iar şarpele nu poate sări peste mutări.
În timpul jocului, Bulănel dispune de o cantitate infinită de mere pe care le poate plasa în orice moment, în oricare dintre celulele libere ale gridului. Atunci când capul şarpelui ajunge într-o celulă care conţine un măr, şarpele va creşte instantaneu în lungime cu o unitate, coada sa rămânând pe loc în timpul mutării respective.
Jocul se termină în oricare din următoarele situaţii:
- Şarpele se loveşte de peretele care înconjoară gridul
- Şarpele se loveşte de el însuşi. Atenţie: În cadrul unei mutări, toate celulele şarpelui se deplasează simultan.
- Şarpele efectuează toate mutările din secvenţa stabilită de Bulănel.
Definim scorul obţinut ca fiind lungimea şarpelui în momentul terminării jocului. Bulănel vrea să plaseze merele în aşa fel încât să obţină cel mai mare scor posibil, indiferent dacă jocul se termină înainte ca şarpele să termine secvenţa de mutări.
Date de intrare
Fişierul de intrare aiacusarpe.in conţine pe prima linie valorile N, M şi T, separate prin spaţiu. Cea de-a doua linie conţine T caractere din mulţimea {N, E, S, V}, reprezentând secvenţa de mutări.
Date de ieşire
În fişierul de ieşire aiacusarpe.out trebuie să conţină o singură valoare: scorul maxim care poate fi obţinut prin plasarea strategică a merelor.
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.
Exemplu
| aiacusarpe.in | aiacusarpe.out |
|---|---|
| 3 4 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.
