学步园

题意:

一块N*M*K的巧克力, 徒手掰一次掰一层, 用刀切可重叠. 问得到1*1*1的块最少的次数.

思路:

推公式...

首先考虑徒手掰:

对于一维的, n-1.

二维的, (m-1) + m*(n-1) = m*n - 1.

三维的, (k - 1) + k*(m*n - 1) = k*m*n - 1.

然后是用刀切:

对于一维的, lg n.

对于二维的, lg n + lg m.

三维的, lg n + lg m + lg k.

全部都是向上取整.

#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
int main()
{
    ll m,n,k;
    int T,cas = 0;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%I64d%I64d%I64d",&m,&n,&k);
        ll ans1 = n*m*k - 1;
        ll ans2 = (ll)(ceil(log(n*1.0)/log(2.0))+ceil(log(m*1.0)/log(2.0))+ceil(log(k*1.0)/log(2.0)));
        printf("Case #%d: %I64d %I64d\n",++cas,ans1,ans2);
    }
}

要push了~!