Jzzhu has a big rectangular chocolate bar that consists of n × m unit squares. He wants to cut this bar exactly k times. Each cut must meet the following requirements:
- each cut should be straight (horizontal or vertical);
- each cut should go along edges of unit squares (it is prohibited to divide any unit chocolate square with cut);
- each cut should go inside the whole chocolate bar, and all cuts must be distinct.
The picture below shows a possible way to cut a 5 × 6 chocolate for 5 times.
Imagine Jzzhu have made k cuts and the big chocolate is splitted into several pieces. Consider the smallest (by area) piece of the chocolate, Jzzhu wants this piece to be as large as possible. What is the maximum possible area of smallest piece he can get with exactlyk cuts? The area of a chocolate piece is the number of unit squares in it.
A single line contains three integers n, m, k (1 ≤ n, m ≤ 109; 1 ≤ k ≤ 2·109).
Output a single integer representing the answer. If it is impossible to cut the big chocolate k times, print -1.
3 4 1
6
6 4 2
8
2 3 4
-1
In the first sample, Jzzhu can cut the chocolate following the picture below:
In the second sample the optimal division looks like this:
In the third sample, it's impossible to cut a 2 × 3 chocolate 4 times.
题意:
给出 n,m(1 ~ 10 ^ 9),k(2 X 10 ^ 9)代表给出一个 N * M 个的格子矩阵,后要求切 K 刀,使得出的最小方块的格子尽量大。输出这个格子数。
思路:
贪心。尽量多的横切或者尽量多的纵切。
AC:
#include <cstdio> #include <algorithm> #include <cstring> using namespace std; typedef long long ll; int main() { ll n, m, k; scanf("%I64d%I64d%I64d", &n, &m, &k); if (n + m - 2 < k) printf("-1\n"); else { ll maxn = 0; if (n > k) maxn = max(maxn, m * (n / (k + 1))); if (m > k) maxn = max(maxn, n * (m / (k + 1))); if (n <= k) maxn = max(maxn, m / (k - (n - 1) + 1)); if (m <= k) maxn = max(maxn, n / (k - (m - 1) + 1)); printf("%I64d\n", maxn); } return 0; }
相关推荐
If you are familiar with the origin of the DevOps term, and can’t wait to start facilitating the game, feel free to skip this chapter. Otherwise, read on to learn about...Chocolate, Lego and Scrum game.
Working with LEGO and chocolate, using avatars, personas, and role cards, you will gain an understanding of the Dev and Ops roles as well as their interdependencies. Throughout the game, players go ...
chocolate
Chocolate Chip CookiesChocolate Chip Cookies
chocolate.cache
amd CPU能用的巧克力内核chocolate_kernel
本源码是一个妄撮chocolate的安卓版小游戏的项目源码,项目本身比较比较小实现也比较简单,只有四个java文件,源码没有注释,这类游戏用一句话概况就是:挑战裸露极限满足偷窥欲(听起来好吊),就是这样,需要的...
Chocolate Doom旨在以一种可以在现代计算机上运行的形式,准确地复制Doom和其他基于Doom引擎的游戏的原始DOS版本。 最初,Chocolate Doom只是Doom的源端口。 该项目现在包括异端和赫克森的港口以及Strife。 ...
Wordpress Chocolate模板
chocolate巧克力英语演讲实用PPT课件.pptx
chocolate : github : Grabli66/chocolate 用法 需要最新的Crystal编译器来编译一些样本。 你好,世界 require " chocolate " include Zephyr include Chocolate get " / " do " Hello, world! " end listen { ...
09.Chocolate Competition Poised to Intensify in 2018
Coffee,Tea,Chocolate,and the Brain(咖啡,茶,巧克力与智力)是一份整理发布的食品资料文档...该文档为Coffee,Tea,Chocolate,and the Brain(咖啡,茶,巧克力与智力),是一份很不错的参考资料,具有较高参考...
Amaris Chocolate网站 作为里程碑项目1:以用户为中心的前端开发模块的一部分进行开发和设计。 样机响应图像是使用创建的。 目录 意象 图示 特征 现有功能 未来的实施 技术领域 测验 部署方式GitHub页面 学分 代码 ...
这是2017code jam round 2 problem A题目里的小测试数据