*Hello Brother,*

It is not called memorization.

The correct form is MEMOIZATION..

Thank you.

ANUPAMIt is not called memorization.

The correct form is MEMOIZATION..

Thank you.

ANUPAM

**Moderator:** Board moderators

Please can anybody tell me why the judge accepts the first one but doesn't accept the second one and gives a time-limit exceeded error. While on my computer with MSVC++ compiler it's exactly the opposite; the first one runs fine while in the second case time is exceeded because the loop doesn't exit with start and end are zero.

[cpp]

int main(int argc, char* argv[])

{

long nStart, nEnd, nMax;

RedNum[1]=1;

while(cin>>nStart>>nEnd)

{

if(nStart<nEnd)

nMax = MaxCycle(nStart, nEnd);

else

nMax = MaxCycle(nEnd, nStart);

cout << nStart << ' ' << nEnd << ' ' << nMax << endl;

}

return 0;

}

[/cpp]

[cpp]

#include <iostream.h>

#define SIZE 1000000

unsigned short MaxCycle(unsigned long Start, unsigned long End);

unsigned short ReduceAlgo(unsigned long n);

unsigned short ReduceAlgo2(unsigned long n);

unsigned short RedNum[SIZE + 1] = {0};

int main(int argc, char* argv[])

{

long nStart, nEnd, nMax;

RedNum[1]=1;

scanf("%d %d", &nStart, &nEnd);

while(nStart!=0 && nEnd!=0)

{

if(nStart<nEnd)

nMax = MaxCycle(nStart, nEnd);

else

nMax = MaxCycle(nEnd, nStart);

printf("%d %d %d\n", nStart, nEnd, nMax);

scanf("%d %d", &nStart, &nEnd);

}

return 0;

}

unsigned short MaxCycle(unsigned long Start, unsigned long End)

{

unsigned short nMax=1, nCur;

for(;Start<=End; Start++)

{

nCur = ReduceAlgo(Start);

if(nCur > nMax)

nMax = nCur;

}

return nMax;

}

/* Recursive */

unsigned short ReduceAlgo(unsigned long n)

{

if(n==1)

return 1;

if(n<SIZE)

{

if(RedNum[n])

return RedNum[n];

if(n%2)

RedNum[n] = ReduceAlgo(3*n + 1) + 1;

else

RedNum[n] = ReduceAlgo(n/2) + 1;

return RedNum[n];

}

else

{

if(n%2)

return ReduceAlgo2(3*n + 1) + 1;

else

return ReduceAlgo2(n/2) + 1;

}

}

/* iterative */

unsigned short ReduceAlgo2(unsigned long n)

{

short ctr=1;

while(n != 1)

{

if(n<SIZE && RedNum[n])

return RedNum[n] + ctr - 1;

if(n%2)

n = 3*n + 1;

else

n = n/2;

ctr++;

}

return ctr;

}[/cpp]

[/cpp]

[cpp]

int main(int argc, char* argv[])

{

long nStart, nEnd, nMax;

RedNum[1]=1;

while(cin>>nStart>>nEnd)

{

if(nStart<nEnd)

nMax = MaxCycle(nStart, nEnd);

else

nMax = MaxCycle(nEnd, nStart);

cout << nStart << ' ' << nEnd << ' ' << nMax << endl;

}

return 0;

}

[/cpp]

[cpp]

#include <iostream.h>

#define SIZE 1000000

unsigned short MaxCycle(unsigned long Start, unsigned long End);

unsigned short ReduceAlgo(unsigned long n);

unsigned short ReduceAlgo2(unsigned long n);

unsigned short RedNum[SIZE + 1] = {0};

int main(int argc, char* argv[])

{

long nStart, nEnd, nMax;

RedNum[1]=1;

scanf("%d %d", &nStart, &nEnd);

while(nStart!=0 && nEnd!=0)

{

if(nStart<nEnd)

nMax = MaxCycle(nStart, nEnd);

else

nMax = MaxCycle(nEnd, nStart);

printf("%d %d %d\n", nStart, nEnd, nMax);

scanf("%d %d", &nStart, &nEnd);

}

return 0;

}

unsigned short MaxCycle(unsigned long Start, unsigned long End)

{

unsigned short nMax=1, nCur;

for(;Start<=End; Start++)

{

nCur = ReduceAlgo(Start);

if(nCur > nMax)

nMax = nCur;

}

return nMax;

}

/* Recursive */

unsigned short ReduceAlgo(unsigned long n)

{

if(n==1)

return 1;

if(n<SIZE)

{

if(RedNum[n])

return RedNum[n];

if(n%2)

RedNum[n] = ReduceAlgo(3*n + 1) + 1;

else

RedNum[n] = ReduceAlgo(n/2) + 1;

return RedNum[n];

}

else

{

if(n%2)

return ReduceAlgo2(3*n + 1) + 1;

else

return ReduceAlgo2(n/2) + 1;

}

}

/* iterative */

unsigned short ReduceAlgo2(unsigned long n)

{

short ctr=1;

while(n != 1)

{

if(n<SIZE && RedNum[n])

return RedNum[n] + ctr - 1;

if(n%2)

n = 3*n + 1;

else

n = n/2;

ctr++;

}

return ctr;

}[/cpp]

[/cpp]

I don't know why it takes more time. Remove the condition

[cpp] curNumber > 100 [/cpp]

In a loop of a million, this will take more processing than it will without it.

I have used the same learning technique using recursive decent rather than iterative. It gave me 0.131. see if you can gain some points and help me with my problem. Here it is:

http://online-judge.uva.es/board/viewto ... c&start=45

[cpp] curNumber > 100 [/cpp]

In a loop of a million, this will take more processing than it will without it.

I have used the same learning technique using recursive decent rather than iterative. It gave me 0.131. see if you can gain some points and help me with my problem. Here it is:

http://online-judge.uva.es/board/viewto ... c&start=45

The reason is that rather than handling the stdin directly, the judge simply redirects stdin to a file so when we read, it reads from a file. So when the EOF character of the file is encountered, the while loop exits. But EOF = 0 so the second one should also exit but it doesn't. And I still don't know why.

the judge doesn't input u that value, it just gives you an EOF.

the solution would be checking for EOF in the return value of scanf, not it's variables.

wrong:

[c]

scanf("%d %d",&i,&j);

while(i != 0 && j != 0)

[/c]

right:

[c]

while(scanf("%d %d",&i,&j) != EOF)

[/c]

I confused it with another question that did give 0 0 as the ending input.

But I don't think that the second one should work either. The reason is that scanf returns the number of inputs read, not what was read. I haven't tested it but I think it is so. so if scanf reads 0 numbers for the last line and EOF = -1 as given below then it will still continue.

But this definitely does work:

[cpp]

while(scanf("%d %d",&i,&j) != EOF)

[/cpp]

well any ways I found what the problem was. Following is how IOS.h defines some constants

[cpp]

#ifndef NULL

#define NULL 0

#endif

#ifndef EOF

#define EOF (-1)

#endif

[/cpp]

EOF is -1, not 0, which was my mistake. I mistook EOF to be 0;

Thanx alot.

I have tried everything...

I can't see what's wrong!!!

And I am not supposing that the second number is greater than the first one.

Can anyone help me?

[c]

#include <stdio.h>

#include <unistd.h>

/* Read from standard input

Returns 0 if there's nothing there

*/

int readInput(int * min, int * max){

char aux[20];

int number=0;

int i=0;

read(0, aux, 1);

if(aux[0]<'0' || aux[0]>'9') return 0;

while(aux[i++]!='\n'){

read(0, aux+i, 1);

}

if(i==1) return 0;

for(i=0; aux*>='0' && aux**<='9'; i++){*

number*=10;

number+=aux*-'0';*

}

*min=number;

number=0;

i++;

while(aux*<'0' || aux**>'9') i++;*

while(aux*!='\n'){*

number*=10;

number+=aux[i++]-'0';

}

*max=number;

return 1;

}

int lengthVector[1000001];

/*Returns the cycle length of number

Fills lengthVector

*/

int getCycleLength(long long int number){

long long int nxtNumber;

if(number<1000001){

if(lengthVector[number]!=0) return lengthVector[number];

if(number%2 == 1) nxtNumber=3*number+1;

else nxtNumber = number/2;

return(lengthVector[number] = getCycleLength(nxtNumber) + 1);

}else{

if(number%2 == 1) nxtNumber=3*number+1;

else nxtNumber = number/2;

return(getCycleLength(nxtNumber) + 1);

}

}

/*Returns the greatest cycle in [min:max]

*/

int getMaxCycle(int min, int max){

int maximum = lengthVector[min];

int i = min+1;

while(i<=max){

if(lengthVector*>maximum) maximum=lengthVector**;*

i++;

}

return(maximum);

}

int main(){

long long int i;

int min=1, max=1;

/*Zero the array*/

for(i=2; i<1000001; i++) lengthVector*=0;*

lengthVector[1]=1;

/*Fills all the array lengthVector*/

for(i=2; i<1000001; i++){

if(lengthVector*==0){*

getCycleLength(i);

}

}

/*Receiving the inputs and printing the max cycles*/

while(readInput(&min,&max)){

if(min>max) printf("%d %d %d\n", min, max, getMaxCycle(max, min));

else printf("%d %d %d\n", min, max, getMaxCycle(min,max));

}

return 0;

}

[/c]

I can't see what's wrong!!!

And I am not supposing that the second number is greater than the first one.

Can anyone help me?

[c]

#include <stdio.h>

#include <unistd.h>

/* Read from standard input

Returns 0 if there's nothing there

*/

int readInput(int * min, int * max){

char aux[20];

int number=0;

int i=0;

read(0, aux, 1);

if(aux[0]<'0' || aux[0]>'9') return 0;

while(aux[i++]!='\n'){

read(0, aux+i, 1);

}

if(i==1) return 0;

for(i=0; aux

number*=10;

number+=aux

}

*min=number;

number=0;

i++;

while(aux

while(aux

number*=10;

number+=aux[i++]-'0';

}

*max=number;

return 1;

}

int lengthVector[1000001];

/*Returns the cycle length of number

Fills lengthVector

*/

int getCycleLength(long long int number){

long long int nxtNumber;

if(number<1000001){

if(lengthVector[number]!=0) return lengthVector[number];

if(number%2 == 1) nxtNumber=3*number+1;

else nxtNumber = number/2;

return(lengthVector[number] = getCycleLength(nxtNumber) + 1);

}else{

if(number%2 == 1) nxtNumber=3*number+1;

else nxtNumber = number/2;

return(getCycleLength(nxtNumber) + 1);

}

}

/*Returns the greatest cycle in [min:max]

*/

int getMaxCycle(int min, int max){

int maximum = lengthVector[min];

int i = min+1;

while(i<=max){

if(lengthVector

i++;

}

return(maximum);

}

int main(){

long long int i;

int min=1, max=1;

/*Zero the array*/

for(i=2; i<1000001; i++) lengthVector

lengthVector[1]=1;

/*Fills all the array lengthVector*/

for(i=2; i<1000001; i++){

if(lengthVector

getCycleLength(i);

}

}

/*Receiving the inputs and printing the max cycles*/

while(readInput(&min,&max)){

if(min>max) printf("%d %d %d\n", min, max, getMaxCycle(max, min));

else printf("%d %d %d\n", min, max, getMaxCycle(min,max));

}

return 0;

}

[/c]

I not assuming that the fsecond is bigger...

[c]

#include <stdio.h>

#include <unistd.h>

/* Read from standard input

Returns 0 if there's nothing there

*/

int readInput(int * min, int * max){

char aux[20];

int number=0;

int i=0;

read(0, aux, 1);

if(aux[0]<'0' || aux[0]>'9') return 0;

while(aux[i++]!='\n'){

read(0, aux+i, 1);

}

if(i==1) return 0;

for(i=0; aux

number*=10;

number+=aux

}

*min=number;

number=0;

i++;

while(aux

while(aux

number*=10;

number+=aux[i++]-'0';

}

*max=number;

return 1;

}

int lengthVector[1000001];

/*Returns the cycle length of number

Fills lengthVector

*/

int getCycleLength(long long int number){

long long int nxtNumber;

if(number<1000001){

if(lengthVector[number]!=0) return lengthVector[number];

if(number%2 == 1) nxtNumber=3*number+1;

else nxtNumber = number/2;

return(lengthVector[number] = getCycleLength(nxtNumber) + 1);

}else{

if(number%2 == 1) nxtNumber=3*number+1;

else nxtNumber = number/2;

return(getCycleLength(nxtNumber) + 1);

}

}

/*Returns the greatest cycle in [min:max]

*/

int getMaxCycle(int min, int max){

int maximum = lengthVector[min];

int i = min+1;

while(i<=max){

if(lengthVector

i++;

}

return(maximum);

}

int main(){

long long int i;

int min=1, max=1;

/*Zero the array*/

for(i=2; i<1000001; i++) lengthVector

lengthVector[1]=1;

/*Fills all the array lengthVector*/

for(i=2; i<1000001; i++){

if(lengthVector

getCycleLength(i);

}

}

/*Receiving the inputs and printing the max cycles*/

while(readInput(&min,&max)){

if(min>max) printf("%d %d %d\n", min, max, getMaxCycle(max, min));

else printf("%d %d %d\n", min, max, getMaxCycle(min,max));

}

return 0;

}

[/c]

If you are getting the wrong answer reply from the judge then there can only be one thing wrong. You are assuming three things.

One that the the character set that the judge's computer is using has:

'0' - '9' as consecutive characters.

Two, that they are in the correct ascending order and not in decending or other random order.

Three and most importantly which most probably is the reason for your programs wrong answers is that you are assuming that the judge's computer uses '\n' as the line ending character in its files. Rember some files have '\r\n' which both combined give the next line character i.e. not simply line-feed but the combination of "Carriage-return, Line-feed".

If there is something else wrong, Then I can't say. The judge might even be using files that end lines with '\r' for all we know, so you can get "Time limit exceede" error too.

The second-best thing to do is to use these functions instead:

[cpp]

isspace();

isdigit();

isalpha();

sscanf();

sfprintf();

...

[/cpp]

The best thing ofcourse is to use

[cpp]

cin

scanf

[/cpp]

for reading data.

[cpp]

isspace(aux

[/cpp]

as it skips over spaces, tabs, \r, \n etc. Really any kind of a character representing empty spaces. Also to end the program look for the EOF character because the judge redirects the stdin to a file so you will always get this as the last character of the file, so you can always know for sure that your program is not exceeding time because it is waiting for more input (maybe invalid input) to end, rather than EOF.

Pls help me

/*@JUDGE_ID: 42099PZ 100*/

#include<iostream>

using namespace std;

long findmax(long a,long b)

{

long i,j,k,temp,max,count;

if(a>b)

{

temp=a;

a=b;

b=temp;

}

max=1;

count=1;

for(i=a,j=i;i<=b;i++,j=i)

{

if(count>max)

{

max=count;

}

count=1;

while(j!=1)

{

count++;

if(j%2==0)

{

j/=2;

}

else

{

j=(3*j)+1;

}

}

}

return max;

}

main()

{

long a,b;

while(cin>>a>>b)

{

cout<<a<<" "<<b<<" ";

long x=findmax(a,b);

cout<<x<<endl;

}

}

/*@END_OF_SOURCE_CODE*/

2,17 Top

Thanx in advance

[c]#include <stdio.h>

unsigned int findmaxcycle(unsigned int i, unsigned int j)

{

register unsigned int n, counter, min, max, k, p;

static cycles[999999];

counter = 1;

k = 1;

if (i > j)

{min = j; max = i;}

else

{min = i; max = j;}

for (k = min; k <= max; k++)

{

n = k;

while (n != 1)

{

if (n % 2 != 0)

n = 3*n + 1;

else

n = n / 2;

counter++;

}

cycles[k] = counter;

counter = 1;

}

for (k = min + 1, p = min; k <= max; k++)

{

if (cycles[p] < cycles[k]) p = k;

}

return cycles[p];

}

int main()

{

unsigned int i, j;

while(1) {

scanf("%d%d", &i, &j);

printf("%d %d %d\n", i, j, findmaxcycle(i, j));}

return 0;

}[/c]

[c] for(input=i;input<=j;input++) {

long int count=1,n=input;

while(n != 1) {

count++;

if((n % 2) != 0)

n = (3*n)+1;

else

n = n >> 1;

}

if(count > maxcycle)

maxcycle =count;

}[/c]

also, you are supposed to get all inputs and THEN output the results.