## 100 - The 3n + 1 problem

Moderator: Board moderators

yogeshgo05
New poster
Posts: 47
Joined: Sun Nov 27, 2005 12:43 pm

### 3N+1

hey guys this is code , acm judge says TLE ,
some body tell me whats wrong , i m a begginer

# include <stdio.h>

int main()
{
int i,j,c=1;
int m,n,k=0,r;
printf("enter the value of i &j");
while(scanf("%d %d",&i,&j)!=EOF)
{
m=i,n=j;
r=i;
while(r!=j)
{ i=r;
c=1;
while(i!=1)
{

if((i%2)!=0)
{
i=3*i+1;

}
else
{
i=i/2;

}

c++;
}
if(k<c)k=c;
r++;

}
printf("%d %d %d ",m,n,k);

}
return 0;
}

Timo
Learning poster
Posts: 70
Joined: Tue Oct 11, 2005 2:44 am
Location: Indonesia
Hi yogeshgo05,

you must to set the value of k to zero when read a new input.

your code is TLE because the first input can be greater than the second input.
your code didn't handle that case so it loop forever.

I have fixed your code and send it to judge and get AC.

Code: Select all

``````#include <stdio.h>

void swap(int *a, int *b)
{
int c;
c=*a;
*a=*b;
*b=c;
}

int main()
{

int i,j,c=1;
int m,n,k=0,r;

while(scanf("%d %d",&i,&j)!=EOF)
{
m=i,n=j;
if(i>j) swap(&i,&j);
r=i;

k=0;
while(r!=j+1)
{
i=r;
c=1;
while(i!=1)
{
if((i%2)!=0)
{
i=3*i+1;
}
else
{
i=i/2;
}
c++;
}
if(k<c)k=c;
r++;
}
printf("%d %d %d\n",m,n,k);

}
return 0;
}``````
"Life is more beautiful with algorithm"

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm

### Re: 3N+1

yogeshgo05 wrote: printf("enter the value of i &j");
please dont print anything unwanted, otherwise u'll get wrong answer. and post topic at the right place. this topics might be posted at volume I, with the subject including both problem number and problem name, moreover better use code tag, so that your code will be easily readable(as Timo did), have a nice day ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

Dewr
New poster
Posts: 6
Joined: Sun Dec 04, 2005 4:08 pm

### update

i updated my program! i want speed!
judge server said me "RUNTIME ERROR!" Code: Select all

``````#include <stdio.h>
#include <memory.h>
#ifndef ONLINE_JUDGE
#include <time.h>
clock_t start, finish;
#endif

unsigned int inputi;
unsigned int inputj;
unsigned int cycle;
unsigned int nownumber;
unsigned int maxcycle;
unsigned int thenumber;
unsigned int dummy;
unsigned int boolsw = 0;
unsigned int * data;

void checkitup();
unsigned int checkit();

int main()
{
data = new unsigned int;
memset(data, 0, 4000000);
lalala:
maxcycle = 1;

if(scanf("%u %u", &inputi, &inputj)==EOF)
{
delete[] data;
return 0;
}

#ifndef ONLINE_JUDGE
if(inputi<1 || inputi >999999 || inputj<1 || inputj >999999)
{
printf("min = 1      max = 999999\n");
goto lalala;
}
#endif

#ifndef ONLINE_JUDGE
start =clock();
#endif
if(inputi > inputj)
{
boolsw^=1;
inputi^=inputj;
inputj^=inputi;
inputi^=inputj;
}
nownumber = inputi;
checkitup();

do{
nownumber++;
if(checkit())
continue;
checkitup();
}while(nownumber!=inputj);
#ifndef ONLINE_JUDGE
finish = clock();
printf("it takes %f seconds.\n", (double)(finish-start)/(double)CLK_TCK);
#endif

if(boolsw)
{
boolsw^=1;
inputi^=inputj;
inputj^=inputi;
inputi^=inputj;
}
printf("%u %u %u\n", inputi, inputj, maxcycle);
goto lalala;
}

void checkitup()
{
if(data[nownumber])
{
if(maxcycle<data[nownumber])
maxcycle = data[nownumber];
return;
}
thenumber = nownumber;
cycle = 0;
while(1)
{
cycle++;
if(thenumber == 1)
break;
else if(thenumber&1)
{
thenumber += (thenumber << 1);
thenumber++;
}
else
{
dummy = thenumber>>1;
if(dummy < 1000000 && data[dummy])
{
cycle += data[dummy];
break;
}
thenumber>>=1;
}
}
data[nownumber] = cycle;
if(maxcycle < cycle)
maxcycle = cycle;
}

unsigned int checkit()
{
dummy = nownumber<<1;
if(dummy<=inputj)
return 1;
else
return 0;
}
``````

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Contact:

### Re: update

Dewr wrote:i updated my program! i want speed!
judge server said me "RUNTIME ERROR!" Where did you update your program? Runtime error doesn't mean your program is running slow. You'll get Time limit exceeded for that.

=viki=
New poster
Posts: 23
Joined: Mon Jan 02, 2006 6:23 pm
Contact:
check out my prog its in C....im getting compile error prob 100

Code: Select all

``````#include<stdio.h>

long max=0;
void process(long,long);

int main(void)
{
long x,y;
scanf("%d%d",&x,&y);
process(x,y);
printf("%ld  %ld  %ld\n",x,y,max);
return 0;
}

void process(long x, long y)
{long i,count=0,n;
for(i=x;i<y;i++)
{
n=i;
while(1)
{
count++;
if(max<count)
max=count;
if(n==1)
{
count=0;
break;
}

if((n%2)==0)
n=n/2;

else
n=(3*n)+1;

}
}
}
``````
using dev c++ for compilation...
its compiled on my system
whats the problem here?

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Contact:
Are you sure you're getting compile error?

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore
I have been getting weird compile errors for C code myself for problem 142 which I wrote around one year ago and resubmitted as C code after some corrections and got compile error. The original code had compiled ok in the OJ when I submitted one year ago as C code as well. I had to submit my C code as C++ code to make it compile. I was not able to find out why my C code had compile error when I resubmitted because the e-mail address in my user profile for the OJ is gone and I could not edit my profile to enable it back.

From viki's code for problem 100, I think it might be because of this:

Code: Select all

``long i,count=0,n;``
Rewriting this as:

Code: Select all

``````long i,count,n;
count = 0;
``````
might help.

Also your code will get WA from the judge even if you managed to get the judge to compile your code successfully.

There was something similar in my problem 142 code as well which could have caused the compile error in the OJ although it compiled fine with a gcc 2.95 compiler I have. Your code compiles fine with the gcc 2.95 compiler I have.

Also, you could enable the option in your profile to receive compile error messages via e-mail.

tobby
Learning poster
Posts: 98
Joined: Fri Dec 30, 2005 3:31 pm
chunyi81 wrote:Also, you could enable the option in your profile to receive compile error messages via e-mail.
I don't think you can do that now, because the update info feature is not working.

=viki=
New poster
Posts: 23
Joined: Mon Jan 02, 2006 6:23 pm
Contact:

### 100 WA(getting output on m sstem though)

here goes the code

Code: Select all

``````#include<stdio.h>

long max=0;
void process(long,long);

int main(void)
{
long x,y;
scanf("%ld%ld",&x,&y);
process(x,y);
printf("%ld  %ld  %ld\n",x,y,max);
max=0;
return 0;
}

void process(long x, long y)
{long i,count=0,n;
for(i=x;i<y;i++)
{
n=i;
while(1)
{
count++;
if(max<count)
max=count;
if(n==1)
{
count=0;
break;
}

if((n%2)==0)
n=n/2;

else
n=(3*n)+1;

}
}
}
``````

im getting WA .. plz point out the problem here ..
this is m first ACM problem..
tried the while loop variation for taking input also
while(scanf("%d%d",&x,&)==2)
what shall i do plz help its working on m sstem for all inputs
plz help

=viki=
New poster
Posts: 23
Joined: Mon Jan 02, 2006 6:23 pm
Contact:

Code: Select all

``````#include<stdio.h>

long max=0;
void process(long,long);

int main(void)
{
long x,y;
scanf("%ld%ld",&x,&y);
process(x,y);
printf("%ld  %ld  %ld\n",x,y,max);
max=0;
return 0;
}

void process(long x, long y)
{long i,count=0,n;
for(i=x;i<y;i++)
{
n=i;
while(1)
{
count++;
if(max<count)
max=count;
if(n==1)
{
count=0;
break;
}

if((n%2)==0)
n=n/2;

else
n=(3*n)+1;

}
}
}
``````
plz help now im getting WA whats wrong here plz point out

this is my first ACM problem
so if some thing is wrong in taking input plz point out...

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain
The input haven't only a case.
You must check if x is greater than y or not.
By other hand, you must reuse another post that talk about the same problem, also there are a lot of post about this problem that you can have a look and I'm almost sure that they will resolve your doubts and mistakes.
Good luck! =viki=
New poster
Posts: 23
Joined: Mon Jan 02, 2006 6:23 pm
Contact:

Code: Select all

``````#include<stdio.h>

long max=0;
void process(long,long);

int main(void)
{
long x,y;
scanf("%ld%ld",&x,&y);
process(x,y);
printf("%ld  %ld  %ld\n",x,y,max);
max=0;
return 0;
}

void process(long x, long y)
{long i,count=0,n;
for(i=x;i<y;i++)
{
n=i;
while(1)
{
count++;
if(max<count)
max=count;
if(n==1)
{
count=0;
break;
}

if((n%2)==0)
n=n/2;

else
n=(3*n)+1;

}
}
}
``````

plz sm1 compile n run this code on ur system n tell me whats wrong gettin WA... but its running on my system (using dev c++)...
this is my first ACM problem ..heavent submitted any prob before
tried to submit it more than 10 times .. initially it was CE now im getting WA plz help

=viki=
New poster
Posts: 23
Joined: Mon Jan 02, 2006 6:23 pm
Contact:
e i tried....

Code: Select all

``````#include<stdio.h>

long max=0;
void process(long,long);

int main(void)
{
long x,y;
while(scanf("%ld%ld",&x,&y)==2) {
process(x,y);
printf("%ld  %ld  %ld\n",x,y,max);
max=0;
}
return 0;
}

void process(long x, long y)
{long i,count=0,n;
for(i=x;i<y;i++)
{
n=i;
while(1)
{
count++;
if(max<count)
max=count;
if(n==1)
{
count=0;
break;
}

if((n%2)==0)
n=n/2;

else
n=(3*n)+1;

}
}
}
``````
plz tell me whats the prob..
after while(scanf("%d%d",&x,&)==2) the loop never terminates

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am
=viki= wrote:plz sm1 compile n run this code on ur system n tell me whats wrong gettin WA... but its running on my system (using dev c++)...
this is my first ACM problem ..heavent submitted any prob before
tried to submit it more than 10 times .. initially it was CE now im getting WA plz help