OJ Board

Posted: **Wed Oct 01, 2003 9:33 am**

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

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

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

Posted: **Wed Oct 01, 2003 11:09 am**

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

Posted: **Wed Oct 01, 2003 3:12 pm**

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.

Posted: **Wed Oct 01, 2003 11:49 pm**

what compiler message do you get ?

Posted: **Thu Oct 02, 2003 3:47 am**

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.

Posted: **Sat Oct 04, 2003 12:05 am**

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?

Posted: **Sun Oct 05, 2003 10:16 am**

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.

Posted: **Wed Oct 08, 2003 2:05 pm**

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.

Posted: **Thu Oct 09, 2003 6:46 am**

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

Posted: **Thu Oct 09, 2003 6:48 am**

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?

Posted: **Thu Oct 09, 2003 7:34 am**

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

Posted: **Thu Oct 09, 2003 7:37 am**

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

Posted: **Thu Oct 09, 2003 2:41 pm**

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.

Posted: **Sun Oct 12, 2003 2:13 am**

OmShanti wrote: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?

Posted: **Sun Oct 12, 2003 2:33 am**

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?

OJ Board

100 - The 3n + 1 problem

Here is my code

100: Compile Error!!

Re: Always WA in 100 [Pascal]