If you get WA in problem 100, read me before post!

[nightdog]

good luck with the next problem

[fangs404]

good luck with the next problem

thanks. hopefully, i won't have any problems any more (other than algorithmical), now that i know the way that the judge wants us to parse and read in strings. thanks for all your help.

[Farqaleet]

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]

[Farqaleet]

I found out why the first one is accepted by the judge.

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.

[nightdog]

in the second one, you don't quit the program unless you have a valid INPUT with the value 0.
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]

[Farqaleet]

You are right. I didn't think of that. Thanx for the help.

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.

[Farqaleet]

Sorry for the typo above. Here is what does work
[cpp]
while(scanf("%d %d",&i,&j) != 0)
[/cpp]

[39949FP]

What's wrong with this code???
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[i]>='0' && aux[i]<='9'; i++){
number*=10;
number+=aux[i]-'0';
}
*min=number;

number=0;
i++;
while(aux[i]<'0' || aux[i]>'9') i++;

while(aux[i]!='\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[i]>maximum) maximum=lengthVector[i];
i++;
}

return(maximum);
}

int main(){
long long int i;
int min=1, max=1;

/*Zero the array*/
for(i=2; i<1000001; i++) lengthVector[i]=0;
lengthVector[1]=1;

/*Fills all the array lengthVector*/
for(i=2; i<1000001; i++){
if(lengthVector[i]==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]

[Farqaleet]

I don't see anything wrong with the logic.

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.

[Farqaleet]

I think I know why the judge is rejecting your program. You are not looking out for spaces at the start of the input. Put some code that skips over spaces. A better way to do it is to use
[cpp]
isspace(aux[i]);
[/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.

[Klexer]

I m gettin WA everytime i submit this
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

[nightdog]

your program does not output correctly... it should wait for the end of all the input, and then output the results by order... besides that, your program seems fine

good luck

[JW]

My code has got LT. Why?
[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]

[nightdog]

if you got a time limit exceeded from the online judge, it's probably because your algorithm is slow or inefficient in some point.. i'd suggest changing the part where you find the higher cycle length, here's a suggestion: instead of using an array to store all values of the cycle length, override the current maxcycle value if the one u just got is bigger. that way, when you end the cycle, you'll have the biggest cycle length.

[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.

[JW]

Thank nightdog.
Do you mean my input and output are wrong?