4358392 2006-02-24 00:56:30 Accepted 2.207 4360 28565 C++ 100 - The 3n + 1 problem
~cpp #include <iostream> #include <vector> using namespace std; const int Min = 1; const int Max = 1000000; int table[Max]; struct Data { int num; int pre_count; }; void process() { vector<Data> data; Data temp; int i, j, k, count; unsigned long num; for(i = Min; i < Max; i++) { if(table[i] == 0) { num = i; count = 1; while(num != 1) { if(num % 2 == 0) { temp.num = num /=2; temp.pre_count = count++; if(num > Min && num < Max && table[num] == 0) data.push_back(temp); } else if(num % 2 != 0) { temp.num = num = num*3 + 1; temp.pre_count = count++; if(num < 0) cout << " 하하 " <<endl; if(num > Min && num < Max && table[num] == 0) data.push_back(temp); } } table[i] = count; for(j = i; j < Max; j *=2) table[j] = count++; for(k = 0; k < data.size(); k++) { count = table[i] - data[k].pre_count; for(j = data[k].num; j < Max; j *=2) table[j] = count++; } data.clear(); } } } int main() { int i, j, k, max_num; process(); // for(i =1; i < 20; i++) // cout << i << " " << table[i] << endl; // cout << table[999999]; while(cin >> i >> j) { cout << i << " " << j << " "; if(i > j) { k = j; j = i; i = k; } max_num = 0; for(k = i; k <= j; k++) { if(table[k] > max_num) max_num = table[k]; } cout << max_num << endl; } return 0; }