100 - The 3n + 1 problem

[rjhadley]

The goto statements make the code hard to read. The original code is almost identical to the while loop version I gave, except for how it handles the value of 1. The version with the goto statements is equivalent to:
[cpp]
do {
if( j % 2 > 0 ) {
j= ( 3 * j ) + 1;
x++;
} else {
j = j / 2;
x++;
} // if
} while( j > 1 );
[/cpp]
So when j = 1, the flow of the program enters the loop and j goes from 1 -> 4 -> 2 -> 1 and x = 4 when it exits the do-while loop.

In the while loop version, the condition ( j > 1 ) is false, and the program flow doesn't enter the loop, leaving x with a value of 1. (Which is the correct answer).

You probably should consult a C++ reference about namespaces. In short, they are used to control the scope of what is declared in the headers files, i.e. where and how you can use the functions, classes, objects, etc. that are declared in the headers. This is useful if you have a large amount of code, where two methods could end up with the same name (which would normally cause compile errors). For example, we can have two variables called number if we put them in different namespaces:

[cpp]
#include <iostream>

// without this we would need to be explicit and use "std::cout" instead of "cout"
using namespace std;

namespace Alpha {
int number = 2;
}; // namespace Alpha

namespace Beta {
int number = 4;
}; // namespace Beta

int
main( void )
{
cout << "Alpha: " << Alpha::number << endl;
cout << "Beta: " << Beta::number << endl;

return 0;
}
[/cpp]

And this will print out:

Alpha: 2
Beta: 4

Namespaces are kind of new, so your code will compile and work without the line [cpp]using namespace std;[/cpp] (At least with the version of the g++ compiler currently used by the judge).

[Neon]

I am calculating the right answers. But how do I terminate the program?

What I have done is, the program keeps looping until there is input, and terminates when something like ctrl-c is pressed. Is this fine?

I am doing this, because we dont know how many times the program should loop. I usually receive the time limit exceeded error. But I think that the code is fine.

Any input is welcome.

Neon.

[jasemty]

In my program, should I just read all lines of input first and generated all lines of output at the end?
I got "wrong answer" from the online judge system, but I found that I get correct answer when I input manually.
Thank you for your attention.

[ElSoloMar]

12 45
12 5
1 1 <----------- could it 0, 1, 3, ?
2 9
2 2 <----------- could it 1 or 2?
70 5000

What whould be the output for lines 3 and 5?

[ElSoloMar]

For this input

Code: Select all

1               1
1               2
2               2
1               3
4               4
1               5
1               10
10              1
100             200
201             210
900             1000

I obtain the following results

Code: Select all

1 1 1
1 2 2
2 2 2
1 3 8
4 4 8
1 5 8
1 10 20
10 1 20
100 200 125
201 210 89
900 1000 174

ANY SUGGESTIONS? !!!!!

[off_algos]

YES!
my program gives the following output for ur input set:

Code: Select all

1 1 1
1 2 2
2 2 2
1 3 8
4 4 3
1 5 8
1 10 20
10 1 20
100 200 125
201 210 89
900 1000 174

[off_algos]

the input ends with an end of file marker
in unix systems its ^d and in dos based systems its ^z
if your program terminates at this commands then your TLE is not due to problems in receivng input/output.
check if u exceed numerical limits that would make your program run n an infinite loop
eg:

Code: Select all

   while(i!=1)
{
if(i%2){i=3*i+1;}
else {i/=2;}
}

could run infinitely if i became neg(coz of exceeding limits)

[ElSoloMar]

It seems our difference is just in the way I handle when boths bound have
the same value. I can see where I am wrong now: I am considering any
case ' N N ' as ' 1 N ' and because of that I get 8 from ' 3 ' . That should be
easyly fix. Thanks you very much!!!!

[Noel]

Help! I can't find the problem?? thanks
[cpp]
/*@begin_of_source_code*/
#include<iostream>
using namespace std;
#define MAX 1000000
void main()
{
int i=0,j=0,temp,max;
while(1)
{
cin>>i>>j;
if(cin.eof() || cin.fail()) break;
if(i>MAX||j>MAX||i<=0||j<=0)
{
cerr<<endl;
break;
}
if(i>j)
{
temp=i;
i=j;
j=temp;
}
max=0;
for(int n=i;n<=j;n++)
{
temp=n;
int count=1;
if(temp==1)
{
count=1;
}
else
{
while(temp!=1)
{
if(temp%2) temp=3*temp+1;
else
temp=temp/2;
count++;
}
}
temp=count;
if(max<temp)
{
max=temp;
}
}
cout<<i<<" "<<j<<" "<<max<<endl;
}
}
/*@end_of_source_code*/[/cpp]

[route]

The values of i and j are swapped, so the order in the output is also wrong.

Example:
Input :
10 1
Output:
(should be)
10 1
(But you)
1 10

[27584NX]

Hi there ElSoloMar.
As described in the algorithm, your output for

1 1

is
1 1 1
Since we would print 1 once and then finish the loop.
For the second case:

2 2

is
2 2 2
Since we would print 2 once then divide by 2 and print 1, finishing the loop.
Try a for structure like this (if you are using C):

for ( i=min; i<=max; i++)

if min = max, we will run the code only once.
Be careful with the output ( send them in the original order ) and swap them if they come with the major number second.

See ya!

[Ed C]

Can someone plz tell me what's wrong:

[cpp]
#include <iostream>
using namespace std;
main (void)
{
int a, i, j, il, c;
while (cin >> i >> j)
{
cout << i << " " << j << " ";

if (i > j)
{
c = i;
i = j;
j = c;
}
c = 0;
for (int n = i; n <= j; n++)
{
a = n;
il = 1;
while (a != 1)
{
if ((a % 2) != 0)
a = (3 * a + 1);
else
a = (a / 2);
il++;
}

if (c < il)
c = il;
}

cout << c;
}
return 0;
}
[/cpp]

[Nick]

your logic isn't incorrect, but your program's output is the one causing problems
P100 wants you to ouput not only the max cycle length,but also the two input numbers
ex : INPUT -->10 100

OUTPUT should be --->10 100 119

also,
INPUT -->100 10
OUTPUT-->100 10 119

[yiuyuho]

And you forget to
cout<<c<<endl;

you used cout<<c;

which only allow one test data

And the output might not even be flushed to the console.

[Ed C]

Thanks I've sorted it now.