Five-second rule

University of Oregon (UO) is more famous for athletics and partying than
their students’ academic abilities. This problem, though, is about their
also famous hygienic habits.

In most of the United States kids are taught about the Five-second rule:
if the food falls to the ground, you can only pick it up and eat it if
it has been in the ground less than 5 seconds – otherwise it is
considered unsanitary. Such carelessness is unheard of in UO’s
fraternity houses. “5 seconds! Preposterous!”, claims the typical UO
student. “We never wait more than 1 second to pick up the food from the
ground. Otherwise, the ants will reach it first. Even Willie, the
raccoon living under the sink, rarely needs more than 3 or 4 seconds to
pick up any fallen food.”

In this problem we will give you a map of a UO fraternity house: an
N × M grid. Empty squares appear as ‘.’. Every other square is
impassable: squares with ‘#’ are walls, while uppercase letters
correspond to critters nests. For each type of critter (uppercase
letter) we will give you the critter’s reaction time (the amount of
milliseconds that the critter needs to realize that some food has
fallen) and the movement time (the amount of milliseconds that the
critter needs to move one square in the map, in each of the four
directions).

For each square with no wall, please compute the minimum amount of
milliseconds that the first critter to arrive needs to reach that
square. Print a digit to indicate that minimum number of seconds,
rounded to the closest second: ‘0’ means from 0 to 499 milliseconds;
‘1’ means from 500 to 1499 milliseconds; etc. If all critters need 9500
or more milliseconds to reach that square, print ‘+’. If no critter can
reach that square (something common in Ivy Plus colleges, but rarely
seen in UO) then print ‘.’.

Input

Input consists of several cases. Each case begins with N, M (both
between 1 and 700) and K (between 0 and 26). Next, the map: N lines with
M chars each. Finally, we have K triples, each one describing one type
of critter: an uppercase letter, the reaction time (an integer between 0
and 10⁴), and the movement time (an integer between 1 and 10⁴). Every
type of critter in the map will have its corresponding description.

Output

For each case, print its how-many-seconds-rule map. Separate the output
of two cases with a line with three dashes.

Problem information

Author: Omer Gimenez
Event: Vint-i-quatrè Concurs de Programació de la UPC - Semifinal
Date: 2026-06-18

Generation: 2026-06-12T11:32:50.122Z

© Jutge.org, 2006–2026.
https://jutge.org
