DEFKIN2 - Defense of a kingdom 2

no tags 

This is an extension to the problem DEFKIN http://www.spoj.com/problems/DEFKIN/ and solve it first before doing this.

Theodore implements a new strategy game “Defense of a Kingdom”. On each level a player defends the Kingdom that is represented by a rectangular grid of cells. The player builds crossbow towers in some cells of the grid. The tower defends all the cells in the same row and the same column. No two towers share a row or a column.


Now the king inputs width(w),height(h),number of towers(n). Here n<= min(w,h).

There there can be many ways to place the towers in the grid.

Lets define a function penalty(Ni) for the ith combination of tower placements,which is  number of cells in the largest undefended rectangle. For example,one of the combinations of placing a tower is shown in the picture and has a penalty=12.

Suppose there are in total k combinations . Then there are penalty(N1),penalty(N2),penalty(N3)...........penalty(Nk). 

The task of the user is to find the minimum of these penalties.


 


An example of one of the combinations

Input

The first line of the input file contains the number of test cases.

 

Each test case consists of a line with three integer numbers: w — width of the grid, h — height of the grid and n — number of crossbow towers (1 ≤ w, h ≤ 40 000; 0 ≤ n ≤ min(w, h)).

Output

For each test case, output a single integer number- the minimum penalty 
Output answer for each test case in a new line 

Example

Input:
1
15 8 3
Output:
6

hide comments
vivu01: 2016-03-08 15:45:30

Last edit: 2016-03-08 16:28:50
Narendra pal: 2015-10-24 19:04:27

how come the output is 6....can anyone explain....

agspoj: 2015-10-06 16:43:12

I have removed Scanner and used bare System.in, and that solved the problem.

mehmetin: 2015-10-06 13:54:36

@agspoj: You should use a faster input method.

agspoj: 2015-10-06 12:02:44

I got time limit exceeded although my code involves only reading and parsing input and calculating one simple equation. It cannot be done faster in java.

Scanner sc = new Scanner(System.in);
int T = Integer.parseInt(sc.nextLine());
while (T-- > 0) {
String[] vars = sc.nextLine().split(" ");
double w = Integer.parseInt(vars[0]);
double h = Integer.parseInt(vars[1]);
double n = Integer.parseInt(vars[2]);

System.out.println( (int)( calculate_result_equation_here ) );
}

mehmetin: 2015-10-04 12:34:39

Actually an easy problem. I got lots of wrong answers before getting accepted, due to wrong approach.

mandrathax: 2015-10-03 11:24:51

I think there is a typo under output, one should output the *minimum* penalty obviously

snehil10111995: 2015-09-28 19:35:22

No link to submit the problem

Its available now .cheers.

Last edit: 2015-09-28 22:39:03

Added by:Neel
Date:2015-09-28
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY