100 - The 3n + 1 problem

[Ice-Eight]

Got it! Thanks for the help

[ausiva]

My code compiles fine in my gcc..but the judge throws up compiler error always...I have tried MANY times..This is teh code..Any help would be appreciated. Thanks

Code: Select all

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

//This function returns the 'cycle length' for n, as defined in the 3n+1 problem
unsigned long cycleLength(unsigned long n)
{
    int len = 1;
    while(n!=1)
    {
               if(n%2)
                   n=3*n + 1;
               else
                   n=n/2;
               ++len;
    }
    return len;
}

//This prints the maximum cycle length of numbers between i and j inclusive
void maxCycleLength(unsigned long i, unsigned long j)
{
    int swap_flag=0;
    unsigned long k;
    unsigned long len;
    unsigned long maxLen=0;
    if(i>j)
    {
           i=i^j;
           j=i^j;
           i=i^j;
           swap_flag=1;
    }
   
    for(k=i; k<=j; k++)
      if((len=cycleLength(k))>maxLen)
         maxLen = len;
                       
    if(swap_flag)               
       printf("%ld\t%ld\t%ld\n", j,i,maxLen);
    else
       printf("%ld\t%ld\t%ld\n", i,j,maxLen);
}

int main(void)
{
    unsigned long i;
    unsigned long j;
    while(scanf("%ld %ld",&i,&j)==2)
    {
        if(i<1 || j<1)
        {
               printf("\nInvalid Input");
               return 1;
        }
        maxCycleLength(i,j);
    }
    return 0;
}

[/code]

[ausiva]

The above code is for problem 100.

[sumankar]

My code compiles fine in my gcc..but the judge throws up compiler error always...

The judge's C compiler gets high on C++ comments.

I couldn't help but comment on a few other things in your code viz:

Code: Select all

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

//This function returns the 'cycle length' for n, as defined in the 3n+1 
problem
/* Use comments such as this one */
unsigned long cycleLength(unsigned long n)
{
    int len = 1;
    [...]
    return len;
/* types: declare len as an unsigned int */
}

//This prints the maximum cycle length of numbers between i and j inclusive
void maxCycleLength(unsigned long i, unsigned long j)
{
    int swap_flag=0;
    unsigned long k;
    unsigned long len;
    unsigned long maxLen=0;
    if(i>j)
    {
           i=i^j;
           j=i^j;
           i=i^j;
           /* you can get worse [oops, terse] :)
           i ^= j ^= i ^= j;
           */
  [...] 
 /* need %lu for unsigneds */                    
    if(swap_flag)               
       printf("%ld\t%ld\t%ld\n", j,i,maxLen);
  [...]
}

int main(void)
{
    unsigned long i;
    unsigned long j;
    while(scanf("%ld %ld",&i,&j)==2)
    /* need %lu for unsigneds */
    {
[...]
}

[AhlyM]

hi programmers.
i have two solutions for acm 3n+1 problem#100 one works and the other don't.
i have tested both of them they worked for me and give the same answer but acm accepted one an doesn't accept the other.

The Accepted Code:

Code: Select all

program p100 (input, output); 

var 
  i, j: integer; 

function getCL(N: integer): integer; 
var k: integer; 
begin 
  k := 1; 
  while N <> 1 do begin 
    if odd(N) then N := 3*N + 1 
    else N := N div 2; 
    k := k + 1; 
  end; 
  getCL := k; 
end; 

function getMaxCL(i, j: integer): integer; 
var k: integer; 
  max, curCL: integer; 
begin 
  max := 0; 
  for k:=i to j do begin 
    curCL := getCL(k); 
    if curCL > max then max := curCL; 
  end; 
  getMaxCL := max; 
end; 

begin 
  while not eof(input) do begin 
    readln(i, j); 
    write(i, ' ', j, ' '); 
    if i < j then 
      writeln(getMaxCL(i, j)) 
    else 
      writeln(getMaxCL(j, i)); 
  end; 
end.

The Wrong Answer Code:

Code: Select all

program p100 (input, output); 
var 
   n,i,c,j,f,z:integer; 
begin 
     while not eof(input) do 
     begin 
     readln(i, j); 
     write(i, ' ', j,' '); 
     z:=0; 
     if j>i then 
     begin 
          for f:=i to j do 
          begin 
               c:=1; 
               n:=f; 
               while n<>1 do 
               begin 
                    if odd(n) then n:=(3*n)+1 else n:=(n div 2); 
                    c:=c+1; 
                    if c>z then z:=c; 
               end; 
          end; 
     end 
     else 
     begin 
          for f:=j to i do 
          begin 
               c:=1; 
               n:=f; 
               while n<>1 do 
               begin 
                    if odd(n) then n:=(3*n)+1 else n:=(n div 2); 
                    c:=c+1; 
                    if c>z then z:=c; 
               end; 
          end; 
     end; 
     writeln(z); 
     end; 
end.

Can any one figure out the problem because i'm going mad ?

Thanks.

[AhlyM]

hi programmers.
i have two solutions for acm 3n+1 problem#100 one works and the other don't.
i have tested both of them they worked for me and give the same answer but acm accepted one an doesn't accept the other.

The Accepted Code:

Code: Select all

program p100 (input, output); 

var 
  i, j: integer; 

function getCL(N: integer): integer; 
var k: integer; 
begin 
  k := 1; 
  while N <> 1 do begin 
    if odd(N) then N := 3*N + 1 
    else N := N div 2; 
    k := k + 1; 
  end; 
  getCL := k; 
end; 

function getMaxCL(i, j: integer): integer; 
var k: integer; 
  max, curCL: integer; 
begin 
  max := 0; 
  for k:=i to j do begin 
    curCL := getCL(k); 
    if curCL > max then max := curCL; 
  end; 
  getMaxCL := max; 
end; 

begin 
  while not eof(input) do begin 
    readln(i, j); 
    write(i, ' ', j, ' '); 
    if i < j then 
      writeln(getMaxCL(i, j)) 
    else 
      writeln(getMaxCL(j, i)); 
  end; 
end.

The Wrong Answer Code:

Code: Select all

program p100 (input, output); 
var 
   n,i,c,j,f,z:integer; 
begin 
     while not eof(input) do 
     begin 
     readln(i, j); 
     write(i, ' ', j,' '); 
     z:=0; 
     if j>i then 
     begin 
          for f:=i to j do 
          begin 
               c:=1; 
               n:=f; 
               while n<>1 do 
               begin 
                    if odd(n) then n:=(3*n)+1 else n:=(n div 2); 
                    c:=c+1; 
                    if c>z then z:=c; 
               end; 
          end; 
     end 
     else 
     begin 
          for f:=j to i do 
          begin 
               c:=1; 
               n:=f; 
               while n<>1 do 
               begin 
                    if odd(n) then n:=(3*n)+1 else n:=(n div 2); 
                    c:=c+1; 
                    if c>z then z:=c; 
               end; 
          end; 
     end; 
     writeln(z); 
     end; 
end.

Can any one figure out the problem because i'm going mad ?

Thanks.

[Artikali]

you should check
input
1 1
wrong output
1 1 0
correct one
1 1 1

.

[Artikali]

Code: Select all

         while n<>1 do 
               begin 
                    if odd(n) then n:=(3*n)+1 else n:=(n div 2); 
                    c:=c+1; 
                    if c>z then z:=c; 
               end;

Code: Select all

 
             while n<>1 do 
               begin 
                    if odd(n) then n:=(3*n)+1 else n:=(n div 2); 
                    c:=c+1; 
               end;      
              if c>z then z:=c; 

[/code]

[gapsonhk]

Code: Select all

program p100;
var n,i,j,k:longint;
    c,max:integer;
begin
   while not(eof())do begin
       max:=0;
       readln(i,j);
       write(i,' ',j,' ');
       if i>j then begin
           k:=i;
           i:=j;
           j:=k;
       end;
       for k:=i to j do begin
          n:=k;
          c:=0;
          if n=1 then
            c:=0
          else begin
             repeat
                   if n mod 2=0 then
                      n:=n div 2
                   else
                       n:=3*n+1;
                   c:=c+1;
             until n=1;
          end;
          if c>=max then
             max:=c+1;
       end;
       writeln(max);
   end;
end.

i have handed in 20times but still error
>can anyone tell me where i am wrong?
thx

[Hackson]

Read this post
http://online-judge.uva.es/board/viewtopic.php?t=3015

[gapsonhk]

sorry
still don't know why,where is the bug

[fpavetic]

in input, i can be greater than j so you must think of that case...
and in the output you must print how you read it

for example.

input
2 1

output
2 1 max_solution

[gapsonhk]

still error

[fpavetic]

check this
1 1

output should be 1, but your program outputs 2

[gapsonhk]

Time Limit Exceeded