GARBAGE - Garbage Collection

no tags 

A big office uses a cleaning robot to empty the trash can in every cubicle. The surface of
each cubicle is a square and the office floor plan is organized as a rectangular matrix of R
rows of C cubicles each. The cleaning process begins by the robot entering the floor by a
door that accesses the topmost leftmost cubicle, and finishes with the robot exiting using
the same door. Both entering and leaving take 26 seconds each. When the cleaning robot
is in a cubicle it can emtpy the trash can using 13 seconds. The robot can also move to
a cubicle that shares a side with its current location, using 38 seconds. The robot needs
to enter in each cubicle at least once to empty its trash can.

The total time the robot takes for the entire process depends on the actual tour through
the different cubicles. Among all possible tours, we are interested in those of minimum

Given the description of the office, you must indicate the minimum time required for
the entire cleaning process (including entering, leaving, emptying the trash can in every
cubicle, and moving around). Notice that it is possible that an optimal tour passes
through a cubicle several times, but the robot has to take the time to empty the trash
can only once.


The input contains several test cases, each one described in a single line. The line contains
two integers R and C separated by a single space, representing the number of rows and
cubicles per row, respectively (1 ≤ R, C ≤ 100). The last line of the input contains the
number −1 twice separated by a single space and should not be processed as a test case.


For each test case output a single line with an integer representing the minimum number
of seconds that the robot needs to complete the cleaning process.


4 2
3 3
-1 -1

Output: 460

hide comments
N Hari Prasad: 2011-01-31 19:34:34

plz give some bigger test cases please. .

Shaka Shadows: 2010-09-26 19:41:31

Problem PLCNUM1 in the tutorial section can give some good hints about this one :).

Added by:Pablo Ariel Heiber
Time limit:0.289s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 VB.NET
Resource:FCEyN UBA ICPC Selection 2009