2015
04-16

Break the Chocolate

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.

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.

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.

2
1 1 3
2 2 2

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

#include <iostream>
#include <cstdio>
#define _int64 long long

using namespace std;

int main()
{
//freopen("1.txt","r",stdin);
int h,t;
_int64 n,m,k;
for (h=scanf("%d",&t);h<=t;h++)
{
scanf("%I64d%I64d%I64d",&n,&m,&k);
_int64 ans=n*m*k,now=1,cnt=0,u=0;
for (cnt=0,now=1;now<n;) cnt++,now<<=1; u+=cnt;
for (cnt=0,now=1;now<m;) cnt++,now<<=1; u+=cnt;
for (cnt=0,now=1;now<k;) cnt++,now<<=1; u+=cnt;
printf("Case #%d: %I64d %I64d\n",h,ans-1,u);
}
return 0;
}

1. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同，其树的前、中、后序遍历是相同的，但在此处不能使用中序遍历，因为，中序遍历的结果就是排序的结果。经在九度测试，运行时间90ms，比楼主的要快。

2. #include <cstdio>

int main() {
//answer must be odd
int n, u, d;
while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
if(n<=u) { puts("1"); continue; }
n-=u; u-=d; n+=u-1; n/=u;
n<<=1, ++n;
printf("%dn",n);
}
return 0;
}