## 100 - The 3n + 1 problem

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

r.z.
Learning poster
Posts: 56
Joined: Thu Jun 05, 2003 1:57 pm
Yes I've found the bug yesterday and finally got accepted

why I keep doing mistakes like this.... Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
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
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)
Zhao Le
Learning poster
Posts: 80
Joined: Mon May 05, 2003 4:09 am
Location: Shanghai,China

### How could you explain this?

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
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
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
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)
fibonacci
New poster
Posts: 2
Joined: Thu Jun 12, 2003 2:30 pm

### 100 WA

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
Learning poster
Posts: 80
Joined: Mon May 05, 2003 4:09 am
Location: Shanghai,China
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
Learning poster
Posts: 80
Joined: Mon May 05, 2003 4:09 am
Location: Shanghai,China
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
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia
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
System administrator
Posts: 201
Joined: Sun Oct 07, 2001 2:00 am
Location: Valladolid, Spain
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)
Best regards,

Fernando N
Zhao Le
Learning poster
Posts: 80
Joined: Mon May 05, 2003 4:09 am
Location: Shanghai,China

### Thanks.

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
System administrator
Posts: 201
Joined: Sun Oct 07, 2001 2:00 am
Location: Valladolid, Spain
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.
Best regards,

Fernando N
Nick
Learning poster
Posts: 53
Joined: Sun Jan 12, 2003 4:49 am

### To Zhao Le

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
Learning poster
Posts: 53
Joined: Sun Jan 12, 2003 4:49 am

### To Zhao Le

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
New poster
Posts: 3
Joined: Mon Jun 02, 2003 4:14 am
Location: Zhejiang University CS
Contact:

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.``````
There Can Be Miracles When You Believe
daiwb
New poster
Posts: 3
Joined: Mon Jun 02, 2003 4:14 am
Location: Zhejiang University CS
Contact:
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;
}
``````
There Can Be Miracles When You Believe