A rectangle N by M must be tiled by rectangles with side ratio 2:1, added one at a time so the union stays a rectangle; find the min and max tile counts.
Hard8MathNumber theoryGreedyImplementationNo attempts yetTime limit2sMemory limit512 MBLong ago, in the land of Cartesia, the Rectangle Empire ruled. The empire was large and prosperous, and it grew by conquering its neighbors again and again. Most customs of that civilization are no longer understood, but the way it divided its land is known.
The territory of the empire was split into districts, and the districts always met three conditions.
When the empire was founded it consisted of a single district. After that it gained districts by conquest, and every time it took a new region it turned exactly that land into one new district. No two conquests happened at the same time. Adding a district was the only way the borders ever changed, and once a district existed it was never split, reshaped, or merged with another one.
The custom the empire cared about most is that the whole territory had to be a rectangle after every conquest. Unlike a single district, the whole territory does not need side lengths in the ratio 2:1.
Archaeologists found that at one moment the empire measured N×M in Ξ. Cartesia is an infinite plane, so these numbers can be very large. Over all the ways the empire could have been founded and expanded, find the minimum and the maximum possible number of districts at that moment.
The first and only line contains two integers N and M (1≤N,M≤108).
Print the minimum number of districts and the maximum number of districts on one line, separated by a space. If no history of founding and conquest produces an N×M empire, print -1 -1 instead.
The picture below shows how the minimum of 5 districts and the maximum of 8 districts are reached for a 10×6 empire. The labels #1, #2, #3, and so on give the order in which the districts were added, and the size of each district is written in brackets as (k×2k) or (2k×k).
