100 - The 3n + 1 problem

[chunyi81]

I got the following errors compiling your code with gcc 2.95 as well as gcc 3.3.2:

The command I typed to compile was: gcc p100.c -o p100

p100.c was the file I saved your code in.

Undefined first referenced
symbol in file
clrscr /var/tmp/ccXoI3I5.o
getche /var/tmp/ccXoI3I5.o
gotoxy /var/tmp/ccXoI3I5.o
puttext /var/tmp/ccXoI3I5.o
wherex /var/tmp/ccXoI3I5.o
wherey /var/tmp/ccXoI3I5.o
ld: fatal: Symbol referencing errors. No output written to p100
collect2: ld returned 1 exit status

[amo-ej1]

My programme compile successfully in TURBOR C

the online judge doesn't use that compiler. And all the undefined references chunyi81's gcc mentioned are functions that are specific to your compiler (and thus nog available to gcc, nor to the online judge)

[abhi]

i am totally new to ACM.........so plz help me
how do i accept inputs from the file without using fscanf()???
how do i accept inputs from the file using scanf() and how do i keep on accepting it till i get the EOF ?????

[shamim]

You assume that you are taking input from file. That is, use the standard input and output routines like scanf(), printf().

To read until EOF, for prob 100, use:

Code: Select all

while ( scanf("%d %d",&a,&b) == 2 ) {
// do something.
}

== 2, indicates that you are expecting two input for scanf(). If EOF file is reached, the loop terminates.

[ayon]

moreover, scanf() return EOF while it reaches to EOF. so you can use

Code: Select all

while(scanf("%d%d", &a, &b) != EOF)
{
...
}

because it is sometime boring to count how many data is being scanned

[shamim]

Actually EOF has a problem. If the input file contains extra characters at the end which are escape characters, it may happen that EOF is never reached and no integer is read either. In such cases, the Program will not finish in Time and get TLE.

I remember, I had this problem once and on looking at a thread, I changed EOF to == (inputcount) and got AC after getting many TLE's.

[abhi]

hey i got problem 100 AC . but it took 3.7 s . many people have got it AC in 0.00 ,0.002...... etc. i would like to know what is the fastest way to solve this problem

[mamun]

Dynamic. Store the values in a large array as much as possible and retrieve them when necessary.

[Dewr]

its the code...

Code: Select all

see below.

TIME LIMIT ERROR. help!

[Rocky]

I Not Debug Your Code But There Are Many Many Post On The Problem In Board So Search Them And Find Your Bug........

GOOD LUCK
Rocky

[Dewr]

i clicked {search button} but she couldnt serach anyone.
(i inputed "time", "100"....)

and i update

Code: Select all

#include <stdio.h>
#include <memory.h>
#ifndef ONLINE_JUDGE
#include <time.h>
clock_t start, finish;
#endif

unsigned int inputi;
unsigned int inputj;
unsigned int cycle;
unsigned int nownumber;
unsigned int maxcycle;
unsigned int thenumber;
unsigned int dummy;
unsigned int boolsw = 0;
unsigned int * data;

void checkitup();
unsigned int checkit();

int main()
{
    data = new unsigned int[1000000];
    memset(data, 0, 4000000);
    lalala:
    maxcycle = 1;
    
    if(scanf("%u %u", &inputi, &inputj)==EOF)
    {
       delete[] data; 
       return 0;
    }
    
    #ifndef ONLINE_JUDGE
    if(inputi<1 || inputi >999999 || inputj<1 || inputj >999999)
    {
      printf("min = 1      max = 999999\n");
      goto lalala;
    }
    #endif
    
    #ifndef ONLINE_JUDGE
    start =clock();
    #endif
    if(inputi > inputj)
    {
         boolsw^=1;
         inputi^=inputj;
         inputj^=inputi;
         inputi^=inputj;
    }
    nownumber = inputi; 
    checkitup();
    
    do{
             nownumber++;
             if(checkit())
               continue;
             checkitup();
             }while(nownumber!=inputj);
    #ifndef ONLINE_JUDGE
    finish = clock();
    printf("it takes %f seconds.\n", (double)(finish-start)/(double)CLK_TCK);
    #endif
    
    if(boolsw)
    {
         boolsw^=1;
         inputi^=inputj;
         inputj^=inputi;
         inputi^=inputj;
    }
    printf("%u %u %u\n", inputi, inputj, maxcycle);
    goto lalala;
}

void checkitup()
{
     if(data[nownumber])
     {
       if(maxcycle<data[nownumber])
         maxcycle = data[nownumber];
       return;
     }
       thenumber = nownumber;
       cycle = 0;
       while(1)
       {
             cycle++;
             if(thenumber == 1)
               break;
             else if(thenumber&1)              
               thenumber += (thenumber << 1)+1;               
             else
               thenumber>>=1;
       }
       data[nownumber] = cycle;
       if(maxcycle < cycle)
         maxcycle = cycle;
}

unsigned int checkit()
{
     dummy = nownumber<<1;
     if(!(dummy&1) && dummy<=inputj)
       return 1;
     else
       return 0;
}

[Rocky]

i can not understand your code...but can you explain your method to me..
i dont understant why you use array..

GOOD LUCK
Rocky

[Rocky]

read the following thread:
http://online-judge.uva.es/board/viewto ... highlight=

it may help you

GOOD LUCK
Rocky

[Dewr]

RUNTIME ERROR!!


ok. let me explain.

the array is for store results. (pay memory for speed)
i dont want reoperation!

Code: Select all

unsigned int * data = new unsigned int [1000000];
............
if(data[nownumber])
     {
       if(maxcycle<data[nownumber])
         maxcycle = data[nownumber];
       return;
     }

"boolsw" is switch for memory swapped of not swapped.

Code: Select all

if(inputi > inputj)
    {
         boolsw^=1;
         inputi^=inputj;
         inputj^=inputi;
         inputi^=inputj;
    }

"dummy" is for store nownumber<<1(same nownumber*2)
if there are "n*2" in next-checklist, the operation is unnecessary.

Code: Select all

unsigned int checkit()
{
     dummy = nownumber<<1;
     if(dummy<=inputj)
       return 1;
     else
       return 0;
}

[mamun]

The inputs are too big to fit in unsigned int. Use long instead.