每次切蛋糕只有两种情况,横着切和竖着切,并且最大只有10个人,所以直接dfs。
如果切x,那么只能在x均分成n份的地方切,也就是x/n的倍数,模拟每种情况即可。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <stack>
#include <queue>
#include <cmath>
#define ll long long
#define pi 3.1415927
#define inf 0x3f3f3f3f
#define mod 1000000007
using namespace std;
#define _int __int128_t
int n,m;
double dfs(double x, double y, int n)
{
if(n==1)
return x>y?x/y:y/x;
double maxs=inf;
for(int i=1;i<=n/2;++i){
double x1=x*i/n, y1=y*i/n;
maxs=min(maxs,max(dfs(x1,y,i),dfs(x-x1,y,n-i)));
maxs=min(maxs,max(dfs(x,y1,i),dfs(x,y-y1,n-i)));
}
return maxs;
}
int main ()
{
int T,x,y,i,t,j,k,p,sum=0;
cin>>x>>y>>n;
double maxs=dfs(x,y,n);
printf("%.6f\n",maxs);
return 0;
}
京公网安备 11010502036488号