ccbeginner

UVa Q11730

Jan 4th, 2020
110
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //UVa Q11730
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. vector<int> prm;
  6. int vis[1001];
  7.  
  8. void init(){
  9.     prm.emplace_back(2);
  10.     for(int i = 3; i < 1000; i += 2){
  11.         bool yes = 1;
  12.         for(int j = 0; j < prm.size(); ++j){
  13.             if(i % prm[j] == 0){
  14.                 yes = 0;
  15.                 break;
  16.             }
  17.         }
  18.         if(yes)prm.emplace_back(i);
  19.     }
  20. }
  21.  
  22. int main(){
  23.     init();
  24.     int cnt = 0;
  25.     int s,t;
  26.     while(cin >> s >> t){
  27.         if(s == 0 && t == 0)break;
  28.         ++cnt;
  29.         if(s == t){
  30.             cout << "Case " << cnt << ": 0\n";
  31.             continue;
  32.         }
  33.         int ans = -1;
  34.         memset(vis, 0, sizeof(vis));
  35.         deque<int> dq;
  36.         dq.emplace_back(s);
  37.         while(!dq.empty() && ans == -1){
  38.             int tmd = dq.front();
  39.             dq.pop_front();
  40.             //cout << tmd << endl;
  41.             for(int i = 0; i < prm.size() && prm[i] < tmd && ans == -1; ++i){
  42.                 int nxt = tmd+prm[i];
  43.                 if(nxt > t)break;
  44.                 if(tmd % prm[i] == 0 && !vis[nxt]){
  45.                     if(nxt == t)ans = vis[tmd] + 1;
  46.                     else{
  47.                         vis[nxt] = vis[tmd] + 1;
  48.                         dq.emplace_back(nxt);
  49.                     }
  50.                 }
  51.             }
  52.         }
  53.         cout << "Case " << cnt << ": " << ans << '\n';
  54.     }
  55.     return 0;
  56. }
RAW Paste Data