100 - The 3n + 1 problem

[shamim]

printf(" %d\n",maxlength);
}

I think there should be an extra closing bracket. that is

printf(" %d\n",maxlength);
}
}

[Maarten]

why don't you try to compile and run your program on your own computer before sending it to the judge ? I'm sure your compiler would have spotted the last mistake

[Morning]

it's a mistake;my code is

Code: Select all

#include<stdio.h> 
void main() 
{ 
   long i,bi,min,max,temp; 
   int length,maxlength; 
   while(1) 
   { 
       
      printf("%ld %ld",min,max); 
      maxlength=1; 
       
      if(max<min) 
      { 
         temp=max; 
         max=min; 
         min=temp; 
      } 
       
      for(i=max;i>=min;i--) 
      { 
         length=1; 
         bi=i; 
          
         while(i!=1) 
         { 
             
            if(i%2==1) 
            { 
               length+=1; 
               i=i*3+1; 
            } 
            if(i%2==0) 
            { 
               length+=1; 
               i=i/2; 
            } 
         } 
          
         if(length>maxlength) 
            maxlength=length; 
         i=bi; 
      } 
       
      printf(" %d\n",maxlength); 
   }
}

i can compile it correctly in VC,turbo c++,but after i send it to the judge@acm.uva,it said compile error,and it always happen.

[Maarten]

what compiler message do you get ?

[Morning]

I found if i send my code to the judge@uva.es,it will always said "parse error befor char 0317",but if i use the online judge system in the uva,there will be no compile error.

[hedgehog1204]

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

int circleLength(int n)
{
int cl=1;

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


main()
{
int i, j;
int cl;

while(scanf("%d %d", &i, &j) != EOF)
{
int max = 1;
printf("%d %d ", i, j);

if (i>j) {int temp=i; i=j; j=temp;};
for (int k=i; k<=j; k++)
{
cl = circleLength(k);
if (cl > max) max=cl;
}
printf("%d\n", max);
}
}
[/cpp]
It runs 3 sec. Do you know how to reduce the running time? I noticed there are some solutions with 00:02 seconds
Any other improvements you can suggest?

[Maarten]

00.02 sounds improbable to me too; i think those people just sent a precalculated table.
However, you can speed up your program significantly using memorization, thus not calculating the same cycle length twice.
For example, if you have already calculated the cycle length for 10:
(10 5 16 8 4 2 1, length = 7), and you try to calculate the cycle length for, say, 7 (7,22,11,34,17,52,26,13,40,20,10, ... ) you notice that at the moment you arrive at the "10" you can simply read off the cycle length from your table, thus obtaining a cycle length of 10 + length(10) = 17.

[Krishkinn]

My program has not solved the problem. It ran during 0.549 seconds.
WHY?

Code: Select all

{ @JUDGE_ID:   37494NH   100   Pascal   "The 3n + 1 problem" }
const
  maxx=1000000;
var
  i,j:longint;
  n,k,max:longint;
  l:extended;
  was:array[1..maxx]of longint;
Procedure proces;
begin
  max:=0;
  for i:=n to k do
  begin
    l:=i;
    j:=0;
    while l<>1 do
    begin
      if (l<=maxx)and(was[trunc(l)]<>0) then
      begin
        j:=j+was[trunc(l)];
        break;
      end;
      if l/2=trunc(l/2) then l:=l/2 else l:=l*3+1;
      inc(j);
    end;
    was[i]:=j;
    j:=j+1;
    if j>max then max:=j;
  end;
  writeln(max);
end;
begin

  while not eof do
  begin
    read(n,k);
    write(n,' ',k,' ');
    if n>k then
    begin
      j:=k;
      k:=n;
      n:=j;
    end;
    if n=0 then exit;
    proces;
  end;

end.

[linolium]

Well, 100 works fine on my computer, compiles no problemo. Not so on the judges'.

Here are the compiler error messages:

Code: Select all

01966610_24.c: In function `get_cycle_length':
01966610_24.c:9: parse error before `/'
01966610_24.c:11: parse error before `/'

Here is the code:

Code: Select all

/*   @JUDGE_ID:   37633FY   100   C   */
#include <stdio.h>

int get_cycle_length(int n)
{
        int cycle_length = 1;
        while (n != 1)
        {
                if (n % 2 == 0) {       // number is even
                        n = n / 2;
                } else {                        // number is odd
                        n = (n * 3) + 1;
                }
                cycle_length++;
        }
        return cycle_length;
}

int get_max_cycle_length(int i, int j) {
        int max_cycle_length    = 0;
        int cycle_length                = 0;
        int index                               = 0;
        int max                                 = 0;

        if (i > j) {
                max = i;
                i = j;
                j = max;
        }

        for (index = i; index <= j; index++) {
                cycle_length = get_cycle_length(index);
                if (cycle_length > max_cycle_length) {
                        max_cycle_length = cycle_length;
                }
        }
        return max_cycle_length;
}

int main() {
        int i = 0;
        int j = 0;
        while (scanf("%d %d", &i, &j)) {
                printf("%d %d %d\n", i, j, get_max_cycle_length(i, j));
        }
        return 0;
}

[linolium]

I tried changing my two comments to /* this style */, and it compiles. But it takes over 10 secs to execute?! and sends me a too long error. What is going on.. and I should be able to use //these comments too anyway, right?

[Larry]

Not in ANSI C. If you use gcc, use the -ansi flag and it'll tell you that. Only in C++ is that allowed.

[Larry]

Ya, for help on this problem, go to the related thread.. there are many many threads on 100...

[kuasha]

In ANSI C for comments // is not allowed. We must use /* comment */. I did never find any situation where a C++ compiler failed to compile a C program. Then why using C is necessary? (may be I don't know teh reason). And again there is one more thing... Mail programs often breaks lines when it bocomes long depending on its settings. Comments are written after some code in a line and there is a great chance to be broken. so using /* --- */ is safe. I don't know how submit-o-matic works with broken lines.

[zack]

I don't know what is wrong:[pascal]program program100;
const
Niesk=0;
var
tab: array[1..1000000] of qword;

i,j,k,h,p: longint;
max,printed: qword;

[/pascal]

In http://acm.uva.es/problemset/pascal.html it says

Do NOT use LongInt type!

Can that be the reason for the error?

[zack]

In the pascal info page at http://acm.uva.es/problemset/pascal.html they say that "longint" isn't to be used.

I'm using free pascal to compile and the only way to get the program working with bigger numbers ( the 900 1000 input, for example) is to use bigint.

The code outputs the correct result for all the sample inputs provided.

I already submited "integer" and "longint" (to i and j) versions of the code and both give WA.

- Is the problem in "longint" / "integer" or in something else?