## 100 - The 3n + 1 problem

Moderator: Board moderators

DarkX2
New poster
Posts: 3
Joined: Wed Feb 28, 2007 9:27 am
Well,

I'm trying to figure out, why this is always giving me a WA:

Code: Select all

``````#include <iostream>

using namespace std;

int main()
{
long i, j, n;
while (cin  >> i >> j)
{
long hi, hj;
long max = 0;
if (i > j)
{
hi = j;
hj = i;
}
else
{
hi = i;
hj = j;
}
cout << i << " " << j << " ";

for (int t=hi;t<hj;t=t+1)
{
long c = 1;
n = t;

while (n != 1)
{
if ( (n % 2) != 0)
{
n = (3 * n) + 1;
}
else
{
(n = n / 2);
}

c = c + 1;

if (c > max)
{
max = c;
}

}

}

cout << max << endl;
}
}
``````

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
Just try the statefull's test cases above there..

DarkX2
New poster
Posts: 3
Joined: Wed Feb 28, 2007 9:27 am
With this new code, I receive the same anwsers as statefull's had tested before -with the exception of the 787843 case, that seems not to finish...

Code: Select all

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

using namespace std;

int main()
{
unsigned long int i, j, n;
while (scanf("%ld %ld",&i,&j)==2)
{
unsigned long int hi, hj;
unsigned long int  max = 0;
if (i > j)
{
hi = j;
hj = i;
}
else
{
hi = i;
hj = j;
}
printf("%ld %ld ",i,j);

for (int t=hi;t<hj;t=t+1)
{
unsigned long int c = 1;
n = t;

do
{
if (n == 1)
{
max = max +1;
}
else
{
if ( (n % 2) != 0)
{
n = (3 * n) + 1;
}
else
{
(n = n / 2);
}

c = c + 1;

if (c > max)
{
max = max+1;
}
}

}
while (n != 1);

}

printf("%ld\n",max);
}
}``````
I still get wrong answer. I don't realize doing anything totally different from newtons version posted above that gets Accepted.

Any ideas what's up?

EDIT:

Arrghh, I got it. Long is too small, I thought that Long > Int, but I was wrong...

EDIT2:

Still getting WA...
Is Statefulls Answer for 787843 right? I'm getting 470 as solution...

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
Ah.. I think it should be

Code: Select all

``for (int t=hi; t <= hj; t=t+1)``
and "int" is enough..

DarkX2
New poster
Posts: 3
Joined: Wed Feb 28, 2007 9:27 am
Well,

I tried it, but it didn't change anything.

Working just with Int does not work, at least not with Visual Studio 6

animeshnayan
New poster
Posts: 5
Joined: Tue Mar 20, 2007 7:44 am
DarkX2 wrote:With this new code, I receive the same anwsers as statefull's had tested before -with the exception of the 787843 case, that seems not to finish...

Code: Select all

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

using namespace std;

int main()
{
unsigned long int i, j, n;
while (scanf("%ld %ld",&i,&j)==2)
{
unsigned long int hi, hj;
unsigned long int  max = 0;
if (i > j)
{
hi = j;
hj = i;
}
else
{
hi = i;
hj = j;
}
printf("%ld %ld ",i,j);

for (int t=hi;t<hj;t=t+1)
{
unsigned long int c = 1;
n = t;

do
{
if (n == 1)
{
max = max +1;
}
else
{
if ( (n % 2) != 0)
{
n = (3 * n) + 1;
}
else
{
(n = n / 2);
}

c = c + 1;

if (c > max)
{
max = max+1;
}
}

}
while (n != 1);

}

printf("%ld\n",max);
}
}``````
I still get wrong answer. I don't realize doing anything totally different from newtons version posted above that gets Accepted.

Any ideas what's up?

EDIT:

Arrghh, I got it. Long is too small, I thought that Long > Int, but I was wrong...

EDIT2:

Still getting WA...
Is Statefulls Answer for 787843 right? I'm getting 470 as solution...
check out for this part .... first of all (t<=hj) is desired .... n then max is not bein choosen correctly..i have modified it and get AC

Code: Select all

``````#include <stdio.h>
#include<iostream>
using namespace std;
int main()
{
long i, j, n;
while (scanf("%ld %ld",&i,&j)==2)
{
long  hi, hj;
long  max = 0;
if (i > j)
{
hi = j;
hj = i;
}
else
{
hi = i;
hj = j;
}
printf("%ld %ld ",i,j);

for (long t=hi;t<=hj;t=t+1)
{
long  c = 0;
n = t;

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

}
else
{
n = n / 2;

}
c++;
}
// cout<<c<<endl;
if (c +1> max)
{
max=c+1;
}

}

printf("%ld\n",max);
}
}
``````
I am striving to write bug free codes (

NottaBenna
New poster
Posts: 1
Joined: Mon Mar 26, 2007 10:07 pm
I'm completely new to programming... I tried the first problem, but I'm still getting WA (I tried it some 20 times now...)

Can someone help me?

Here is my code:
#include <stdio.h>

int main (void)
{
unsigned int num1, num2, i, j, cycle_length, max_cycle;
scanf ("%ld %ld", & num1, & num2);
max_cycle = 1;

if ((num1 < num2) && (num2 < 1000000))
{
for (i = num1; i <= num2; i ++)
{
cycle_length = 1;
j = i;
while (j > 1)
{
if ((j % 2) == 0)
j = j / 2;
else
j = (3 * j) + 1;
cycle_length ++;
}
if (cycle_length > max_cycle)
max_cycle = cycle_length;
}
}

else if ((num1 > num2) && (num1 < 1000000))
{
for (i = num2; i <= num1; i ++)
{
cycle_length = 1;
j = i;
while (j > 1)
{
if ((j % 2) == 0)
j = j / 2;
else
j = (3 * j) + 1;
cycle_length ++;
}
if (cycle_length > max_cycle)
max_cycle = cycle_length;
}
}

printf ("%ld %ld %ld\n", num1, num2, max_cycle);
return (0);
}

intek
New poster
Posts: 1
Joined: Sat Apr 14, 2007 8:24 am

### 100: restricted function (i'm new *SNIFF)

Code: Select all

``````// http://acm.uva.es/p/v1/100.html

#include <iostream>
using namespace std;

int algorithm(int x)
{
int temp=x;
int count=0;

algorithm:
if(temp!=1)
{
// ODD***************************
if(temp%2) {
temp = (3*temp)+1;
count++;
goto algorithm;
}

// EVEN***************************
if(!(temp%2)) {
temp = temp/2;
count++;
goto algorithm;
}
}
else {
count++;
return count;
}
}

int MCL;
int main()
{
int temp;
for(; temp<1000000;){
int VALone=0, VALtwo=0;
MCL=0;

// Check input > 0
do {
cin >> temp; if(temp>0) VALone = temp;
cin >> temp; if(temp>0) VALtwo = temp;
} while(temp>1000000);

// Final check > 0                              -> algorithm(VALone, VALtwo)
if(VALone && VALtwo > 0) {
int temp;
if(VALone>VALtwo) {                  // sort values in numeric order
temp = VALone;
VALone = VALtwo;
VALtwo = temp;
}
for(int i=VALone; i<=VALtwo; i++) {
int FUNC= algorithm(i);
if(FUNC>MCL) MCL = FUNC;
}
cout << VALone << " " << VALtwo << " " << MCL << '\n';
}
}
return 0;
}``````

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
What do you mean restricted functin.
I submitted your code and got WA.

HyperWireD
New poster
Posts: 1
Joined: Thu Apr 26, 2007 5:37 pm
NottaBenna wrote:I'm completely new to programming... I tried the first problem, but I'm still getting WA (I tried it some 20 times now...)

Can someone help me?

Here is my code:
...unsigned int num1, num2, i, j, cycle_length, max_cycle;...
you are using ints. Here is some info about how big a number your primitive types hold:

INT_MAX is 32767
UINT_MAX is 65535 (unsigned)

but specifications say i and j could be up to 1000000 (1 million)

LONG_MAX is 2147483647
ULONG_MAX is 4294967295

Try using long or unsigned long.

roshanlen
New poster
Posts: 1
Joined: Fri Apr 27, 2007 10:46 pm

### problem# 100, gets WA, but don't know why

hi all,

my code for problem #100 is as follows, i am getting a WRONG ANSWER error. But I cannot figure out why.

Code: Select all

``````#include<iostream>
using namespace std;
#define SIZE 1000000
int cyc_length[SIZE];
inline int calc_length(int n )
{
int a,l,s;
if ( n == 1 ) return 1;
if ( cyc_length[n] == -1  ) return cyc_length[n];
s = n;
l = 0;
while ( n != 1 )
{
l++;
a = n%2 ? n*3 +1 : n/2;
if ( a < SIZE )
{
if ( cyc_length[a] > 0 )
{
l = l + cyc_length[a] - 1;
break;
}
cyc_length[a] = -1;
}

n = a;
}
cyc_length[s] = ++l;
return l;
}
int main(int argc, char* argv[])
{
int first, second, temp, current,max_length, length;
for (int i = 0 ; i < SIZE ; )
{
cyc_length[i++] = 0;
cyc_length[i++] = 0;
cyc_length[i++] = 0;
cyc_length[i++] = 0;
}
while (cin>>first>>second)
{
/* printf("%d %d ",first,second); */
cout <<first<<" "<<second<<" ";
if ( first > second )
{
temp = first;
first = second;
second = temp;
}
current = first;
max_length = 1;
while ( current < second )
{
length = calc_length(current);
if ( length > max_length )
max_length = length;
current++;
};
/*printf("%d\n",max_length);*/
cout<<max_length<<endl;
}
return 0;
}
``````

Rocky
Experienced poster
Posts: 124
Joined: Thu Oct 14, 2004 9:05 am
Contact:
To roshanlen:

May u done some worng...
check it....

input

Code: Select all

``````20 20
9999 9999
1 9999
340 3000
3000 340
500 101
1 1
9999 9998
``````
output

Code: Select all

``````20 20 8
9999 9999 92
1 9999 262
340 3000 217
3000 340 217
500 101 144
1 1 1
9999 9998 92
``````
GOOD LUCK
Rocky

gates1
New poster
Posts: 7
Joined: Tue May 01, 2007 2:11 pm
can anybody help me

i always get wa, here is my code:

Code: Select all

``````var n,k:array[1..100000] of longint;
i,j,max,p,k1,f:longint;
function nn(a:longint):integer;
begin
p:=0;
while a<>1 do begin
if a mod 2=0 then a:=a div 2 else a:=(3*a)+1;
inc(p);
end;
nn:=p;
end;
begin
i:=0;
repeat
inc(i);
until eof;
k1:=i;
for i:=1 to k1 do begin
max:=0;
if k[i]<n[i] then begin
f:=k[i];
k[i]:=n[i];
n[i]:=f;
end;   if n[i]>0 then begin
for j:=n[i] to k[i] do
if nn(j)>max then max:=nn(j);
writeln(n[i],' ',k[i],' ',max+1);
end;
end;
end.

``````

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
Try Rocky's test cases right up there..

gates1
New poster
Posts: 7
Joined: Tue May 01, 2007 2:11 pm
rocky's test cases work on my program