打卡信奥刷题（2813）用C++实现信奥题 P4160 [SCOI2009] 生日快乐

P4160 [SCOI2009] 生日快乐

题目描述

windy 的生日到了，为了庆祝生日，他的朋友们帮他买了一个边长分别为XXX和YYY的矩形蛋糕。

现在包括 windy，一共有NNN个人来分这块大蛋糕，要求每个人必须获得相同面积的蛋糕。

windy 主刀，每一切只能平行于一块蛋糕的一边（任意一边），并且必须把这块蛋糕切成两块。

这样，要切成NNN块蛋糕，windy 必须切N−1N-1N−1次。

为了使得每块蛋糕看起来漂亮，我们要求NNN块蛋糕的长边与短边的比值的最大值最小。

你能帮助 windy 求出这个比值么？

输入格式

一行三个整数X,Y,NX,Y,NX,Y,N。

输出格式

一行一个浮点数，保留666位小数。

输入输出样例 #1

输入 #1

5 5 5

输出 #1

1.800000

说明/提示

对于100%100\%100%的数据，满足1≤X,Y≤1041 \le X,Y \le 10^41≤X,Y≤104，1≤N≤101\le N\le 101≤N≤10。

C++实现

#include<bits/stdc++.h>#defineilinline#defineFor(i,a,b)for(double(i)=(a);(i)<=(b);(i)++)usingnamespacestd;intn,x,y;ildoubledfs(doublex,doubley,intk){if(k==1){returnmax(x,y)*1.0/min(x,y);}doubleans=233333333,mx=x*1.0/k,my=y*1.0/k,t1,t2;For(i,1,k/2){t1=max(dfs(mx*i,y,i),dfs(x-mx*i,y,k-i));t2=max(dfs(x,my*i,i),dfs(x,y-my*i,k-i));ans=min(ans,min(t1,t2));}returnans;}intmain(){cin>>x>>y>>n;printf("%.6lf",dfs(x,y,n));return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容