What fits in the budget?

Before writing a line of code, you work out which shapes of solution the constraints leave room for. This tool does that arithmetic for you: given the largest input the problem allows and the number of operations you can afford, it reports the most expensive shape that still fits.

The shapes are considered in this order, from cheapest to dearest: n, then n^2, then n^3, then 2^n, then n!. Walk the list in that order and stop at the first shape whose cost at the given n is greater than the budget. Return the shape before it, as a string exactly as written above. If even n is over budget, return none. If every shape fits, return n!.

Worked example: with n = 10 and budget = 1000000, the costs are 10, then 100, then 1000, then $2^{10} = 1024$, then $10! = 3628800$. The first four are all at most a million and the fifth is not, so the walk stops at n! and the answer is the shape before it, 2^n.

• Constraints: n is between 1 and 1000000, and budget is between 1 and 1000000000.
• The five strings to return are exactly n, n^2, n^3, 2^n, n!, plus none when nothing fits.
• Never compute $2^n$ or $n!$ in full. At n = 1000000 both have more digits than there are atoms nearby. Multiply one factor at a time and stop the moment the running value exceeds the budget.
• The rule is the walk, not the cheapest fit. With n = 1 and budget = 1, the cost of 2^n is 2, which is over budget, so the walk stops there and the answer is n^3, even though n! would have fitted.