100  The 3n + 1 problem
Moderator: Board moderators

 New poster
 Posts: 11
 Joined: Wed Jun 21, 2006 5:11 pm
 Contact:
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
Anything other than Accepted is irritating,even Presentation Error
http://acm.uva.es/problemset/usersjudge.php?user=40301
http://acm.uva.es/problemset/usersjudge.php?user=40301

 New poster
 Posts: 1
 Joined: Wed Oct 25, 2006 4:54 am
 Location: Korea, of Republic
 Contact:
Problem #100 3n+1 Problem Wrong Answer> please Help
#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]
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]
Problem 100 WA
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
Thanks
Problem solved
Last edited by genti on Sun Oct 29, 2006 8:57 am, edited 2 times in total.
 little joey
 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
Input will be terminated by EOF. So, use
And make sure that your code handles multiple cases correctly.
Code: Select all
while(scanf("%lu %lu",&i,&j)==2)
Ami ekhono shopno dekhi...
HomePage
HomePage
Thxs for suggesting..
Thxs pankaj......now i got mistake...

 New poster
 Posts: 8
 Joined: Mon Jul 10, 2006 9:31 am
RTE 100
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;
}
#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;
}
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, 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 will do the job.
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 )
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")
performance
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.
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.
performance
So I submitted one that uses a 1,000,000 sized array, calculations are done on the fly, i.e. no precaculations.
That finished running in 0.104s, a huge improvement from the previous naive straighforward notabulation 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.
That finished running in 0.104s, a huge improvement from the previous naive straighforward notabulation 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.
100 runtime & mem usage
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
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
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.
Ami ekhono shopno dekhi...
HomePage
HomePage