Magic machine#4850

Magic machine (Editorial)

The idea:

The range of values is small: [1, 9999]. Therefore we can precompute the answer for every value reachable from a.

Define dis[x] = the minimum number of operations required to transform a into x.

We construct the directed graph of states where nodes are integers in [1,9999] and edges correspond to the allowed operations. The answer is obtained by running a breadth–first search (BFS) from the starting value a.

Implementation:

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
const int maxn = 1e4 + 5;

int dis[maxn];
int sum(int x){
  int sum = 0;
  while(x > 0){
    sum += x % 10;
    x /= 10;
  }
  return sum;
}
int main() {
  cin.tie(0)->sync_with_stdio(0);
  int a, b;
  cin >> a >> b;
  for(int i = 0; i <= 9999; i ++){
    dis[i] = INF;
  }
  dis[a] = 0; // We start from a

  queue<int>q;
  q.push(a);
  while(!q.empty()){
    int num = q.front();
    q.pop();

    // First button:
    int first = num * 3;

    if(0 <= first and first <= 9999){
      if(dis[first] > dis[num] + 1){
        dis[first] = dis[num] + 1;
        q.push(first);
      }
    }

    // Second button:
    int second = num + sum(num);

    if(0 <= second and second <= 9999){
      if(dis[second] > dis[num] + 1){
        dis[second] = dis[num] + 1;
        q.push(second);
      }
    }

    // Third button:
    int third = num - 2;

    if(0 <= third and third <= 9999){
      if(dis[third] > dis[num] + 1){
        dis[third] = dis[num] + 1;
        q.push(third);
      }
    }
  }
  cout << dis[b] << '\n';
}