Revizia anterioară Revizia următoare
| 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 sa urcat intro racheta si sa pierdut intrun 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 iar fi putut 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, teai oferit sa calculezi numarul de pozitii diferite in care sar 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 setul (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)
