All Submissions


PROBLEM:
There is a rectangular grid that consists of W x H square cells. I stand on one of the cells and simulate the following steps:
• Initially, I am facing east.
• I move in steps. In each step I move to the adjacent cell in the direction I am currently facing.
• I can not leave the grid.
• I do not visit the same cell twice.
• If a step forward does not cause me to break the above rules, I take the step.
• Otherwise, I rotate 90 degrees to the left (counter-clockwise) and check whether a step forward still breaks the above rules. If not, I take the step and continue executing this program (still rotated in the new direction).
• If the rotation left did not help, I terminate the execution of this program.
• I may also terminate the execution of the program manually, at any moment.
I forgot the dimensions of the grid and the original (x,y) coordinates of the cell on which the I was originally standing, but I do remember its movement.
You are given a vector moves. This sequence of positive integers shall be interpreted as follows: I performed moves[0] steps eastwards, turned left, performed moves[1] steps northwards, turned left, and so on. After performing the last sequence of steps, I stopped. (Either I detected that I should terminate, or I stopped manually.) I am not sure if the sequence of moves is valid. If the sequence of moves is impossible, return -1. Else, return the minimum area of a grid in which the sequence of moves is possible. (I.e., the return value is the smallest possible value of the product of W and H.).

Input:
The first line contains T: the number of test cases.
For each test case there is a single line containing N, the size of vector moves followed by elements of move.

Output:
For each test case output on a different line the minimum area if possible or -1 if impossible.

Constraint:
Each element of moves is less than 60.
The number of elements in moves is less than 60.

Sample input:
3
2 3 10
4 1 1 1 1
4 8 6 6 1

Sample Output:
44
-1
-1

Explanation:
1. Place the robot in a 4*11 board.
2. Impossible sequence of moves.
3. Impossible sequence of moves.


Problem Setter:Shradha Chhaparia

Languages: Brain,C,C++,Java,C#,JavaScript,Pascal,Perl,PHP,Python,Ruby,Text

Time Limit: 5 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Submit

Login to post clarification.

No Clarifications.

Contest

Mode Judge

Passive

Online

Overall Rankings

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0