National Olympiad in Informatics, China, 2003
While Alex was solving "The Lucky Mouse" from the NOI2003 practice contest, he felt that it was too easy, so he made some changes:
- Change the limit of
in the original problem from to . - Change the time required to cross a street to
minutes (where is the street number). - A condition is introduced: the distance between Tyke's house
and Jerry's house is less than or equal to the distance between Spike's house and Jerry's house . Even still, Alex was able to solve the problem really quickly. So, he decided to create some input data to test his program. He has just created some layouts satisfying these conditions, but to increase the difficulty of the data, he wishes for you to help him determine a set of values for , , and , such that the time it takes for Jerry to receive his presents is maximized.
Revised Problem (Note: You do not have to solve this)
Lucky Jerry Mouse's birthday is coming up, and the bulldogs Spike and
Tyke would each like to give him a birthday present. To receive the
presents, Jerry plans to depart from his house
Toontown consists of
Jerry's house is at location
Task Description
Definition: Let
Given the layout of Toontown, find values for
, and is maximized.
Determine the value of
Input Specification
The first line of input will contain two integers
Output Specification
The output should contain a single integer
Sample Input
4 3
1 2 1
2 3 1
3 4 1
Sample Output
4
Problem translated to English by .
Comments