CodeForces 520B Two Buttons
Description
Vasya has found a strange device. On the front panel of a device there are: a red button, a blue button and a display showing some positive integer. After clicking the red button, device multiplies the displayed number by two. After clicking the blue button, device subtracts one from the number on the display. If at some point the number stops being positive, the device breaks down. The display can show arbitrarily large numbers. Initially, the display shows number n.
Bob wants to get number m on the display. What minimum number of clicks he has to make in order to achieve this result?
Input
The first and the only line of the input contains two distinct integers n and m (1 ≤ n, m ≤ 104), separated by a space .
Output
Print a single number — the minimum number of times one needs to push the button required to get the number m out of number n.
Sample Input
4 6
2
10 1
9
Hint
In the first example you need to push the blue button once, and then push the red button once.
In the second example, doubling the number is unnecessary, so we need to push the blue button nine times.
思路1:math 对于n < m时,从m出发,若m为偶数,m减半,否则,加1减半(对应结果加1),直到m <= n
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int n, m;
void solve()
{
cin >> n >> m;
if(n >= m) {cout << n - m << endl;return;}
int ans = ;
while(n < m)
{
if(m & ) {ans++;m++;}
m >>= ;
ans++;
}
ans += n - m;
cout << ans << endl;
}
int main()
{
solve();
return ;
}
思路2:bfs + 剪枝(记忆化)
/*times memy
78ms 2104k
by orc
*/
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
int n ,m;
bool vis[];//此处的vis标记数组并不是像以往一样标记有没有做过而做到不走重复路径
struct node{ //这里是做备忘录,记忆化搜索
int x;
int cnt;
};
void bfs(node v)
{
memset(vis,false,sizeof vis);
queue<node> que;
que.push(v);
node now, nex;
while(!que.empty())
{
now = que.front();
que.pop();
if(vis[now.x]) continue;
if(now.x <= ) continue;//既然要做备忘录,那么下标就不能为0
if(now.x > m){ //重要剪枝,若now.x > m, 即now.x * 2就没必要入队,只能通过 - 1 来达到状态m
nex.x = now.x - ;
nex.cnt = now.cnt + ;
que.push(nex);
continue;
}
if(now.x == m) {cout << now.cnt << endl; return;}
nex.x = now.x - ;
nex.cnt = now.cnt + ;
que.push(nex);
nex.x = now.x * ;
nex.cnt = now.cnt + ;
que.push(nex);
vis[now.x] = true;//循环结尾处对当前出队元素now标记
}
}
int main()
{
cin >> n >> m;
if(n >= m) cout << n - m << endl;
else
{
node v;
v.x = n;
v.cnt = ;
bfs(v);
}
}
最新文章
- Spring-----定时任务Quartz配置
- jsoup 简介
- C# Socket网络编程精华篇(转)
- 浅谈管道模型(Pipeline)
- CF 13E Holes 【块状链表】
- 【Java面试】基础知识篇
- linux下TUN/TAP虚拟网卡的使用
- 看望朋友(家达)--->;>;对事情的专注及时间效率学习
- fast ai-lesson 1 报错解决方法(正则表达式提取文件名)
- 复制ASP.NET的ASHX、aspx文件的注意事项
- 封装qq分享静态库到cocopod
- 洛谷 P1112 波浪数
- NOIP2012 Day1 T2国王游戏 洛谷P1080
- #Python学习#python虚拟环境——virtualenv
- 在docker中执行linux shell命令
- 远程连接MySQL数据库报错:is not allowed to connect to this MYSQL server的解决办法
- PHP中预定义超全局数组(变量)
- HDU 6462.人类史上最大最好的希望事件-递推 (“字节跳动-文远知行杯”广东工业大学第十四届程序设计竞赛)
- jQuery二级下拉菜单
- Oracle9i之xmltype应用(1)