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: "Switchback"
Description A construction firm, which you work for, has signed a contract to complete construction of attraction called “Switchback”. The building site is a rectangle which is split into By the moment of signing the contract the following work has already been done at the attraction building site. First, a mast was built in each of the squares. The height of the mast in the square ( H ≤ 100, natural). Second, construction of a launching complex was started at the top of the mast with coordinates (_{ij}a, b), where 1 ≤ a ≤ N, 1 ≤ b ≤ M.The idea of the attraction is the following. A small carriage with passengers moves from one square to another adjacent square, square by square. It starts moving from the square with the launching complex and moves until it stops. It moves on rails built on tops of masts according to the following rules: - at the launching complex the carriage is slightly pushed so to start moving in any direction
**downwards**; - on arrival to the next square the carriage can continue its movement in the same direction or can turn 90° to the right or to the left;
- the carriage’s speed increases by one for each unit of height reduction while moving downwards; the carriage
**can not**move downwards if its current speed is zero; - the carriage’s speed decreases by two for each unit of height increment while moving upwards. If the carriage moves upwards than its initial speed has to be sufficient to reach the next square;
- the carriage’s speed during a transition to an adjacent square decreases by one while moving horizontally;
- safety rules forbid to change the carriage’s speed during transition to an adjacent square by more than 2 units;
- the carriage has brakes which can be used only to stop the carriage on arrival to the final square. However, safety rules forbid using brakes if the carriage’s speed on arrival to this square is more than three units.
The number of squares visited by the carriage during its trip is called The construction firm has to build rails on tops of the masts. As the only programmer in the firm, you need to write a program which can find the longest possible path according to the rules above. It is guaranteed that this path exists and its length is greater than zero. Input The first line of the input contains values M values per line. The numbers in the input file’s lines are separated by one or more spaces.Output The output contains several lines. The first line contains an attraction length Sample Input 5 5 1 1 10 8 6 3 4 9 7 6 5 8 4 5 5 2 1 2 3 5 7 8 1 4 3 3 2 Sample Output 14 2 1 2 2 1 2 1 3 2 3 3 3 3 2 3 1 4 1 4 2 5 2 5 3 5 4 5 5 Source Northeastern Europe 2004, Western Subregion |

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

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

Any problem, Please Contact Administrator