Goro Want Chocolate
Statement
Goal
Goro hungry. Goro want chocolate.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
┌─────────────────────┬──────┬──────┐It's possible to split down to
│ │ │ │
│ │ 1 │ 1 │
│ │ │ │
│ ├──────┴──────┤
│ │ │
│ 3 │ │
│ │ │
│ │ 2 │
│ │ │
│ │ │
│ │ │
└─────────────────────┴─────────────┘
Input
Single line: H and W, dimensions of the chocolate rectangle, space-separated.
Output
N the minimal number of squares we can chop out with no waste.
Constraints
1 ≤ H, W ≤ 150
Example
Input
3 5
Output
4
Tags
Chocolate, Dynamic programming
Difficulty
Medium
Test cases
Test 1 Test
Input
3 5
Output
4
Validator 1 Validator
Input
5 3
Output
4
Test 2 Test
Input
51 13
Output
10
Validator 2 Validator
Input
47 11
Output
10
Test 3 Test
Input
101 97
Output
22
Validator 3 Validator
Input
93 97
Output
11
Test 4 Test
Input
150 149
Output
12
Validator 4 Validator
Input
148 149
Output
13
Solution language
Solution
Stub generator input