<PREV Problem:
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.
asp06 mar 2010C++2900.02206 
asp06 mar 2010C++3100.02206 
asp06 mar 2010C++2800.01210 
vitar12 jun 2011C2500.01220 
asp06 mar 2010C++2600.01227 
vitar12 jun 2011C2600.01229 
vitar12 jun 2011C2000.01230 
vitar12 jun 2011C2100.01230 
vitar12 jun 2011C2300.01230 
asp06 mar 2010C++2500.01231 
stasg706 mar 2010C++1300.01249 
stasg706 mar 2010C++1500.01249 
Philip_PV29 jul 2009C++600.01253 
stasg706 mar 2010C++900.01266 
stasg706 mar 2010C++300.01283 
VladimirChelnokov09 mar 2010C++400.02308 
WsemirZ28 may 2009C++1400.01338 
WsemirZ28 may 2009C++1200.01345 
fetetriste07 mar 2010C++200.06351 
Logger06707 may 2010C++400.02387 
mathematic25 sep 2012C++500.02388 
neko25 dec 2011C++101.03410 


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.

3 1 
100 00:01

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 =