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

程序：

import java.util.Scanner;

public class Main {

	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		int T=sc.nextInt();
		int[] result=new int[T];
		for(int i=0;i<T;i++){
			int M=sc.nextInt();
			int N=sc.nextInt();
			int K=sc.nextInt();
			result[i]=getNum(M,N,K);
		}
		printResult(result);
	}

	private static int getNum(int m, int n, int k) {
		int result=0;
		int max=n;
		int min=m;
		if(m>n){
			min=n;
			max=m;
		}
		int start=new Double(Math.sqrt(k)).intValue();
		if(start>min)
			start=min;
		for(int i=start;i>1;i--){
			int x=i;
			int y=k/x;
			if(y>max)
				break;
			int z=k%x;
			int s=getResult(x,y,z,max,min);
			if(s>result){
				result=s;
			}
		}
		return result;
	}

	private static int getResult(int x, int y, int z, int max, int min) {
		int 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;
			}
		}
		return result;
	}

	private static void printResult(int[] result) {
		for(int i=0;i<result.length;i++){
			System.out.println("Case #"+(i+1)+": "+result[i]);
		}
	}
}

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

——20130408

PS：

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

——20130409