11507 - Bender B. Rodríguez Problem
Time limit: 4.000 seconds
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2502
Bender is a robot built by Mom's Friendly Robot Company at its plant in Tijuana, Mexico in 2996 . He is aBending-Unit 22, serial number 2716057 and chassis number 1729 . He was created for the task of bending metal wires. Bender needs to bend a wire of length L (L
2 an integer). The wire is represented in the Bender's brain (aMOS Technology 6502 microprocessor) as a line stucked in the origin of a tridimensional cartesian coordinate system, and extended along the x positive axis (+x), so that the fixed extreme of the wire is in the coordinate (0,0,0) and the free extreme of the wire is in the coordinate (L,0,0).
Bender bends the wire at specific points, starting at the point (L-1,0,0) and ending at the point (1,0,0). For each i from L-1 to 1, Bender can take one of the following decisions:
Not to bend the wire at point (i,0,0).
To bend the wire at point (i,0,0) an angle of
to be parallel to the axis +y, -y, +z or -z. For example, if L=3 and Bender bends the wire at (2,0,0) on the +y axis direction, and at (1,0,0) on the -yaxis direction, the result would be:
Given a sequence of bends, you must determine what direction is pointed by the last segment of the wire (+xin the example). You can suppose that the wire can intercept itself, after all it is the future!
Input
The first line of each test case gives an integer L (2
L
100000) indicating the length of the wire.
The second line of each test case contains the L-1 decisions taken by Bender at each point, separated by spaces. The j-th decision in the list (for each 1
j