A. Jzzhu and Chocolate
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
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.
Input
A single line contains three integers n,?m,?k (1?≤?n,?m?≤?109; 1?≤?k?≤?2·109).
Output
Output a single integer representing the answer. If it is impossible to cut the big chocolate k times, print -1.
Sample test(s)
input
3 4 1
output
6
input
6 4 2
output
8
input
2 3 4
output
-1
Note
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的方格块，要求切k次，使其中最小的一块最大，求这个值（方格块边缘不能切）
分析：
我们假设n>m,所以下面横着切是最多的
无解的时候：n行分块最多切n-1次，n-1+m-1<k
画几次切图，我们不难发现一个贪心规律（一横+一竖肯定使其分割的最小的那个方格块更小），最好沿着一个方向切，横着切就要把横着的都切完，竖着就要把竖着的都切完。
1. 当k<=m-1时候，
横着切满或者竖着切满，
ans=max(ans,m/(k+1)*n);
ans=max(ans,n/(k+1)*m);k+1：一刀能够把一方格块分成两部分，两刀就三个部分
2.k<=n-1
横着切满就行
ans=max(ans,n/(k+1)*m);
3.k>=n
竖着切满+剩下的横着切
或者横着切满+剩下的竖着切
ans=max(ans,n/(k-(m-1)+1)*1);
ans=max(ans,m/(k-(n-1)+1)*1);式子具体含义画一下图就ok
#include <bits/stdc++.h>
#define mod 1000000007
#define ll long long
using namespace std;
int main(){ll n,m,k;scanf("%lld%lld%lld",&n,&m,&k);if((n-1)+(m-1)<k) printf("-1\n");else if((n-1)+(m-1)==k)printf("1\n");else{if(m>n) {ll t=n;n=m;m=t;}ll ans=-100;if(k<=m-1){ans=max(ans,m/(k+1)*n);ans=max(ans,n/(k+1)*m);}else if(k<=n-1){ans=max(ans,n/(k+1)*m);//ans=max(ans,n/(k-(m-1)+1)*1);}else{ans=max(ans,n/(k-(m-1)+1)*1);ans=max(ans,m/(k-(n-1)+1)*1);}printf("%lld\n",ans);}return 0;
}