#include #include #include #include using namespace std; struct elem{ unsigned long int val; unsigned long int steps; unsigned long int eval; 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 = 37; elem* v = new elem[5000007];//vector v(100000000); while(a != 0 && b != 0){ steps++; unsigned 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%5000007 + hash*(c%4998231))%5000007].steps == steps){ hash ++; //if (hash) } v[(c%5000007 + hash*(c%4998231))%5000007].val = counter; v[(c%5000007 + hash*(c%4998231))%5000007].steps = steps; v[(c%5000007 + hash*(c%4998231))%5000007].eval = c; } //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); hash =0; while (v[(c%5000007 + hash*(c%4998231))%5000007].steps == steps){ if (v[(c%5000007 + hash*(c%4998231))%5000007].eval == c){ break; } hash ++; } if(v[(c%5000007 + hash*(c%4998231))%5000007].steps == steps){ if( a > b ){ cout << a << " needs " << counter << " steps, " << b << " needs " << v[(c%5000007 + hash*(c%4998231))%5000007].val << " steps, they meet at " << c << endl; } else{ cout << a << " needs " << v[(c%5000007 + hash*(c%4998231))%5000007].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 > b ){ 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; }