Description
windy的生日到了,为了庆祝生日,他的朋友们帮他买了一个边长分别为 X 和 Y 的矩形蛋糕。现在包括windy
,一共有 N 个人来分这块大蛋糕,要求每个人必须获得相同面积的蛋糕。windy主刀,每一切只能平行于一块蛋糕
的一边(任意一边),并且必须把这块蛋糕切成两块。这样,要切成 N 块蛋糕,windy必须切 N-1 次。为了使得
每块蛋糕看起来漂亮,我们要求 N块蛋糕的长边与短边的比值的最大值最小。你能帮助windy求出这个比值么?
Input
包含三个整数,X Y N。1 <= X,Y <= 10000 ; 1 <= N <= 10
Output
包含一个浮点数,保留6位小数。
Sample Input
Sample Output
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
double dfs(double x,double y,double k)
{
double i;
double ans=2e9;
if (k==) return (max(x,y)/min(x,y));
for (i=;i<k;i++)
{
ans=min(ans,max(dfs(x,y*i/k,i),dfs(x,y*(k-i)/k,k-i)));
ans=min(ans,max(dfs(x*i/k,y,i),dfs(x*(k-i)/k,y,k-i)));
}
return ans;
}
int main()
{double X,Y,k;
cin>>X>>Y>>k;
printf("%.6lf",dfs(X,Y,k));
}
[SCOI2009]生日快乐的更多相关文章
-
BZOJ 1024: [SCOI2009]生日快乐 dfs
1024: [SCOI2009]生日快乐 Time Limit: 20 Sec Memory Limit: 256 MB 题目连接 http://www.lydsy.com/JudgeOnline/p ...
-
BZOJ 1023 [SCOI2009]生日快乐
1024: [SCOI2009]生日快乐 Time Limit: 1 Sec Memory Limit: 162 MBSubmit: 1729 Solved: 1219[Submit][Statu ...
-
BZOJ 1024 [SCOI2009]生日快乐 (搜索)
1024: [SCOI2009]生日快乐 Time Limit: 1 Sec Memory Limit: 162 MBSubmit: 3025 Solved: 2201[Submit][Statu ...
-
【BZOJ1024】[SCOI2009]生日快乐(搜索)
[BZOJ1024][SCOI2009]生日快乐(搜索) 题面 BZOJ 洛谷 题解 看到这个数据范围就感觉是爆搜.我们爆搜左右分成多少块,这样子左右的面积已知,再枚举一下横着切还是竖着切,这样子就可 ...
-
bzoj千题计划115:bzoj1024: [SCOI2009]生日快乐
http://www.lydsy.com/JudgeOnline/problem.php?id=1024 枚举横着切还是竖着切,一边儿分多少块 #include<cstdio> #incl ...
-
【bzoj1024】[SCOI2009]生日快乐
1024: [SCOI2009]生日快乐 Time Limit: 1 Sec Memory Limit: 162 MBSubmit: 2372 Solved: 1717[Submit][Statu ...
-
BZOJ1024 [SCOI2009]生日快乐
本文版权归ljh2000和博客园共有,欢迎转载,但须保留此声明,并给出原文链接,谢谢合作. 本文作者:ljh2000作者博客:http://www.cnblogs.com/ljh2000-jump/转 ...
-
BZOJ 1024: [SCOI2009]生日快乐
Description 将一个 \(x\times y\) 的矩形分成 \(n\) 块,让最长边:最短边 最小. Sol 搜索. \(n\) 只有 \(10\) 写一个类似于记搜的东西就好了. Cod ...
-
1024: [SCOI2009]生日快乐
暴力题,N<=10,没注意到平均分,读题真是.. 我们对于一个矩形分成两块进行搜.然后求较大值. ans=min(ans,max(dfs(x,y/n*i,i),dfs(x,y/n*(n-i),n ...
-
1024: [SCOI2009]生日快乐 - BZOJ
Description windy的生日到了,为了庆祝生日,他的朋友们帮他买了一个边长分别为 X 和 Y 的矩形蛋糕.现在包括windy,一共有 N 个人来分这块大蛋糕,要求每个人必须获得相同面积的蛋 ...
随机推荐
-
[NOIP2015] 子串substring 题解
[题目描述] 有两个仅包含小写英文字母的字符串A和B.现在要从字符串A中取出k个互不重叠的非空子串,然后把这k个子串按照其在字符串A中出现的顺序依次连接起来得到一个新的字符串,请问有多少种方案可以使得 ...
-
iphone尺寸设计
http://www.paintcodeapp.com/news/ultimate-guide-to-iphone-resolutions http://daily.zhihu.com/story/4 ...
-
未能加载文件或程序集";Microsoft.Web.Infrastructure, Version=1.0.0.0, Culture=neutral, PublicKeyToken=31bf3856ad
问题: 未能加载文件或程序集"Microsoft.Web.Infrastructure, Version=1.0.0.0, Culture=neutral, PublicKeyToken=3 ...
-
九度OJ 1371 最小的K个数 -- 堆排序
题目地址:http://ac.jobdu.com/problem.php?pid=1371 题目描述: 输入n个整数,找出其中最小的K个数.例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4 ...
-
QF——OC的多态,动态绑定及实现原理
多态: 封装,继承,多态是面向对象的三大特征. 那多态到底是什么呢? 多态:允许不同的类定义相同的方法,OC能自己判断当前类所对应的方法,不会混乱. 动态类型:程序直到运行时才确定对象的类型. 动态绑 ...
-
WindowsAPI 之 CreatePipe、CreateProcess
MSDN介绍 CreatePipe A pipe is a section of shared memory that processes use for communication. The pro ...
-
面试题汇总--数据储存/应用程序/UI控件/客户端的安全性与框架处理。。。
一 数据储存 1.如果后期需要增加数据库中的字段怎么实现,如果不使用 CoreData 呢?编写 SQL 语句来操作原来表中的字段1)增加表字段ALTER TABLE 表名 ADD COLUMN 字 ...
-
sublime如何实现函数折叠
Ctrl+Shift+[ 折叠代码 Ctrl+Shift+] 展开代码 Ctrl+KT 折叠属性 Ctrl+K0 展开所有
-
Python Django 之 Views HttpRequest HttpReponse
一.Python Django 之 Views 数据交互 http请求中产生两个人核心对象: http请求:HttpRequest对象 http响应:HttpReponse对象 所在位置django. ...
-
Android界面设计
从继承关系来看,所有组件继承自View.容器也是继承自View,它能容纳别的View. 所有容器继承自ViewGroup.包括 FrameLayout, LinearLayout, RelativeL ...