<PREV Problem:
NEXT>
Solved by 38 users: defrager, Kuznetsov_S, DAV, DmitrievVladimir814, M_A_X, risinka_814, yura814, gafrustam814, Alexeyev814, alatkon, zloy_mipt, avg79, shatalin_814, brain-001, coolzero814, WsemirZ, KZ, Philip_PV, RAVEman, topspin, asp, stasg7, fetetriste, VladimirChelnokov, Logger067, Dest, tttttt, vitar, neko, mariama, checkil, mikelan, Azizkhan, NIGHTFIT, mathematic, basimova, dzhavaharnal, JohnJones_001.
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Turtle

Time limit = 3 seconds

Memory limit = 32 Mb

Turtle House is located at the beginning of a straight narrow ridges, where dandelion (her favorite delicacy) would appear. Once upon a time turtle had a prophetic dream. She learned that after dandelions will start to grow after midnight. She even learned from that dream the exact location and the exact grow time for each dandelion. So the turtle left her hous at midnight looking forward to eat all the dandelions, and return home before next midnight.

Turtle can crawl at a speed not exceeding the value V_max. It takes d minutes to eat a dandelion. Each dandelion should be eaten in one shot, otherwise it will wither. The farther dandelion grows from the house the later it grows. Several dandelion cannot occupy neither the same point nor the same grow time.

The problem is to determine the time when the turtle would be able to return home, provided she ate all the dandelions and spent the shortest time possible.

$ Input First line contains two integers: V_max (in cm / min) and d (in minutes), 0 < V_max ≤ 200, 0 ≤ d ≤ 500. The second line contains N — the number of dandelions. 0 ≤ N ≤ 1400 (when d = 0), otherwise 0 ≤ N ≤ 200. Each of the next N lines contain: integer x_i — the location of i-th dandelion (distance from the initial turtle position in cm), 0 ≤ x_i ≤ 32767, and t_i — dandelion grow time (in hh:mm format). The input data to ensure that a turtle can eat all the dandelions and return home before next midnight.

$ Output Single string that contains the time turtles return home (in the format hh:mm), rounded up to minutes with ceil function.

Input#1
3 1 
1
100 00:01
Output#1
01:08

Author:
XIV Russian Olympiad on Computer Science, 2 round, The City of Perm.
5-11 April 2002

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 200ms

SW soft NIX
ID = 23.20.166.68