Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: Bale Figures
Description Cows like to build shapes out of hay bales. Each new shape is constructed from N (1 <= N <= 25,000) 1 x 1 x 1 cubic bales.
Bale 1 lies on the floor. After placing it, each successive bale from 2 through N is attached to the shape by placing the new bale in the proper relative position to one of the bales already placed. For instance, imagine the following figure: Bale 1 - on the floor This results in an (inverted) L-shape:
Adding another bale: Bale 5 - OVER Bale 1 adds height to the shape:
But adding another directive: Bale 6 - BACK Bale 4 results in an invalid shape, since bales 3 and 6 would overlap. Given N bales and placements described as above, output the exposed surface area of the solid figure if the shape is valid. A face is considered exposed if it is not touched by any face of any other bale and does not touch the floor (i.e., is not the bottom of a cube on the floor). Output -1 if the shape is invalid. No bale will be placed farther than 25 bale-widths from the first bale. No bale will be placed below the floor level. Input * Line 1: A single integer, N
* Lines 2..N: These lines describe the placement of bales 2..N in the form "j X". Line 2 describes bale 2; line 3 describes bale 3; and so on. The letter "X" is one of: "L" (left), "R" (right), "F" (front), "B" (back), "O" (over), or "U" (under). The bales can be glued and require no underlying support if extended over an empty space. Output * Line 1: The exposed surface area of the resulting solid. If the solid is invalid, output "-1".
Sample Input 5 1 R 2 F 3 F 1 O Sample Output 18 Source |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator