Problem Specification Value
Time Limit 1 Sec
Memory Limit 162 MB
Submit 2215
Solved 1599

Description

windy 的生日到了, 为了庆祝生日, 他的朋友们帮他买了一个边长分别为 X 和 Y 的矩形蛋糕. 现在包括 windy, 一共有 N 个人来分这块大蛋糕, 要求每个人必须获得相同面积的蛋糕. windy 主刀, 每一切只能平行于一块蛋糕的一边 (任意一边), 并且必须把这块蛋糕切成两块. 这样, 要切成 N 块蛋糕, windy 必须切 N-1 次. 为了使得每块蛋糕看起来漂亮, 我们要求 N 块蛋糕的长边与短边的比值的最大值最小. 你能帮助 windy 求出这个比值么?

Input

包含三个整数, X Y N. 1 <=X, Y <=10000; 1 <=N <=10

Output

包含一个浮点数, 保留 6 位小数.

Sample Input

5 5 5

Sample Output

1.800000

HINT

Source

http: //www. cnblogs. com/HQHQ/p/5612326. html 重要的事说三遍: 相同面积, 相同面积, 相同面积; 于是我就被坑了, 首先想到二分, 然后不知道怎么验证答案, 后来想到一个贪心, 是错的......

于是默默地重新读题, 发现是暴搜就可以了, 毕竟数据范围小.


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long double lf;
const lf inf = 1e11;

lf  dfs(lf x, lf y, int cnt)
{
    lf  res = inf;
    if (cnt == 1)
        return max(x / y, y / x);
    for (int i = 1; i <= cnt / 2; i++) {
        res = min(res, max(dfs(x / cnt * i, y, i), dfs(x / cnt * (cnt - i), y, cnt - i)));
        res = min(res, max(dfs(x, y / cnt * i, i), dfs(x, y / cnt * (cnt - i), cnt - i)));
    }
    return res;
}

int x, y, n;

int main(int argc, char **argv)
{
    scanf("%d%d%d", &x, &y, &n);
    lf  res = dfs(x, y, n);
    printf("%.6Lf\n", res);
    return 0;
}
from pydatagen import *
x = randrange(1, 10000)
y = randrange(1, 10000)
n = randrange(3, 10)
printf('%d %d %d' % (x, y, n))
fclose()