Determining maximum possible number of pieces of a bar with given number of cuts

Question

I came across a challenge on Hackerrank which has me stumped literally. It is a coding problem but I am not looking for the code, rather I can't figure out the mathematical approach towards it.

Problem Statement

Alex is attending a Halloween party with his girlfriend, Silvia. At the party, Silvia spots the corner of an infinite chocolate bar.

If the chocolate can be served as only 1 x 1 sized pieces and Alex can cut the chocolate bar exactly K times, what is the maximum number of chocolate pieces Alex can cut and give Silvia?

Input Format The first line contains an integer T, the number of test cases. T lines follow. Each line contains an integer K.

Output Format T lines; each line should contain an integer that denotes the maximum number of pieces that can be obtained for each test case.

Constraints 1≤T≤10 2≤K≤107

Note: Chocolate must be served in 1 x 1 sized pieces. Alex can't relocate any of the pieces, nor can he place any piece on top of another.

Sample Input #00

4 5 6 7 8

Sample Output #00

6 9 12 16

Some places which aren't quite clear to me are:

1. What does the question mean by ... only 1 x 1 sized pieces?
2. How would you begin cutting an infinite chocolate bar?

I'd highly appreciate if someone could point out the mathematical logic behind this problem.

Answer 1

This does not really point out the mathematic logic, but it might help with understanding the problem and answer the two questions:

From the text (a corner is mentioned) I'm assuming you can imagine the infinite choclate bar as an array, "unbounded" on two sides, i.e.

c c c c ...

c c c c ...

.

.

where c denotes a piece of chocolate of size $1\times 1$ where 1 has an arbitrary but fixed unit of length. You can "cut" between the lines of c's, that is you can place $K$ lines in the blank spaces and try to isolate as many $c's$ as possible.

edit: using this model, it should not be to hard to solve this mathematically, because you can only place lines horizontally or vertically. You could for example try to count/maximize the number of intersections between horizontal and vertical lines. Of course you could also model it with general cut positions and have to use extra arguments to justify that the model used here suffices.

Answer 2

Imagine the chocolate bar as the region $x \geq 0$, $y \geq 0$ in the $xy$- plane.

If Alex makes cuts along the lines $x = 1$, $x = 2$, $y = 1$ then the chocolate bar is cut into six pieces. Two of these pieces are $1 \times 1$ squares, and so they are servable.

Answer 3

From the test cases, I am "deducing" that you are only allowed to cut infinite horizontal and vertical lines on the chocolate bar.... For instance two horizontal lines at heights 1 and 2 and three vertical ones at lengths 1,2,3 will leave 6 pieces drop...

Therefore, with m+n lines (horiz-vert) you get mn pieces. The problem now is maximize mn for a given m+n.

The answer should be easy, when m+n=2k, we get k^2, when m+n=2k+1, we get k(k+1)...