100 - The 3n + 1 problem

[DarkX2]

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]

Just try the statefull's test cases above there..

[DarkX2]

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]

Ah.. I think it should be

Code: Select all

for (int t=hi; t <= hj; t=t+1)

and "int" is enough..

[DarkX2]

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]

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);
   }
}

[NottaBenna]

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]

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]

What do you mean restricted functin.
I submitted your code and got WA.

[HyperWireD]

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]

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]

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]

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);
read(n[i],k[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;
readln;
end.

[helloneo]

Try Rocky's test cases right up there..

[gates1]

rocky's test cases work on my program