imported>Unknown at 05:22, 7 February 2021

2021-02-07T05:22:15Z

New page

4358392 2006-02-24 00:56:30 Accepted 2.207 4360 28565 C++ 100 - The 3n + 1 problem
#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;
}

3N 1/김상섭 - Revision history

imported>Unknown at 05:22, 7 February 2021