Advertisement
Josif_tepe

Untitled

Oct 27th, 2024
65
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.45 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <vector>
  4. using namespace std;
  5.  
  6.  
  7. int main() {
  8.     int p, n;
  9.     cin >> p >> n;
  10.    
  11.     queue<int> q;
  12.     vector<bool> visited(14, false);
  13.     for(int i = 0; i < n; i++) {
  14.         int x;
  15.         cin >> x;
  16.         visited[x] = true;
  17.     }
  18.    
  19.     vector<bool> vis(100000, false);
  20.     q.push(100);
  21.     q.push(0);
  22.     vis[100] = true;
  23.     for(int i = 0; i < 99999; i++) {
  24.         bool moze = true;
  25.         int x = i;
  26.         int cnt = 0;
  27.         while(x > 0) {
  28.             int digit = x % 10;
  29.             if(visited[digit]) {
  30.                 moze = false;
  31.                 break;
  32.             }
  33.             cnt++;
  34.             x /= 10;
  35.            
  36.         }
  37.         if(moze and i != 100) {
  38.             q.push(i);
  39.             q.push(cnt);
  40.             vis[i] = true;
  41.         }
  42.     }
  43.    
  44.     while(!q.empty()) {
  45.         int number = q.front();
  46.         q.pop();
  47.         int dist = q.front();
  48.         q.pop();
  49.        
  50.         if(number == p) {
  51.             cout << min(dist, p - 100) << endl;
  52.             return 0;
  53.         }
  54.        
  55.         if(number + 1 < 100000 and !vis[number + 1]) {
  56.             q.push(number + 1);
  57.             q.push(dist + 1);
  58.             vis[number + 1] = true;
  59.         }
  60.         if(number - 1 >= 0 and !vis[number - 1]) {
  61.             q.push(number - 1);
  62.             q.push(dist + 1);
  63.             vis[number - 1] = true;
  64.         }
  65.     }
  66.    
  67.     return 0;
  68. }
  69.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement