每次切蛋糕只有两种情况,横着切和竖着切,并且最大只有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; }