100 - The 3n + 1 problem

[richardxx]

No one can answer that?

OK, any guy willing to share your code?
Thx.

[pankaj trivedi]

Dont create new thread for the existing ones. Your problem has been discussed in the existing thread. anyways you need to print the output in the order it is given in input

[happyboyz]

#include<stdio.h>

void swap(int *p, int *q);

int calculation(int n);
int main(void)
{
int i, j, n, start, end;
int count, maximum = 0;

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

start = i;
end = j;

if(i > j)
{
swap(&i, &j);
}

n = i+1;

while(i <= n && n <= j)
{
count = calculation(n);

n++;

if(maximum < count)
maximum = count;
}

printf("%d %d %d", start, end, maximum);

return 0;
}

void swap(int *p, int *q)
{
int tmp;

tmp = *p;
*p = *q;
*q = tmp;
}

int calculation(int n)
{
int cnt = 1;

while(n != 1)
{
if(n % 2 == 1)
n = (3*n)+1;
else
n = n/2;

++cnt;
}

return cnt;
}[/b]


what is it wrong above source code??
I'm Korean.
I can't speak English.
please understand me.
I don't know that what is wrong abvove source code.
Input same SampleInput and Output same SampleOutput.
please teach me what is wrong abvove source code. [/b]

[genti]

Why do I get a WA from the Compiler??? I've tried it, works everything fine, the results I get from my computer coincide with those of the output example. Any help or suggestion would be highly appreciated.
Thanks

Problem solved

[little joey]

Did you read the umpty or so messages on this problem? The mistake you made must have been posted and answered at least a hunded times by now. Read the output secification carefully.

[genti]

I made the necessary corrections so that the output order of i and j matches the input order, but I'm still getting WA. Reading other posts hasn't helped much.

[Jan]

Input will be terminated by EOF. So, use

Code: Select all

while(scanf("%lu %lu",&i,&j)==2)

And make sure that your code handles multiple cases correctly.

[helloneo]

search first..!

http://online-judge.uva.es/board/viewtopic.php?t=3015

[nnahata]

Thxs pankaj......now i got mistake...

[chaturvedi]

I am new to online judge.. Can anybody tell me when is generally input terminated, see in problems like Australian Voting the no. of people voting is not specified so I donot know how is the input terminated... I tried to use blank line to terminate the input in 3n+1 problem and it didnt work... I had solved the problem before by using the statement while(scanf("%d",&k)==1) for terminating the input... since I wanted to test whether the blank line thing works or not I tried it with 3n+1... It didnt work I got TLE....Heres my code.... the algo is correct as I have got it AC please check for the input procedure is correct or not...


#include <stdio.h>
#include <string.h>
void swap(unsigned long int *a,unsigned long int *b);

int senti=0;
int input(char *,char *);
int main()
{
unsigned long int j;
unsigned short int count;
unsigned long int k,l,m,temp;
char ch,ch1;int temp1,temp2;
char xy[100],yz[100];
int g;
while(1)
{

m=0;
senti=0;

g=input(xy,yz);

k=atol(xy);
l=atol(yz);

if (g==1)
return 0;

if(k>l)
swap(&l,&k);


if(k!=0)
{
for(j=k;j<=l;j++)
{
temp=j;
count=1;
if((2*j)>l){
while(temp!=1)
{
if((temp%2)==1)
temp=temp*3+1;
else
temp=temp/2;
count++;
}
}
if(m<count)
m=count;
}
}
if(senti==1)
swap(&l,&k);

if(k!=0 && l!=0)
printf("%li %li %li\n",k,l,m);


}

return 0;
}

void swap(unsigned long int *a,unsigned long int *b)
{
int hold=*a;
*a=*b;
*b=hold;
senti=1;
}




int input(char *x ,char *y)
{
char str[200];
int a;

char *temp;

gets(str);
temp=str;

for(a=0;str[a]==' ';a++);
temp=temp+a;

strcpy(str,temp);

if(strcmp(str,"")==0)
return 1;

for(a=0;str[a]!='\0';a++)
{
if(str[a]==' ')
{
strncpy(x,str,a);
x[a]='\0';

temp=str;

while(str[a+1]==' ')
a++;

temp=temp+a+1;
break;
}
}

for(a=0;temp[a]!=' ';a++);
temp[a]='\0';


strcpy(y,temp);
return 0;
}

[shamim]

Most recent problems usually state the number of cases at the begining.

And for problems like 3*n+1, you have to test for the end of file condition which is usually done by

Code: Select all

while ( scanf("%d %d",&a,&b) == 2 )

, for this problem.

And there are many problems, deciding the number of input in a line or number of lines in a set of input must be determined.

for the first case, the function strtok() is useful and for the second case, sets are seperated by a blank line, so you must use gets to take a line of input and then determine if its blank or not.

And for this prob, there is no need to take input as char* first as

Code: Select all

scanf("%d %d")

will do the job.

[Lingyis]

On page 2 some people discussed the performance of some of the submissions takes 0.00 CPU seconds to run... using a precalculated table would indeed be very fast, but how then does the program take up only 64K of memory? (memory information is also displayed)

A 1,000,000 length int (or short, for that matter) array clearly takes up a lot more than 64k.

How it can be done?

For now, I'll have to assume they just keep resubmitting and making their precalculated array smaller and smaller until the they find the minimum number that the robot judge would accept their solution.

[Lingyis]

So I submitted one that uses a 1,000,000 sized array, calculations are done on the fly, i.e. no pre-caculations.

That finished running in 0.104s, a huge improvement from the previous naive straighforward no-tabulation implementation, which took 2.56s to run.

But it also took up 2344 kB.

But I would really appreciate if someone could point out how one can get it to under 0.02s using just 64 kB! Thanks in advance.

[popinc]

Can someone please shed some light on how to achieve good runtime and memory usage performance for problem 100, especially runtime?

There are a lot of gurus whose algorithms only cost less than 5ms, but my algorithm costs about 1s. I wonder how did they achieve this performance.

Thanks a lot

[Jan]

Dont open a new thread if there is one already. About reducing time - you can store suppose 100000 values, and while calculating, if 'n' is less than or equal to this value, then you can use the value from the stored table.