Nipun and Dairy Milk
All submissions for this problem are available.Nipun loves sweets a lot, and you want some of his dairy milk. He allows you to eat exactly $K$ pieces of the dairy milk. But he has certain conditions for you to break it. Consider the dairy milk to be a grid of dimension $N × M$ pieces Now Nipun has allowed you to break the dairy milk according to this move- You can break a grid into **two** grids, either horizontally or vertically by the lines between the pieces. The cost for this is equal to (break length)2 Consider an example, a dairy milk of dimension $4 × 2$ squares. You can break it with the vertical axis and get two $4 × 1$ grids (the cost is $4$$2$=$16$) or you can break it horizontally in three ways and get two grids: $1 × 2$ and $3 × 2$(the cost is $2$$2$=$4$) or both grids of $2 × 2$(the cost is $2$$2$=$4$) Now Nipun wants you to find the **minimum** cost incurred for breaking the dairy milk. It is possible to eat exactly $K$ pieces if after all operations there is a set of grids of dairy milk with total pieces adding to $K$. It is not required that the other $N.M-K$ pieces form a single grid. ###Input: - First line will contain $T$, number of testcases. Then the testcases follow. - Each testcase contains three integers $N$, $M$ and $K$ — the dimensions of the chocolate bar and the number of squares you want to eat respectively. ###Output: For each testcase, print the minimum total cost needed to break the chocolate bar, in order to make it possible to eat exactly $K$ squares. ###Constraints - $1 \leq T \leq 40000$ - $1 \leq N,M \leq 30$ - $1 \leq K \leq min(N.M,50)$ ###Subtasks - 20 points - $1 \leq T \leq 5$ - $1 \leq N,M \leq 10$ - $1 \leq K \leq min(N.M,20)$ - 80 points : Original Constraints ###Sample Input: 3 2 2 3 2 2 2 2 2 4 ###Sample Output: 5 4 0
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.