## 100 - The 3n + 1 problem

Moderator: Board moderators

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
You are making the most common mistake in problem 100. If you pay time and read other post about problem 100, you will know what is the mistake.
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

awik_10
New poster
Posts: 14
Joined: Sun May 18, 2003 11:56 am

### problem with 3n+1, always wrong answer

i'm still a newbie, can anybody tell what's my wrong

c
#include<stdio.h>
#include<stdlib.h>

int panjang(unsigned long a,unsigned long b)
{
int ctr=0,cycle=1,i;
unsigned long c,other_a,temp,x=1,y=1,k=1,l=1;
if(a>b)
{
c=a;
a=b;
b=c;
}
other_a=a;
while(other_a<=b)
{
ctr=1;
temp=other_a;
while(temp!=1)
{
ctr++;
/* if(temp%2==0)
{
if(x<temp) { x=temp; y=1; }
}
if(temp%2!=0)
{
if(k<temp) { k=temp; l=1; }
}
*/

if(temp%2!=0) { temp=temp*3+1; }
else{ temp=temp/2; }
if(temp==x&&temp!=1) { ctr=ctr+y-1; break; }
if(temp==k&&temp!=1) { ctr=ctr+l-1; break; }
}
cycle=cycle>=ctr?cycle:ctr;
if(ctr>y&&other_a%2==0)
{
x=other_a;
y=ctr;
}
if(ctr>l&&other_a%2!=0)
{
k=other_a;
l=ctr;
}
other_a++;
}
return cycle;
}

int main()
{
unsigned long a,b;
while(scanf("%lu%lu",&a,&b)==2)
{
if(a>0&&a<1000001&&b>0&&b<1000001)
printf("%lu %lu %d",a,b,panjang(a,b));
}
return 0;
}

it said that it ran during 4.189 seconds.

best regards,
awik

awik_10
New poster
Posts: 14
Joined: Sun May 18, 2003 11:56 am

### wrong answer at 3n+1 problem (100)

i'm sorry about the previous one. can you tell me waht's my wrong? and it said that it ran during 4.189 seconds . this is my code with some of my explanations.

i wait for your replies. thank you.
best regards,

awik
Last edited by awik_10 on Sun May 18, 2003 1:31 pm, edited 1 time in total.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

If you still can't see the problem, tell me.

P.S. I submitted a slightly modified version of your code and got ACC!!!!
Just a very minor mistake, really......
Last edited by Observer on Sun May 18, 2003 12:36 pm, edited 1 time in total.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

awik_10
New poster
Posts: 14
Joined: Sun May 18, 2003 11:56 am
i still don't get it .
can you give me more explanation. by the way, thank you

awik

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Well, sorry...... I'm not a C++ user...
(Can you use file input/output?)

Your problem comes from the layout of the output.
Don't you realize that there's something unnatural in your output format?

By adding just ONE line in your code, you can get an ACC!!!!

1 2
But not for this:
1 2
1 2
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

awik_10
New poster
Posts: 14
Joined: Sun May 18, 2003 11:56 am
thank you anyway for your suggestion. i've just submitted it and got an acc. it only minus "\n" .
awik

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Good for you! Glad that you find it out yourself!!!!!!!!!

7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

fpnc
Posts: 201
Joined: Sun Oct 07, 2001 2:00 am

### If you get WA in problem 100, read me before post!

Please, read carefully the statement; in particular, do not asume that i < j.

Best regards,

Fernando N

powerboy
New poster
Posts: 8
Joined: Mon May 12, 2003 6:13 am
Contact:

### problem 100

The input for problem 100 is a series of lines of numbers.
How do i know when the input ends?
In addition, should i print all the output after all the input or
input
output
input
output
etc...

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia
yes, like that. end at EOF.

Crystal Vision Coders
New poster
Posts: 1
Joined: Fri May 23, 2003 11:58 am
Location: UK
Contact:
Hi All,

I'm a newby to programming contests so be gentle with me. I have written what I think is a solution to problem 100. I submitted it and it got sent back with WA. Investigation suggested that for 113383 int was wrapping to -ve values so I changed to unsigned long but I still get WA. Now (on my PC) I can calculate answers for 1 to 1000000 in 2.5 sec and I use no arrays so the memory usage should be minimal. The examples that are given in the problem all give the correct answers and I have checked with the example code for the problem and can see no significant differences. Can anybody give me a hint as to where I am going wrong. (My code below).

Phil Mason

[c]
#include <stdio.h>

int main(void)
{
int start_val, stop_val, max_length, length;
int orig_start, orig_stop;
unsigned long temp, i;

while(scanf("%d %d\n",&start_val,&stop_val)==2)
{
max_length = 0;

/* Store Original order incase they get swapped */
orig_start = start_val;
orig_stop = stop_val;

/* Swap if needed */
if(start_val > stop_val)
{
stop_val = start_val;
start_val = orig_stop;
}

for(i=start_val; i<stop_val; i++)
{
/* reset the length */
length = 1;
/* Perform the initial calculation */
temp = i;
/* perform the loop */
while(temp != 1)
{
if(temp%2)
temp = (3*temp)+1;
else
temp = temp/2;
length++;
}
/* check that the length not longer than the max */
if(length > max_length)
max_length = length;
} /* End of the for loop */
printf("%d %d %d\n",orig_start, orig_stop, max_length);
}
return(1);
}

[/c]

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut
try this input

Code: Select all

``````1 1
5 5
10 10
``````
with love & light,

titid
Kalo mau kaya, buat apa sekolah?

Xeross
New poster
Posts: 2
Joined: Tue May 27, 2003 6:33 am

### 3n+1. Time Limit

I tried in brute force, so I get TL.

So I collected all of method about solution, constant and cache.

But I am get the message, TL, continouly -_-;;

What the hell is the problem in the source below?

------

#include <stdio.h>

#define MAXNUM 100000

int g_stack[MAXNUM] = {0,};

int main(int argc, char* argv[])
{
while( 1 )
{
long int nFrom, nTo;

while( 2 == scanf( "%ld %ld", &nFrom, &nTo ) )
{
int nMaxCount = 0;
long int n;

if (nFrom<=837799 && nTo>=837799)
{
printf("%ld %ld %d\n",nFrom,nTo,525);
continue;
}
if (nFrom<=626331 && nTo>=626331)
{
printf("%ld %ld %d\n",nFrom,nTo,509);
continue;
}
if (nTo<626331 && nFrom<=511935 && nTo>=511935)
{
printf("%ld %ld %d\n",nFrom,nTo,470);
continue;
}
if (nTo<511935 && nFrom<=410011 && nTo>=410011)
{
printf("%ld %ld %d\n",nFrom,nTo,449);
continue;
}
if (nTo<410011 && nFrom<=230631 && nTo>=230631)
{
printf("%ld %ld %d\n",nFrom,nTo,443);
continue;
}

for( n = nFrom ; n <= nTo ; n++ )
{
long int nValue = n;
int nCount = 0;

while( 1 )
{
nCount++;

if( 1 == nValue )
break;
else
{
if( nValue<MAXNUM && (g_stack[nValue] != 0) )
{
nCount += g_stack[nValue]-1;

break;
}
else
{
if( nValue & 1 )
nValue = nValue * 3 +1;
else
nValue >>= 1;
}
}
}

if( nMaxCount < nCount )
nMaxCount = nCount;

if( n<MAXNUM && (g_stack[n] == 0) )
g_stack[n] = nCount;
}

printf( "%ld %ld %ld\n", nFrom, nTo, nMaxCount );
}
}

return 0;
}

ayaw
New poster
Posts: 18
Joined: Fri May 23, 2003 3:52 pm
Contact:
Hope this'll help u

Code: Select all

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

#define MAXNUM 100000

int g_stack[MAXNUM] = {0,};

int main(int argc, char* argv[])
{
while( 1 )

/* <--- Forever loops!! I can't find "return" for this function or "break" for this loops */

{
long int nFrom, nTo;

while( 2 == scanf( "%ld %ld", &nFrom, &nTo ) )
{
int nMaxCount = 0;
long int n;

if (nFrom<=837799 && nTo>=837799)
{
printf("%ld %ld %d\n",nFrom,nTo,525);
continue;
}
if (nFrom<=626331 && nTo>=626331)
{
printf("%ld %ld %d\n",nFrom,nTo,509);
continue;
}
if (nTo<626331 && nFrom<=511935 && nTo>=511935)
{
printf("%ld %ld %d\n",nFrom,nTo,470);
continue;
}
if (nTo<511935 && nFrom<=410011 && nTo>=410011)
{
printf("%ld %ld %d\n",nFrom,nTo,449);
continue;
}
if (nTo<410011 && nFrom<=230631 && nTo>=230631)
{
printf("%ld %ld %d\n",nFrom,nTo,443);
continue;
}

for( n = nFrom ; n <= nTo ; n++ )
{
long int nValue = n;
int nCount = 0;

while( 1 )
{
nCount++;

if( 1 == nValue )
break;
else
{
if( nValue<MAXNUM && (g_stack[nValue] != 0) )
{
nCount += g_stack[nValue]-1;
break;
}
else
{
if( nValue & 1 )
nValue = nValue * 3 +1;
else
nValue >>= 1;
}
}
}

if( nMaxCount < nCount )
nMaxCount = nCount;

if( n<MAXNUM && (g_stack[n] == 0) )
g_stack[n] = nCount;
}

printf( "%ld %ld %ld\n", nFrom, nTo, nMaxCount );
}
}

return 0;
}
``````
peace...