小招喵跑步

/*单序列的dp问题，在点n处三种方式，根据n的奇偶性来进行讨论
dp[i]：
1.当i是偶数，dp[i/2]+1
2.当i是奇数,dp[(i+1)/2]+2,dp[i-1]+1
3.每个位置先进行初始化，然后就是上面两种情况下多取一下Min
*/
#include <iostream>
#include <vector>
using namespace std;
class Solution{
public:
    int solve(int n){
        if(n<=3)
            return n;
        vector<int> dp(n+1,0);
        //先进行初始化
        dp[1]=1,dp[2]=2,dp[3]=3;
        for(int i=4;i<=n;++i){ //1，2,3不用进行讨论，无论如何就那么几步
            if(i%2==0)
                dp[i]=min(dp[i-1]+1,dp[i/2]+1);
            else
                dp[i]=min(dp[(i+1)/2]+2,dp[i-1]+1);
        }
        return dp[n];
    }
};
int main(){
    int n; //想去的位置
    cin>>n;
    if(n>=0 && n<3){
        cout<<n;
        return 0;
    }
    Solution sol;
    if(n<0)
        cout<<sol.solve(-n);
    else
        cout<<sol.solve(n);
    return 0;
}
/*对于dp的题，其实也是个惯式
1.单序列的dp，那么就是找i+1位置和i位置的联系
2.双序列的dp，那么就是一个二维vec存结果，那么无非就是dp[i][j]与dp[i-1][j],dp[i][j-1],dp[i-1][j-1]三者之间的联系
3.矩阵的dp，这个就比较简单了，直接顺着来即可
总结可以看我给出的各类的例子：
https://blog.csdn.net/qq_26896213/article/details/86507685
*/

/*
参考答案；动态规划
dp[i]表示到达i点的最少步数。
最少就需要考虑两倍的走法
状态转移：
当前位置能被二整除，dp[i] = dp[i/2]+1;
当前位置不能被二整除，dp[i] = min(dp[i-1],dp[i+1/2]+1) + 1

dp[i+1/2]+1这个表示后移一步，比如说i=5,那么可以有dp[4] + 1,也可以有dp[6]+1,
而这里的dp[6]很显然是个偶数，那他的步数就一定是dp[3]+1
*/
import java.math.*;
import java.lang.Math;
import java.util.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader((new InputStreamReader(System.in)));
        int x = Integer.parseInt(br.readLine());
        if(x < 0){
            x = -x;
        }
        if(x == 0){
            System.out.println(0);
            return;
        }
        int[] step = new int[x+1];
        step[0] = 0;
        step[1] = 1;
        for(int i = 2; i < x + 1; i++){
            if(i % 2 == 0){
                step[i] = step[i/2]+1;
            }else{
                step[i] = Math.min(step[i -1], step[(i+1)/2]+ 1) + 1;
            }
        }
        System.out.println(step[x]);
    }
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @author wylu
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int x = Math.abs(Integer.parseInt(br.readLine()));

        int res = 0;
        while (x != 0) {
            if (x % 2 == 0) x >>= 1;
            else x += ((x + 1) / 2 % 2 == 0 && x > 3) ? 1 : -1;
            res++;
        }
        System.out.println(res);
    }
}

/**
 * 小招喵跑步
 * 小招喵喜欢在数轴上跑来跑去，假设它现在站在点n处，它只会3种走法，分别是：
 * 1.数轴上向前走一步，即n=n+1
 * 2.数轴上向后走一步,即n=n-1
 * 3.数轴上使劲跳跃到当前点的两倍，即n=2*n
 * 现在小招喵在原点，即n=0，它想去点x处，快帮小招喵算算最快的走法需要多少步？
 * 输入描述:
 * 小招喵想去的位置x
 * 输出描述:
 * 小招喵最少需要的步数
 * 输入例子1:
 * 3
 * 输出例子1:
 * 3
 */
public class RunningCat {

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int x = scanner.nextInt();
        System.out.println(countQuickSteps(x));
    }

    private static long countQuickSteps(long x) {
        if (x < 0)
            x = -x;
        long quickSteps;
        if (x == 0)
            return 0;
        if (x == 1)
            return 1;
        if (x == 2)
            return  2;
        if (x % 2 == 0){
            quickSteps = countQuickSteps(x/2) + 1;
        }else {
            long q1 = countQuickSteps((x+1) / 2) + 2;
            long q2 = countQuickSteps((x-1) / 2) + 2;

            quickSteps = Math.min(q1,q2);
        }
        return quickSteps;
    }


}

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    scanf("%d", &n);
    n = abs(n);
    int dp[n+1];
    dp[0] = 0;
    dp[1] = 1;
    for(int i=2;i<=n;i++){
        if(i & 1)
            dp[i] = min(dp[i-1], dp[(i+1)/2]+1) + 1;
        else
            dp[i] = min(dp[i-1], dp[i/2]) + 1;
    }
    printf("%d\n", dp[n]);
    return 0;
}

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <climits>
#include <queue>
using namespace std;

// 考虑用bfs找最短路径的做法，类似于单源最短路径求解
// 每次遍历一点，把从当前点，一步可达达的点的距离都更新，如果可达点距离更新了
// 则把他们入队，最终迭代直到队为空
// 考虑当前点一步可达，有几种情况，前进一步，后退一步，当前点*2的点
// 每种情况如果点合法，并且最短距离可以更新，则把此点入队

class Solution {
public:
    int minStep(int n);
};

int Solution::minStep(int n) {

    if (n < 0)
        n = (-1) * n;

    vector<int> distance(n+1, INT_MAX);
    distance[0] = 0;
    queue<int> q; q.push(0);

    while (!q.empty()) {
        int idx = q.front();
        q.pop();

        if (idx + 1 <= n) {
            if (distance[idx + 1] > distance[idx] + 1) {
                distance[idx + 1] = distance[idx] + 1;
                q.push(idx + 1);
            }
        }

        if (idx * 2 <= n) {
            if (distance[idx * 2] > distance[idx] + 1) {
                distance[idx * 2] = distance[idx] + 1;
                q.push(idx * 2);
            }
        }
        if (idx - 1 >= 0) {
            if (distance[idx - 1] > distance[idx] + 1) {
                distance[idx - 1] = distance[idx] + 1;
                q.push(idx - 1);
            }
        }
    }
    return distance[n];
}

int main(void) {
    Solution solu;
    int pos;
    while (cin >> pos) {
        cout << solu.minStep(pos) << endl;
    }
    return 0;
}

#include <iostream>
#include <vector>
 
using namespace std;
 
// 想到位置x处
int process(int x) {
    if (x < 2) {
        return x;
    }
    vector<int> dp(x + 1);
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= x; ++i) {
        if (i % 2 == 0) { // 能整除 // 必然跳更快
            dp[i] = 1 + min(dp[i-1], dp[i / 2]);
        } else {
            dp[i] = 1 + min(dp[i-1], 1 + dp[(i + 1) / 2]);
        }
    }
    return dp[x];
}
 
int main() {
    int x = 0;
    while (cin >> x) {
        cout << process(abs(x)) << endl;
    }
    return 0;
}

def count(n):
    if n<0:
        n = -n
    if n==0:
        return 0
    if n==1:
        return 1
    if n%2==0:
        return count(n//2)+1
    else:
        r1 = count((n+1)//2)+2
        r2 = count((n-1)//2)+2
        return min(r1,r2)

x = int(input())
if x<0: x=-x
dp = [0]*(x+2)
dp[1] = 1
for i in range(2,x+1):
    if i%2 == 0:
        dp[i] = dp[i//2] + 1
    else:
        dp[i] = min(dp[i-1]+1, dp[(i+1)//2]+2)
print(dp[x])

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int target;
    cin>>target;
    
    if (target == 0) {
        cout<<0;
        return 0;
    }

    target = target > 0 ? target : -target;

    int curr = 1;
    vector<int> count(target + 2, 0);
    count[0] = 0;
    count[1] = 1;
    count[2] = 2;

    for (int i = 3; i <= target + 1; ++i) {
        if (i % 2 == 0) {
            // 先找到当前偶数的最小距离
            count[i] = min(count[i-1]+1, count[i/2]+1);
            // i-1一定是奇数，奇数也可能从+1地方到达
            count[i-1] = min(count[i-1], count[i]+1);
        } else { // 奇数时一定从偶数+1
            count[i] = count[i-1]+1;
        }
    }
    cout<<count[target];
}

x = int(input())
i = 0
x = abs(x)
while x != 0:
    if x % 2 == 0:
        x = x/2
        i += 1
    elif x % 4 == 3 and x != 3:
        x += 1
        i += 1
    elif x % 4 == 1:
        x -= 1
        i += 1
    else:
        x = 0
        i += 3
print(i)

# 笨比算法 考拉兹猜想的变形

class Solution:
#     最少需要考虑两倍走法
    def minSteps(self, x: int) -> int:
        if x == 0&nbs***bsp;x == 1:
            return x
        
        if x < 0:
            x = (-1) * x
        
        dp = [x] * (x + 1)
        dp[0] = 0
        dp [1] = 1
        
        for i in range(2, x + 1):
            if i % 2 == 0:
                dp[i] = dp[i // 2] + 1   # 就算整除也会变成浮点数
            else:
                dp[i] = min(dp[(i + 1) // 2] + 2, dp[(i - 1) // 2] + 2)
                
        return dp[-1]
    
if __name__ == '__main__':
    x = int(input())
    my_solution = Solution()
    result = my_solution.minSteps(x)
    print(result)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n; cin >> n; n = abs(n);
    if (n == 0) { cout << 0; return 0; }
    int dp[n];
    dp[0] = 0; dp[1] = 1; dp[2] = 2;
    for (int i=3; i<=n; i++) {
        if (i % 2 != 0) {   // 奇数位置：三种位置
            dp[i] = min(dp[i-1]+1, dp[(i-1)/2]+2);
            dp[i] = min(dp[i], dp[(i+1)/2]+2);
        } else {   // 偶数位置：只需要一种
            dp[i] = dp[i/2] + 1;
        }
    }
    cout << dp[n] << endl;
    return 0;
}

#include<iostream>
#include<queue>
#include<cstdio>
#include<unordered_set>
using namespace std;
int main(){
    int x;
    cin >> x;
    queue<int> q;
    unordered_set<int> s;
    q.push(0);
    s.insert(0);
    int step = 0;
    while(!q.empty()){
        int sz = q.size();
        while(sz--){
            int t = q.front();
            if(t == x){
                //printf("nmsl\n");
                printf("%d",step);
                return  0;
            }
            q.pop();
            if(s.find(t + 1) == s.end()){
                q.push(t+1);
                s.insert(t+1);
            }
            if(s.find(t-1) == s.end()){
                q.push(t-1);
                s.insert(t-1);
            }
            if(s.find(2*t) == s.end()){
                q.push(2*t);
                s.insert(2*t);
            }
        }
        step++;
    }
}

import java.util.*;
public class Main{
    /*public static void main(String[] args){//BFS
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        if(x==0){
            System.out.println(0);
            return;
        }
        LinkedList<Integer> list = new LinkedList<Integer>();
        list.add(0);
        int step = 0;
        while(true){
            step++;
            int size = list.size();
            for(int i=0;i<size;i++){
                int tmp = list.pop();
                if(tmp+1!=x){
                    list.add(tmp+1);
                }else{
                    System.out.println(step);
                    return;
                }
                if(tmp-1!=x){
                    list.add(tmp-1);
                }else{
                    System.out.println(step);
                    return;
                }
                if(tmp*2!=x){
                    list.add(tmp*2);
                }else{
                    System.out.println(step);
                    return;
                }
            }
        }
    }*/
    public static void main(String[] args){//dp
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        if(x==0){
            System.out.println(0);
            return;
        }
        if(x<0)x=-x;
        int[] dp = new int[x+1];
        dp[0] = 0;
        dp[1] = 1;
        for(int i=2;i<=x;i++){
            if(i%2==0){
                dp[i]=dp[i/2]+1;
            }else{
                dp[i]=Math.min(dp[i-1]+1,dp[(i+1)/2]+2);
            }
        }
        System.out.println(dp[x]);
    }
}