100 - The 3n + 1 problem

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 » Sun Nov 06, 2005 9:41 am

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
New poster
Posts: 1
Joined: Wed Oct 26, 2005 8:13 am

Re: ....

Post by amo-ej1 » Mon Nov 07, 2005 12:47 pm

chenhuansheng wrote: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
Learning poster
Posts: 94
Joined: Fri Nov 25, 2005 7:29 pm

input using C for 100

Post by abhi » Sat Nov 26, 2005 12:06 pm

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 ?????

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Sat Nov 26, 2005 12:48 pm

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
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by ayon » Sat Nov 26, 2005 1:39 pm

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
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Sun Nov 27, 2005 7:17 am

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
Learning poster
Posts: 94
Joined: Fri Nov 25, 2005 7:29 pm

fastest method for 100

Post by abhi » Sun Nov 27, 2005 8:59 am

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
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun » Sun Nov 27, 2005 11:15 am

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

Dewr
New poster
Posts: 6
Joined: Sun Dec 04, 2005 4:08 pm

help, 100

Post by Dewr » Sun Dec 04, 2005 4:14 pm

its the code...

Code: Select all

see below.
TIME LIMIT ERROR. help!
Last edited by Dewr on Sun Dec 04, 2005 7:51 pm, edited 1 time in total.

User avatar
Rocky
Experienced poster
Posts: 124
Joined: Thu Oct 14, 2004 9:05 am
Contact:

Abt TLE In 100

Post by Rocky » Sun Dec 04, 2005 6:29 pm

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
New poster
Posts: 6
Joined: Sun Dec 04, 2005 4:08 pm

i used {search button} but!

Post by Dewr » Sun Dec 04, 2005 7:50 pm

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

User avatar
Rocky
Experienced poster
Posts: 124
Joined: Thu Oct 14, 2004 9:05 am
Contact:

abt 100

Post by Rocky » Sun Dec 04, 2005 9:50 pm

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

GOOD LUCK
Rocky

User avatar
Rocky
Experienced poster
Posts: 124
Joined: Thu Oct 14, 2004 9:05 am
Contact:

abt 100

Post by Rocky » Sun Dec 04, 2005 9:58 pm

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

it may help you

GOOD LUCK
Rocky

Dewr
New poster
Posts: 6
Joined: Sun Dec 04, 2005 4:08 pm

ah-HA

Post by Dewr » Mon Dec 05, 2005 7:43 am

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
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun » Mon Dec 05, 2005 9:40 am

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

Post Reply

Return to “Volume 1 (100-199)”