| Fişierul intrare/ieşire: | spatiu.in, spatiu.out | Sursă | ONIS 2015, Runda 3 |
| Autor | Vlad Stoian | Adăugată de |  Paul Diac •diac_paul |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Spatiu
Bulbuka s-a urcat intr-o racheta si s-a pierdut intr-un spatiu bidimensional infinit. Pana ca cei de la Houston sa afle ca exista o problema, Bulbuka a si apucat sa se miste de N ori. Tot ce stiu in momentul asta este ca racheta a pornit de la coordonatele (0,0) si ca in fiecare moment racheta poate sa se miste din orice punct doar in cele 4 directii alaturate de coordonate intregi (de exemplu: (0, 0) -> (0, 1) sau (0, -1) sau (1, 0) sau (-1, 0)).
Problema e cu atat mai mare cu cat in tot acest timp, singurul radar pornit e stricat: in loc sa arate exact locatia in care este racheta in acest moment, el a inregistrat o serie de pasi posibili pe care Bulbuka i-ar fi putut fi facut. Acesti pasi sunt urmatorii:
1 - sus sau stanga (exemplu: (0, 0) -> (0, 1) sau (-1, 0))
2 - jos sau dreapta (exemplu: (0, 0) -> (0, -1) sau (1, 0))
3 - sus sau dreapta (exemplu: (0, 0) -> (0, 1) sau (1, 0))
4 - jos sau stanga (exemplu: (0, 0) -> (0, -1) sau (-1, 0))
5 - sus sau stanga sau jos sau dreapta
Tu, fiind cel mai bun programator dintre cei prezenti, te-ai oferit sa calculezi numarul de pozitii diferite in care s-ar putea afla Bulbuka, pornind de la informatiile furnizate de radarul stricat.
Date de intrare
Fişierul de intrare spatiu.in contine pe prima linie T, numarul de teste. In continuare, pentru fiecare test, pe o singura linie se afla numarul N, urmat de un spatiu si N numere din multimea (1, 2, 3, 4, 5) reprezentand pasii din enunt. Aceste numere nu sunt separate prin spatiu.
Date de ieşire
În fişierul de ieşire spatiu.out se vor gasi T linii, iar fiecare linie va contine un numar natural reprezentand numarul de pozitii diferite calculat.
Restricţii
- T = 20
- 1 ≤ N ≤ 105
Exemplu
| spatiu.in | spatiu.out |
|---|---|
| 2 3 315 2 24 | 9 4 |
Explicaţie
In primul test:
Dupa primul pas, locatiile posibile sunt: (0, 1) sau (1, 0)
Dupa al doilea pas, locatiile posibile sunt: (-1, 1), (0, 2), (0, 0) sau (1, 1)
Dupa al treilea pas, locatiile posibil sunt: (-2, 1), (-1, 0), (-1, 2), (0, -1), (0, 1), (0, 3), (1, 0), (1, 2), (2, 1)
In al doilea test:
Dupa al doilea pas: (-1, -1), (0, -2), (0, 0) sau (1, -1)
