2013编程之美资格赛之长方形（Java实现）

长方形

时间限制: 1000ms 内存限制: 256mb

描述

在 n 条水平线与 m 条竖直线构成的网格中，放 k 枚石子，每个石子都只能放在网格的交叉点上。问在最优的摆放方式下，最多能找到多少四边平行于坐标轴的长方形，它的四个角上都恰好放着一枚石子。

输入

输入文件包含多组测试数据。

第一行，给出一个整数t，为数据组数。接下来依次给出每组测试数据。

每组数据为三个用空格隔开的整数 n，m，k。

输出

对于每组测试数据，输出一行"case #x: y"，其中x表示测试数据编号，y表示最多能找到的符合条件的长方形数量。所有数据按读入顺序从1开始编号。

数据范围

1 ≤ t ≤ 100

0 ≤ k ≤ n * m

小数据：0 < n, m ≤ 30

大数据：0 < n, m ≤ 30000

样例输入

3

3 3 8

4 5 13

7 14 86

样例输出

case #1: 5

case #2: 18

case #3: 1398

主要算法：

define 输出集合l

get t

for 1 to t

get n,m,k

l.add(getresult(n,m,k))

print l

getresult算法：

define r=-1

get min={n,m}, max={n,m}

get mink=(int)sqrt(k)

if mink>min

mink=min

for mink to 2

x=mink;

y=k/x;

if y>max

break;

z=k%x;

result=(x*(x-1)*y*(y-1))/4;

if(z>1){

if(y<max)

result=result+(y*z*(z-1))/2;

else{

result=result+(x*z*(z-1))/2;

}

if result>r

r=result

return r

程序：

这个java代码实现也是通过了比赛的小数据测试，但数据测试未知。

——20130408

ps：

今天早晨数据出来了，这道题的大数据测试是wa，回答错误。在情理之外，但也发现了原因。原因见博文《2013编程之美资格赛之大数据测试（java实现）》

——20130409