Goro picky. Goro only like chocolate shape like square. Goro like few big square better than mucho little square.
You smart. You help Goro find best chocolate chop so squares bigger, no waste.
──────────
You are provided with Goro's chocolate bar's dimensions. You are to answer with the minimal number of squares it's possible to chop out of it, with no leftovers allowed.
Goro chopping works karate-style:
• Goro picks a piece of chocolate among those available.
• Goro holds it firmly between his lower-left and lower-right hands.
• Goro grunts loudly.
• Goro forcefully slashes down the chocolate with his upper-right arm and breaks it in two new rectangular pieces.
Goro is very strong, yet he is disciplined enough that he only splits the chocolate rectangle along its major axes (horizontal and vertical), on the lines.
Example on a 3×5 chocolate grid:
┌─────────────────────┬──────┬──────┐
│ │ │ │
│ │ 1 │ 1 │
│ │ │ │
│ ├──────┴──────┤
│ │ │
│ 3 │ │
│ │ │
│ │ 2 │
│ │ │
│ │ │
│ │ │
└─────────────────────┴─────────────┘ It's possible to split down to 4 square pieces, of sides 3, 2, 1 and 1: first split the 3-sided square from the rest, then split the 2-sided one out, then separate the 1-sided remnants from each other.Solution
This problem consists of finding the minimum number of squares that fit into a rectangle. To do so, we cut off the largest square from the rectangle and continue recursively with the rest. Since the rest is a two-dimensional arrangement, a lot of options are possible and the question is where to split to minimize the number of squares. In fact, we need to test all possible splits and take the one with minimum result.
Assuming we have a rectangle of width \(w\) and hight \(h\), we define the solution recursively. The base case is when \(h=w\), so it is a square. Otherwise we divide the rectangle into all possible pairs of rectangles of size \((w – x, h)\) and \((x, h)\) as well as \((w, h – x)\) and \((w, x)\), which leads to the following recursive algorithm:
def f(w, h):
if w = h return 1
// minimum number of squares by splitting horizontally
m = min { f(i, h) + f(w - i, h) | i ∈ [1, w/2] }
// minumum number of square by splitting vertically
n = min { f(w, i) + f(w, h - i) | i ∈ [1, h/2] }
return min {m, n} Implemented with a dynamic programming cache for already calculated values, we can state the solution as
const [h, w] = readline().split(' ').map(Number);
const dp = new Map;
function solve(w, h) {
let key = w + "x" + h;
let vMin = Infinity;
let hMin = Infinity;
if (w === h) {
return 1;
}
if (dp.has(key)) {
return dp.get(key);
}
for (let i = 1; i <= w / 2; i++) {
hMin = Math.min(solve(i, h) + solve(w - i, h), hMin);
}
for (let i = 1; i <= h / 2; i++) {
vMin = Math.min(solve(w, i) + solve(w, h - i), vMin);
}
dp.set(key, Math.min(vMin, hMin));
return dp.get(key);
}
print(solve(h, w));