Woburn Challenge 2017-18 Finals Round - Senior Division

Problem 5: Crop Rectangles

After weeks of gruelling combat, the unified cow-monkey army has been abruptly called home. Bo Vine and the Head-Monkey have both realized that continuing to fight this war against the Party of Extraterrestrial Gangsters is senseless — if the aliens are provoked into using their devastating vaporization beam, Scarberia is surely doomed. However, they're not prepared to just surrender the Earth to PEG either. Perhaps an alternative resolution can be found? Perhaps an offer of peace can be extended to PEG?

Upon consultation with his leading extraterrestrial linguistics experts, Bo Vine has devised a plan for communicating with the aliens — using the universal alien language of crop formations! Crop circles are difficult to create, but crop rectangles will do just as well. In order to convey a message of peace, Bo Vine has determined that a sequence of N (1 ≤ N ≤ 20) crop rectangles will be necessary, the i-th of which should be R_i metres tall and C_i metres wide (1 ≤ R_i, C_i ≤ 80) when viewed from above.

Unfortunately, having spent just about all of their resources on the war against PEG, the cows and monkeys are having a hard time finding any equipment to mow down crops. The Head-Monkey's old lawnmower will have to do. The lawnmower is able to mow down a 1m×1m square of crops at a time. So, for each crop rectangle i, Bo Vine has drawn out a grid of 1m×1m cells in a field of crops, with R_i rows and C_i columns. What remains is for the Head-Monkey to simply drive the lawnmower around and mow down the crops in all grid's cells! They'll intend to repeat this process independently for all N crop rectangles.

For each crop rectangle, the lawnmower will need to start in the bottom-left corner of the grid, facing in any cardinal direction of the Head-Monkey's choice. After that, at any point, the Head-Monkey may either drive the lawnmower forwards by one cell (in the direction it's currently facing), or turn it 90 degrees in either direction (either clockwise or counter-clockwise). Driving it forwards by one cell consumes one litre of gas, while turning it doesn't consume any.

Much to the Head-Monkey's dismay, her old lawnmower doesn't handle as well as she seemed to remember. In particular, its turning radius is quite lacking, resulting in her needing to drive it forwards at least twice between any two consecutive turns. For example, she may not turn → turn or turn → drive → turn at any point, but she may turn → drive → drive → turn.

For each crop rectangle i, the Head-Monkey will need to keep driving the lawnmower around until it has visited each of the R_i×C_i cells at least once, thus mowing down crops in the required shape. Note that cells may be driven through multiple times if necessary. The lawnmower must never leave the boundaries of the grid, as that would cause the crop formation to no longer be accurate. Unfortunately, the lawnmower's poor turning radius may result in certain crop rectangles being impossible to create altogether.

The Head-Monkey also doesn't want to risk running out of gas before the crop formations are complete, lest they accidentally send a message of war to PEG instead! As such, she'd like to minimize the amount of gas used. For each independent crop rectangle, help her determine the minimum amount of gas required to create it, or report a value of −1 if it's impossible to do so.

Subtasks

In test cases worth 4/35 of the points, 1 ≤ R_i, C_i ≤ 4 for each i.
In test cases worth another 8/35 of the points, 1 ≤ R_i, C_i ≤ 6 for each i.

Input Format

The first line of input consists of a single integer, N.
N lines follow, the i-th of which consists of two space-separated integers, R_i and C_i, for i = 1..N.

Output Format

Output N lines, the i-th of which consists of a single integer, the minimum amount of gas (in litres) required to create the i-th crop rectangle, or −1 if it's impossible

Sample Input

3
3 1
3 2
1 1

Sample Output

2
-1
0

Sample Explanation

For the first rectangle, assuming that the lawnmower starts in the bottom-left corner of the grid facing upwards, it can simply drive forwards twice to mow down the remaining two cells.

For the second rectangle, it's possible to mow down up to 5 different cells — if the lawnmower starts facing to the right, it can drive forwards, turn counter-clockwise (to face upwards), drive forwards twice, turn counter-clockwise (to face to the left), and drive forwards once. However, it's impossible to mow down all 6 cells in the grid.

All Submissions
Best Solutions

Point Value: 25 (partial)
Time Limit: 6.00s
Memory Limit: 128M
Added: May 13, 2018
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)