Mowing the Field#10594
Farmer John is quite reliable in all aspects of managing his farm, except for one: he is terrible at mowing the grass in a timely and logical fashion.
The farm is a large 2D grid of square cells, each with unit area. At time t = 0, FJ starts in one of these cells and mows the grass there, so that initially this is the only cell with cut grass. FJ's subsequent mowing pattern is described by a sequence of statements. For example, if the first statement is "W 10", then for times t = 1 through t = 10 (that is, during the next units of time), FJ moves one cell west at each step, mowing the grass in each cell he visits. After completing these steps, he ends up cells west of his starting position at time t = 10, having mowed every cell along the way.
FJ's progress is so slow that some of the grass he mows may grow back before he finishes mowing the entire field. Any grass that is cut at time will grow back at time t + x.
FJ's mowing pattern may cause him to visit the same cell multiple times. However, he observes that he never visits a cell while its grass is still cut. In other words, whenever he visits a cell, his previous visit to that same cell must have occurred at least units of time earlier, allowing the grass to grow back.
Determine the maximum possible value of for which FJ's observation remains valid.
The first line contains an integer n~(1 \le n \le 100). Each of the next lines contains a statement of the form "d s", where is a character describing a direction ( = north, = east, = south, = west), and s~(1 \le s \le 10) is the number of steps taken in that direction.
Print the maximum value of such that FJ never steps onto a cell whose grass is still cut. If FJ never visits any cell more than once, print .
In this example, FJ visits a cell at time that he had previously visited at time . Therefore, must be at most ; otherwise, the grass from his first visit would not yet have grown back. He also visits a cell at time that he had previously visited at time , so must also be at most . Since the first of these two constraints is tighter, we see that can be at most .
Example 1