100 - The 3n + 1 problem

[r.z.]

Yes I've found the bug yesterday and finally got accepted

why I keep doing mistakes like this....

[Dominik Michniewski]

I don't agree with you, Zhao Le. I always read only actual case(in all problems), compute answer and output it. I got problem 100 in the same way, so I think that's no bug in it . I've got Accepted over 500 problems so I think, that you don't have right ...

Best regards
DM

[Zhao Le]

Here is my code of #100.

Here is WA.
[cpp]#include <iostream>

using namespace std;

void main()
{
long i,j,n;
while(cin>>i>>j)
{
long max=0;
cout<<i<<" "<<j<<" ";
if(i>j)
{
long tmp=j;
j=i;
i=tmp;
}
for(long t=i;t<=j;t++)
{
long c=1;
n=t;
while(n!=1)
{
c++;
if(n%2==1) n=3*n+1;
else n/=2;
}
if(c>max) max=c;
}
cout<<max<<endl;
}

}[/cpp]

Here is AC.

[cpp]#include <iostream>

using namespace std;

class S
{
public:
int i,j;
int max;
S *next;
};

void main()
{
long i,j,n;
S *head=NULL,*p,*q;
while(cin>>i>>j)
{
long max=0;
p=new S;
if(head==NULL) head=p;
else q->next=p;
p->i=i;
p->j=j;
if(i>j)
{
long tmp=j;
j=i;
i=tmp;
}
for(long t=i;t<=j;t++)
{
long c=1;
n=t;
while(n!=1)
{
c++;
if(n%2==1) n=3*n+1;
else n/=2;
}
if(c>max) max=c;
}
p->max=max;
p->next=NULL;
q=p;
}
for(p=head;p;p=p->next)
{
cout<<p->i<<" "<<p->j<<" "<<p->max<<endl;
}

}[/cpp]

Can you explain to me the problem?

This is my first ACM but is more than 2 weeks did nothing then.

And from 500 AC of it point any flaw to me.

Thanks in advance.

[Dominik Michniewski]

Both of codes looks similar ...
Did you try to compile it both and check if both of them give you the same results in all cases ?? many is small mistake in one of them ?
I don't know - if I will have time, I try to check it ....

Best regards
DM

[fibonacci]

I'm sure there's something simple I'm missing me that's giving me a wrong answer...

[cpp]
#include <iostream.h>
void main()
{
int i, j,total=0, ti, tj, temp,max=0, t;
while(cin >> i >> j)
{
// which is larger
if (i > j)
{
t = i;
i = j;
j = t;
}
ti = i; tj=j, temp=0;

for (int x = i; x <= j; x++ )
{
temp = x;
while (temp != 1)
{
if (temp%2 == 0)
{
temp/=2;
total++;
} else
{
temp*=3;
temp++;
total++;
}

}

if (total > max)
max = ++total;
total = 0;
}

cout << ti << " " << tj << " " << max << endl;
max = 0;
}
}
[/cpp]

[Zhao Le]

I don't understand.

Please Please Please Please don't make the assert so quickly.

I change the fisrt to the second one and got AC.

So there is nothing wrong in the first I'm sure.

Who can help me?

[Zhao Le]

Try to use multiinput multioutput tech.

I use got AC. you can see the difference in my codes.

http://acm.uva.es/board/viewtopic.php?t=3015

[Hisoka]

hello fibonacci....

your mistake are :
1. if i < j, you must swap them, but for output you must print like your input.

Code: Select all

if (i > j)
   {
      t = i;
      i = j;
      j = t;
   }
   ti = i; tj=j;

you must put ti = i; tj = j; before swap.

2.

Code: Select all

      if (total > max)
         max = ++total;
         total = 0;
   }

if like this, when total = max, you cannot put into max. I mean like this :
if total = 10 so cycle lenght is 11 ( base on your code ). if max = 10, so cycle lenght max = 10 not 11. and the true answer cycle lenght max = 11.

GOOD LUCK...

[fpnc]

I've sent the first source code and I got accepted:

http://acm.uva.es/cgi-bin/OnlineJudge?S ... 97:1.00:60::

So check your method of submission (I sent it via Submit-o-matic 7)

[Zhao Le]

Thanks, fpnc but I don't understand.

I sent it two days ago but I got WA.

And today you sent it got AC.

Am I make mistake, but Thank you indeed.

[fpnc]

I don't know either. You can see my submission got AC (and it was a copy-and-paste submission of your first code).

Anyway, please note down the full submission number when you find this kind of things as we can retrieve your submissions and try to find out what happens.

[Nick]

Your first submission is surely wrong because you swap the input numbers

Code: Select all

if (i>j)
      {
         long tmp=j;
         j=i;
         i=tmp;
      }
      

the output must have the same sequence as the input was... so you musn't swap them, but instead you can use other variables to store their values temporarily

While in your second code, you've done this by storing the actual value in the linked list, that's why the second got accepted

some other programmers use function with parameter, which does similarly the same idea

regards

[Nick]

Your first submission is surely wrong because you swap the input numbers

Code: Select all

if (i>j)
      {
         long tmp=j;
         j=i;
         i=tmp;
      }
      

the output must have the same sequence as the input was... so you musn't swap them, but instead you can use other variables to store their values temporarily

While in your second code, you've done this by storing the actual value in the linked list, that's why the second got accepted

some other programmers use function with parameter, which does similarly the same idea

regards

[daiwb]

Code: Select all

#include <iostream>

using namespace std;

int main(void){
	long i,j,m,temp,total,max;
	while(cin>>i>>j){
		cout<<i<<" "<<j<<" ";
		max=0;
		if(i>j){
			temp=i;
			i=j;
			j=temp;
		}
		for(m=i;m<=j;m++){
			temp=m;
			total=0;
			while(1){
				total++;
				if(temp%2==0) temp/=2;
				else temp=3*temp+1;
				if(temp==1){
					total++;
					break;
				}
			}
			if(total>max) max=total;
		}
		cout<<max<<endl;
	}
	return 0;
}
[\code]
I think it's the same,but I got WA.So why.

[daiwb]

I havd just changed my code,and got AC.I really made a mistake.

Code: Select all

#include <iostream>

using namespace std;

int main(void){
	long i,j,m,temp,total,max;
	while(cin>>i>>j){
		cout<<i<<" "<<j<<" ";
		max=0;
		if(i>j){
			temp=i;
			i=j;
			j=temp;
		}
		for(m=i;m<=j;m++){
			temp=m;
			total=0;
			while(1){
				if(temp==1){
					total++;
					break;
				}
				total++;
				if(temp%2==0) temp/=2;
				else temp=3*temp+1;	
			}
			if(total>max) max=total;
		}
		cout<<max<<endl;
	}
	return 0;
}