[SCOI2009]生日快乐

时间:2022-09-26 00:08:53

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

5 5 5

Sample Output

1.800000
先要把矩形分成n块,切n-1次
那先把矩形纵向(横向)均等分成n块
把它纵向(横向)按比例切一刀分成两个部分
假设第一部分占了i块,另一个占n-i块,即面积比为i:n-i
那么问题就递归转化成了把第一个矩形再切i-1刀,分成i块
第二个再切n-i-1刀,分成n-i块
这样最后切出的n个矩形面积肯定相同
每次在切出的2个矩形的最大比例中取最大值,看是否小于当前答案
横切和纵切一样,可以枚举i一起算
 #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]生日快乐的更多相关文章

  1. BZOJ 1024&colon; &lbrack;SCOI2009&rsqb;生日快乐 dfs

    1024: [SCOI2009]生日快乐 Time Limit: 20 Sec Memory Limit: 256 MB 题目连接 http://www.lydsy.com/JudgeOnline/p ...

  2. BZOJ 1023 &lbrack;SCOI2009&rsqb;生日快乐

    1024: [SCOI2009]生日快乐 Time Limit: 1 Sec  Memory Limit: 162 MBSubmit: 1729  Solved: 1219[Submit][Statu ...

  3. BZOJ 1024 &lbrack;SCOI2009&rsqb;生日快乐 &lpar;搜索&rpar;

    1024: [SCOI2009]生日快乐 Time Limit: 1 Sec  Memory Limit: 162 MBSubmit: 3025  Solved: 2201[Submit][Statu ...

  4. 【BZOJ1024】&lbrack;SCOI2009&rsqb;生日快乐(搜索)

    [BZOJ1024][SCOI2009]生日快乐(搜索) 题面 BZOJ 洛谷 题解 看到这个数据范围就感觉是爆搜.我们爆搜左右分成多少块,这样子左右的面积已知,再枚举一下横着切还是竖着切,这样子就可 ...

  5. bzoj千题计划115:bzoj1024&colon; &lbrack;SCOI2009&rsqb;生日快乐

    http://www.lydsy.com/JudgeOnline/problem.php?id=1024 枚举横着切还是竖着切,一边儿分多少块 #include<cstdio> #incl ...

  6. 【bzoj1024】&lbrack;SCOI2009&rsqb;生日快乐

    1024: [SCOI2009]生日快乐 Time Limit: 1 Sec  Memory Limit: 162 MBSubmit: 2372  Solved: 1717[Submit][Statu ...

  7. BZOJ1024 &lbrack;SCOI2009&rsqb;生日快乐

    本文版权归ljh2000和博客园共有,欢迎转载,但须保留此声明,并给出原文链接,谢谢合作. 本文作者:ljh2000作者博客:http://www.cnblogs.com/ljh2000-jump/转 ...

  8. BZOJ 1024&colon; &lbrack;SCOI2009&rsqb;生日快乐

    Description 将一个 \(x\times y\) 的矩形分成 \(n\) 块,让最长边:最短边 最小. Sol 搜索. \(n\) 只有 \(10\) 写一个类似于记搜的东西就好了. Cod ...

  9. 1024&colon; &lbrack;SCOI2009&rsqb;生日快乐

    暴力题,N<=10,没注意到平均分,读题真是.. 我们对于一个矩形分成两块进行搜.然后求较大值. ans=min(ans,max(dfs(x,y/n*i,i),dfs(x,y/n*(n-i),n ...

  10. 1024&colon; &lbrack;SCOI2009&rsqb;生日快乐 - BZOJ

    Description windy的生日到了,为了庆祝生日,他的朋友们帮他买了一个边长分别为 X 和 Y 的矩形蛋糕.现在包括windy,一共有 N 个人来分这块大蛋糕,要求每个人必须获得相同面积的蛋 ...

随机推荐

  1. &lbrack;NOIP2015&rsqb; 子串substring 题解

    [题目描述] 有两个仅包含小写英文字母的字符串A和B.现在要从字符串A中取出k个互不重叠的非空子串,然后把这k个子串按照其在字符串A中出现的顺序依次连接起来得到一个新的字符串,请问有多少种方案可以使得 ...

  2. iphone尺寸设计

    http://www.paintcodeapp.com/news/ultimate-guide-to-iphone-resolutions http://daily.zhihu.com/story/4 ...

  3. 未能加载文件或程序集&quot&semi;Microsoft&period;Web&period;Infrastructure&comma; Version&equals;1&period;0&period;0&period;0&comma; Culture&equals;neutral&comma; PublicKeyToken&equals;31bf3856ad

    问题: 未能加载文件或程序集"Microsoft.Web.Infrastructure, Version=1.0.0.0, Culture=neutral, PublicKeyToken=3 ...

  4. 九度OJ 1371 最小的K个数 -- 堆排序

    题目地址:http://ac.jobdu.com/problem.php?pid=1371 题目描述: 输入n个整数,找出其中最小的K个数.例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4 ...

  5. QF——OC的多态,动态绑定及实现原理

    多态: 封装,继承,多态是面向对象的三大特征. 那多态到底是什么呢? 多态:允许不同的类定义相同的方法,OC能自己判断当前类所对应的方法,不会混乱. 动态类型:程序直到运行时才确定对象的类型. 动态绑 ...

  6. WindowsAPI 之 CreatePipe、CreateProcess

    MSDN介绍 CreatePipe A pipe is a section of shared memory that processes use for communication. The pro ...

  7. 面试题汇总--数据储存/应用程序/UI控件/客户端的安全性与框架处理。。。

    一 数据储存  1.如果后期需要增加数据库中的字段怎么实现,如果不使用 CoreData 呢?编写 SQL 语句来操作原来表中的字段1)增加表字段ALTER TABLE 表名 ADD COLUMN 字 ...

  8. sublime如何实现函数折叠

    Ctrl+Shift+[ 折叠代码 Ctrl+Shift+] 展开代码 Ctrl+KT 折叠属性 Ctrl+K0 展开所有

  9. Python Django 之 Views HttpRequest HttpReponse

    一.Python Django 之 Views 数据交互 http请求中产生两个人核心对象: http请求:HttpRequest对象 http响应:HttpReponse对象 所在位置django. ...

  10. Android界面设计

    从继承关系来看,所有组件继承自View.容器也是继承自View,它能容纳别的View. 所有容器继承自ViewGroup.包括 FrameLayout, LinearLayout, RelativeL ...