HDU 4112Break the Chocolate（2011ACM成都赛区）Break the Chocolate

75 阅读 0 评论 50 点赞

我是靠谱客的博主拉长乌冬面，最近开发中收集的这篇文章主要介绍HDU 4112Break the Chocolate（2011ACM成都赛区）Break the Chocolate，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Break the Chocolate

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 427 Accepted Submission(s): 142

Problem Description

Benjamin is going to host a party for his big promotion coming up.
Every party needs candies, chocolates and beer, and of course Benjamin has prepared some of those. But as everyone likes to party, many more people showed up than he expected. The good news is that candies are enough. And for the beer, he only needs to buy some extra cups. The only problem is the chocolate.
As Benjamin is only a 'small court officer' with poor salary even after his promotion, he can not afford to buy extra chocolate. So he decides to break the chocolate cubes into smaller pieces so that everyone can have some.
He have two methods to break the chocolate. He can pick one piece of chocolate and break it into two pieces with bare hand, or put some pieces of chocolate together on the table and cut them with a knife at one time. You can assume that the knife is long enough to cut as many pieces of chocolate as he want.
The party is coming really soon and breaking the chocolate is not an easy job. He wants to know what is the minimum number of steps to break the chocolate into unit-size pieces (cubes of size 1 × 1 × 1). He is not sure whether he can find a knife or not, so he wants to know the answer for both situations.

Input

The first line contains an integer T(1<= T <=10000), indicating the number of test cases.
Each test case contains one line with three integers N,M,K(1 <=N,M,K <=2000), meaning the chocolate is a cube of size N ×M × K.

Output

For each test case in the input, print one line: "Case #X: A B", where X is the test case number (starting with 1) , A and B are the minimum numbers of steps to break the chocolate into N × M × K unit-size pieces with bare hands and knife respectively.

Sample Input

    2 1 1 3 2 2 2 
  

Sample Output

    Case #1: 2 2 Case #2: 7 3 
  

Source

2011 Asia ChengDu Regional Contest

初看感觉非常简单，但是陷阱很多！！！！！！

先把N,M,K从小到大排序。

然后用手扮的次数就是：（N-1）+N*（M-1+M*（K-1））=N*M*K-1；

就是先扮截面积最大的面，就是分最小的N，要N-1次，之后就有了N个M*K了，类似办法，要M-1+M*（K-1）；

但是这里一定要用long long ,int会超出的。（这里注意，比赛果然不一样，陷阱很多，下次注意了）

然后用到的时候。其实是分别切N,M,K。

切N是要[log2(N)]往上取整。往上取整我是加了0.999，不知道大牛们有没有更好的办法！！有的话请留言噢~~~~

切M和K类似。

具体看代码：

#include<stdio.h>
#include<math.h>
int main()
{
int T;
int iCase=0;
int n,m,k;
    scanf("%d",&T);
while(T--)
    {
        iCase++;
        scanf("%d%d%d",&n,&m,&k);
int t1=n,t2,t3=n;
if(m<t1)t1=m;
if(k<t1)t1=k;
if(m>t3)t3=m;
if(k>t3)t3=k;
        t2=n+m+k-t1-t3;
        n=t1;m=t2;k=t3;
int res=0;
if(n>1)res+=(int)(log(1.0*n)/log(2.0)+0.999);//往上取整 
        if(m>1)res+=(int)(log(1.0*m)/log(2.0)+0.999);
if(k>1)res+=(int)(log(1.0*k)/log(2.0)+0.999);
long long res1=(long long)n*m*k-1;
        printf("Case #%d: %I64d %dn",iCase,res1,res);
    }    
return 0;
}