hdu 4112 Break the Chocolate（乱搞题）

题意：要把一块n*m*k的巧克力分成1*1*1的单元，有两种操作方式：1，用手掰（假设力量无穷大），每次拿起一块，掰成两块小的；2，用刀切（假设刀无限长），可以把多块摆在一起，同时切开。问两种方式各需多少次操作才能完成任务。

分析：用手掰很明显是（n*m*k-1）次操作。用刀切注意不是((n-1)+(m-1)+(k-1))次操作，这只是不动原巧克力的操作数。举个例子：1*1*4的巧克力，用刀切，按上面说的要3次操作，实际上只需2次。所以不管是长宽高，都只需要[log₂n]（或m,k）次操作。

注意：数据范围上限是2000，n*m*k后超出2³¹的范围，__int64

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define lld __int64

 using namespace std;

 lld ans;

 void Num(int x)

 {

     while(x>)

     {

         if(x%)

             x=x/+;

         else

             x=x/;

         ans++;

     }

     return ;

 }

 int main()

 {

     int T;

     lld n,m,k;

     scanf("%d",&T);

     for(int cnt=;cnt<=T;cnt++)

     {

         scanf("%I64d%I64d%I64d",&n,&m,&k);

         ans=;

         Num(n);

         Num(m);

         Num(k);

         printf("Case #%d: %I64d %I64d\n",cnt,n*m*k-,ans);

     }

     return ;

 }

巴特西

hdu 4112 Break the Chocolate（乱搞题）

最新文章

热门文章