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

Post by r.z. »

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:

Post by 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
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?

Post by 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
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by 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
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

Post by 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
Learning poster
Posts: 80
Joined: Mon May 05, 2003 4:09 am
Location: Shanghai,China

Post by 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
Learning poster
Posts: 80
Joined: Mon May 05, 2003 4:09 am
Location: Shanghai,China

Post by 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
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia

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

Post by 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)
Best regards,

Fernando N

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

Thanks.

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

Post by 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.
Best regards,

Fernando N

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

To Zhao Le

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

To Zhao Le

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

Post by 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.
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:

Post by 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;
}
There Can Be Miracles When You Believe

Post Reply

Return to “Volume 1 (100-199)”