Informatica Online Judge

  초콜릿 [1476 / 05C4]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 118   Total Tried : 712


The Champion of this Problem (C++) : gs18051 - ms / 636byte
My Best Submission (C++) : N/A

[Codeforces]

Background

경곽이는 $n × m$ 개로 구성된 초콜릿을 가지고 있다.

경곽이는 정확히 $1× 1$크기의 조각 $k$개를 먹고 싶어한다.

그러기 위해서는 당연히 적당한 크기의 조각들로 잘라야 한다. (단, 먹는 모든 조각을 $1× $1크기로 나눌 필요는 없다. 만약 $2× 3$크기를 먹으면 $6$조각을 먹은 것이다.)

한 번의 절단 작업을 통해 초콜릿은 $2$개로 분리가 되며, 오직 수직 혹은 수평으로만 자를 수 있고 매 작업시 자르는 비용은 잘려진 길이의 제곱과 같다.

예를 들어 경곽이가  $2 × 3$ 개로 이루어진 초콜릿을 가지고 있고 수평으로 한 번 자르게 되면 $2$개의  $1 × 3$ 를 얻게 되며 절단 작업시 소요된 비용은 $3^2 = 9$ 이다.

또는 경곽이가 수직으로 자르게 된다면 $2 × 1$ 과 $2 × 2$ 크기의 초콜릿을 가지게 되며 이때 발생한 비용은 $2^2 = 4$이다.

입력은 $t$개의 쿼리로 구성되며 각 쿼리의 의미는 다음과 같다.

초콜릿의 크기를 나타내는 $n, m$ 그리고 먹고싶은 조각의 개수인 $k$가 주어진다.

각 쿼리에 대하여 초콜릿을 자르기 위하여 소요되는 최소비용을 구하시오.

Input

첫 번째 줄은 입력 데이터의 수를 나타내는 정수 $t$ 가 입력된다.

두 번재 줄 부터 $t$개의 $n, m, k$로 이루어진 값이 입력된다. 

[입력값의 정의역]
$1 ≤ t ≤ 40,910$
$1 ≤ n, m ≤ 30$
$1 ≤ k ≤ min(n·m, 50)$

Output

$k$조각을 먹기위해 초콜릿을 잘라야하는 최소 비용을 출력한다.

IO Example

입력
4
2 2 1
2 2 3
2 2 2
2 2 4

출력
5
5
4
0

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]