You are viewing a single comment's thread. Return to all comments →
Solved using a bfs through the numbers
#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> #include <queue> using namespace std; int main() { int Q, n;cin >> Q; while(Q--) { cin >> n; queue<pair<int, int> > q; q.push(make_pair(n, 0)); vector<int> dist(n+1, 200000000); dist[n] = 0; while(!q.empty()){ int t = q.front().first; int steps = q.front().second; q.pop(); if(steps > dist[t]) continue; if(t == 0){ cout << steps << endl; break; } if(t < 0) continue; for(int i = 2; i < sqrt(t)+1; i++){ if(i == t)continue; if(t%i == 0){ int z = max(t/i, i); if(dist[z] <= steps+1) continue; dist[z] = steps+1; q.push(make_pair(z, steps+1)); } } if(dist[t-1] > steps +1 ){ dist[t-1] = steps+1; q.push(make_pair(t-1, steps+1)); } } } return 0; }
Seems like cookies are disabled on this browser, please enable them to open this website
Down to Zero II
You are viewing a single comment's thread. Return to all comments →
Solved using a bfs through the numbers