spatiu

Spatiu

== include(page="template/taskheader" task_id="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 facut. Acesti pasi sunt urmatorii:

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))

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 radar­ul stricat.

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 radar­ul stricat.

h2. 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 set­ul (1,2,3,4,5) reprezentand pasii din enunt. Aceste numere nu sunt separate prin spatiu.

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.

h2. Date de ieşire

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)

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)

Dupa al doilea pas: (­-1, -­1), (0, ­-2), (0, 0) sau (1, -­1)

== include(page="template/taskfooter" task_id="spatiu") ==

10458