HDU - 4112 Break the Chocolate
Problem Description
Benjamin is going to host a party fZ†·Ÿ"http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vciBoaXMgYmlnIHByb21vdGlvbiBjb21pbmcgdXAuPGJyPgpFdmVyeSBwYXJ0eSBuZWVkcyBjYW5kaWVzLCBjaG9jb2xhdGVzIGFuZCBiZWVyLCBhbmQgb2YgY291cnNlIEJlbmphbWluIGhhcyBwcmVwYXJlZCBzb21lIG9mIHRob3NlLiBCdXQgYXMgZXZlcnlvbmUgbGlrZXMgdG8gcGFydHksIG1hbnkgbW9yZSBwZW9wbGUgc2hvd2VkIHVwIHRoYW4gaGUgZXhwZWN0ZWQuIFRoZSBnb29kIG5ld3MgaXMgdGhhdCBjYW5kaWVzIGFyZSBlbm91Z2guIEFuZCBmb3IgdGhlIGJlZXIsIGhlIG9ubHkgbmVlZHMgdG8gYnV5CiBzb21lIGV4dHJhIGN1cHMuIFRoZSBvbmx5IHByb2JsZW0gaXMgdGhlIGNob2NvbGF0ZS48YnI+CkFzIEJlbmphbWluIGlzIG9ubHkgYSA="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
ÌâÒ⣺¸øÄãÁ¢·½ÌåµÄÇÉ¿ËÁ¦£¬ÈÃÄãÓÃÊÖêþ£¬ºÍÓõ¶ÇÐŪ³É1*1*1µÄСÇÉ¿ËÁ¦·Ö±ð×îÉÙÓöàÉÙ£¬Óõ¶ÇУ¬¿ÉÒÔ²»¹ÜÓжàÉÙ¿é
˼·£ºêþµÄ»°£¬¿Ï¶¨Òªsum-1´Î£¬ÇеĻ°£¬ÒòΪ¿ÉÒÔ¶à¿éÒ»ÆðÇУ¬ËùÒÔÎÒÃÇ·Ö±ð¿¼Âdz¤£¬¿í£¬¸ß£¬·Ö±ðÒª¶àÉٴΣ¬²ÅÄÜÇгÉС¿é£¬½á¹ûÊÇlog2(len),·Ö±ðͳ¼ÆÏà¼Ó¾ÍÊÇÁË
#include
#include
#include
#include
#include
typedef long long ll;
using namespace std;
int main() {
int t, n, m, k, cas = 1;
scanf("%d", &t);
while (t--) {
scanf("%d%d%d", &n, &m, &k);
ll ans = 1ll * n * m * k;
int cnt = 0;
cnt += ceil(1.0 * log(n) / log(2));
cnt += ceil(1.0 * log(m) / log(2));
cnt += ceil(1.0 * log(k) / log(2));
printf("Case #%d: ", cas++);
cout << ans-1 << " " << cnt << endl;;
}
return 0;
}
