题目描述

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

输入描述:

包含三个整数，X Y N。
1 ≤ X,Y ≤ 10000 ； 1 ≤ N ≤ 10

输出描述:

包含一个浮点数，保留6位小数。

题解

看到数据范围1 ≤ N ≤ 10，那我们直接暴力dfs去切就可以了。暴力即优雅
我们注意到题目要求说需要面积相同的蛋糕，所以一旦我们某一块蛋糕的大小确定了，他要切几块也就确定了。
对于每次切蛋糕，我们dfs是横向切还是纵向切，而且，为了保证每个人拿到蛋糕的面积相同，我们切的必须是或者的倍数。每次dfs的时候枚举一下切的位置就可以了。

代码

#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pb push_back
#define pii pair<int,int>
#define all(A) A.begin(), A.end()
#define fi first
#define se second
#define MP make_pair
#define rep(i,n) for(register int i=0;i<(n);++i)
#define repi(i,a,b) for(register int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(register int i=int(b);i>=(a);--i)
template<typename T>
inline T read(){
    T s=0,f=1; char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f=-1;ch = getchar();}
    while(isdigit(ch)) {s=(s<<3)+(s<<1)+ch-48;ch = getchar();}
    return s*f;
}
#define gn() read<int>()
#define gl() read<ll>()
template<typename T>
inline void print(T x) {
    if(x<0) putchar('-'), x=-x;
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
////////////////////////////////////////////////////////////////////////
const int N=2e5+100;
double ans=1e9,num=0;
double dfs(double a,double b,int n){
    if(n==1){
        return max(a,b)/min(a,b);
    }
    double x=a/n,y=b/n;
    double ans=1e9;
    for(int i=1,len=n/2;i<=len;++i){
        ans=min(ans,min(max(dfs(x*i,b,i),dfs(a-x*i,b,n-i)),max(dfs(a,y*i,i),dfs(a,b-y*i,n-i))));
    }
    return ans;
}
////////////////////////////////////////////////////////////////////////
int main(){
    double x,y;int n;
    scanf("%lf%lf%d",&x,&y,&n);
    printf("%.6f",dfs(x,y,n));

}
/**
* In every life we have some trouble
* When you worry you make it double
* Don't worry,be happy.
**/