生日快乐题解

生日快乐题解

题解 ：

这个题数据范围较小，可以直接尝试枚举所有切割情况。

题目中有要求，将蛋糕分成大小相等的n块，每一次切割的线一定与一条边平行。所以首先每一刀有两种切法，与长边平行和与短边平行。为了能够将蛋糕n等分，那么当前这一刀可以是过长边的一个n等分点并与短边平行，或过短边的一个n等分点与长边平行。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_N=2e6+20;
const int INF=0x3f3f3f3f;
const LL MOD=19260817;
double X,Y;
int N;
double ans;
double dfs(double x,double y,int n){
    if(x>y)swap(x,y);
    if(n==1){
        return y/x;
    }

    double res=INF;
    for(int i=1;i<n;i++){
        res=min(res,max(dfs(x/n*i,y,i),dfs(x/n*(n-i),y,n-i)));
        res=min(res,max(dfs(x,y/n*i,i),dfs(x,y/n*(n-i),n-i)));

    }
    return res;


}
int main(){
    //ios::sync_with_stdio(false);
    //cin.tie(0),cout.tie(0);
    //freopen("1.in","r",stdin);
    scanf("%lf%lf%d",&X,&Y,&N);
    ans=dfs(X,Y,N);
    printf("%.6f\n",ans);
}