핵심 아이디어

<aside> 💡

나올 수 있는 수를 정점으로 생각하여 BFS

이때 최단거리로 $k$에 도달한 횟수도 저장해야한다.

</aside>

코드

#include <bits/stdc++.h>
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
using namespace std;
typedef long long ll;

int n, k;

bool v[250'001];
int cnt[250'001];
int dist[250'001];

int ans = -1;

signed main()
{
    FASTIO;
    cin >> n >> k;

    memset(dist, 0x7f, sizeof dist);

    queue<pair<int, int>> q;
    q.push({n, 0});
    v[n] = true;
    dist[n] = 0;
    cnt[n] = 1;

    while(!q.empty()){
        auto[cur, d] = q.front();
        q.pop();

        int mn = cur-1;
        int pl = cur+1;
        int ml = 2*cur;
        if(mn>=0){
            if(!v[mn]){
                v[mn] = true;
                dist[mn] = d+1;
                q.push({mn, dist[mn]});
            }
            if(dist[mn] == d+1){
                cnt[mn]+=cnt[cur];
            }
        }
        if(pl<250'000){
            if(!v[pl]){
                v[pl] = true;
                dist[pl] = d+1;
                q.push({pl, dist[pl]});
            }
            if(dist[pl] == d+1){
                cnt[pl]+=cnt[cur];
            }
        }
        if(ml<250'000){
            if(!v[ml]){
                v[ml] = true;
                dist[ml] = d+1;
                q.push({ml, dist[ml]});
            }
            if(dist[ml] == d+1){
                cnt[ml]+=cnt[cur];
            }
        }
    }

    cout << dist[k] <<"\\n";
    cout << cnt[k] << "\\n";

    return 0;
}