#include #include #include #include using namespace std; struct elem{ int val; int steps; bool operator<(const elem& e)const{ return val < e.val; } bool operator==(const elem& e)const{ return val == e.val; } }; int main(){ int a, b; cin >> a >> b; int steps = 20; elem* v = new elem[8000007];//vector v(100000000); while(a != 0 && b != 0){ steps++; unsigned long long int c = min(a, b); int counter = 0; v[c].val = 0; v[c].steps = steps; int hash = 0; while(c != 1){ if(c%2 == 0){ c /= 2; } else{ c = 3*c + 1; } ++counter; hash =0; while (v[(c%1000007 + hash*(c%992421))%1000007].steps == steps){ //hash ++; //if (hash) } v[(c%1000007 + hash*(c%992421))%1000007].val = counter; v[(c%1000007 + hash*(c%992421))%1000007].steps = steps; } //sort(v, &v[100000000]); c = max(a, b); bool cond = true; counter = 0; while(c != 1 && cond){ elem e; e.val = c; //vector::iterator low = lower_bound(v.begin(), v.end(), e); if(v[(c%1000007 + hash*(c%992421))%1000007].steps == steps){ if( a > c ){ cout << a << " needs " << counter << " steps, " << b << " needs " << v[(c%1000007 + hash*(c%992421))%1000007].val << " steps, they meet at " << c << endl; } else{ cout << a << " needs " << v[(c%1000007 + hash*(c%992421))%1000007].val << " steps, " << b << " needs " << counter << " steps, they meet at " << c << endl; } break; } if(c%2 == 0){ c /= 2; } else{ c = 3*c + 1; } ++counter; if (c==1){ if( a > c ){ cout << a << " needs " << counter << " steps, " << b << " needs 0 steps, they meet at " << c << endl; } else { cout << a << " needs 0 steps, " << b << " needs " << counter << " steps, they meet at " << c << endl; } break; } } if (a==1 && b == 1){ cout << "1 needs 0 steps, 1 needs 0 steps, they meet at 1"<< endl; } cin >> a >> b; } return 0; }