Atcoder 2373 Cookie Exchanges
Problem Statement
Takahashi, Aoki and Snuke love cookies. They have A, B and C cookies, respectively. Now, they will exchange those cookies by repeating the action below:
- Each person simultaneously divides his cookies in half and gives one half to each of the other two persons.
This action will be repeated until there is a person with odd number of cookies in hand.
How many times will they repeat this action? Note that the answer may not be finite.
Constraints
- 1≤A,B,C≤109
Input
Input is given from Standard Input in the following format:
A B C
Output
Print the number of times the action will be performed by the three people, if this number is finite. If it is infinite, print -1
instead.
Sample Input 1
4 12 20
Sample Output 1
3
Initially, Takahashi, Aoki and Snuke have 4, 12 and 20 cookies. Then,
- After the first action, they have 16, 12 and 8.
- After the second action, they have 10, 12 and 14.
- After the third action, they have 13, 12 and 11.
Now, Takahashi and Snuke have odd number of cookies, and therefore the answer is 3.
Sample Input 2
14 14 14
Sample Output 2
-1
Sample Input 3
454 414 444
Sample Output 3
1 a==b==c的时候会死循环,其他情况暴力算就行了,因为每一次操作之后最大值-最小值会减半,所以不久就能到达终止条件。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int A,B,C,tot,a,b,c;
int main(){
scanf("%d%d%d",&A,&B,&C);
while(!((A&1)||(B&1)||(C&1))){
if(A==B&&B==C){
puts("-1");
return 0;
} tot++,a=(B+C)>>1,b=(A+C)>>1,c=(B+A)>>1;
A=a,B=b,C=c;
} printf("%d\n",tot);
return 0;
}
最新文章
- Dynamic Virtual Channels
- css 默认样式
- 2014年度辛星html教程夏季版第八节
- FFmpeg发送流媒体的命令(UDP,RTP,RTMP)
- USB C和USB 3.1傻傻分不清?这篇文章可以帮你
- Android项目代码混淆
- 用Python满足满足自己的“小虚荣”
- 有关this
- laravel源码解析
- sort a given string
- Python 文件 writelines() 方法
- jeecg删除菜单导致角色权限设置点不开的问题解决
- 2. K-Means的优化
- socket接口详解
- -no-xrender will disable the qtwebkit
- 如何使用STM32F4的BootLoader和APP程序
- 《Maven实战》关联实际工作的核心知识
- hdu 3790 最短路径问题(双重权值,dijkstra算法)
- BZOJ 1221 [HNOI2001] 软件开发(费用流)
- django 模板实现换行