首页 > 代码库 > 巧克力

巧克力

2024-11-02 23:17:02   204人阅读

巧克力

 

[Description]

 

yaoyiyao 带来了一块 N*M*K 的巧克力，但是这一天机房的人很多，为了公平，tsyao 提议先分成 1*1*1 的，然后每人那一块，剩下的给 yaoyiyao（毕竟是他的嘛）

 

但是 yaoyiyao 不想把力气花在这上面，于是就交给了 FinalSix 神牛，FinalSix 说我们应该用最小的代价来划分这个巧克力。

有两种划分方法：

 

①  用手，每次只能掰一块，至于从哪里掰随便

 

② 用刀，每次可以将几块巧克力重起来，然后从某个位置一刀切下来 FinalSix 不想动手算了，想知道分别使用这两种方法的最少次数分别是多少

 

[Input]

 

一行三个整数 N,M,K，之间用一个空格隔开

 

[Output]

 

两行，每行一个整数，分别表示两种方法的最少次数

 

[Sample 1]

 

chocolate.in

chocolate.out

 

 

1 1 3

2

 

2
 

 

[Sample 2]

 

 

 

chocolate.in

chocolate.out

 

 

2   2 2

7

 

3

 

 

[Hit]

 

对于 30%的数据 1<=N*M*K<=1000

 

对于 50%的数据 N,M,K 的最小质因数只有 2

 

对于 100%的数据 1<=N,M,K<=100000

 

 数学简单题，不必多说。

 

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<cstdlib>
 6 #include<algorithm>
 7 using namespace std;
 8 typedef long long lol;
 9 lol n,m,l,tot,ans;
10 lol gi()
11 {
12     lol ans=0,f=1;
13     char i=getchar();
14     while(i<‘0‘||i>‘9‘){if(i==‘-‘)f=-1;i=getchar();}
15     while(i>=‘0‘&&i<=‘9‘){ans=ans*10+i-‘0‘;i=getchar();}
16     return ans*f;
17 }
18 lol suan(lol x)
19 {
20     lol ans=0;
21     while(x)
22     {
23         if(x==1)break;
24         if(x&1)x++;
25         x>>=1;
26         ans++;
27     }
28     return ans;
29 }
30 int main()
31 {
32     freopen("chocolate.in","r",stdin);
33     freopen("chocolate.out","w",stdout);
34     lol i,j;
35     n=gi();m=gi();l=gi();
36     tot=n*m*l-1;
37     printf("%I64d\n",tot);
38     ans=suan(n)+suan(m)+suan(l);
39     printf("%I64d\n",ans);
40     return 0;
41 }

 

巧克力


联系
我们