100 - The 3n + 1 problem
Moderator: Board moderators
simple yet deceptive
the problem 100 has so easy a solution that the judge has even put up as an example.
yet there are people who have submitted that problem in less than
25 ms.can anybody suggest better algorihtms than the simple brute force and the idea of memoization(using an array of 1000000 elements)
yet there are people who have submitted that problem in less than
25 ms.can anybody suggest better algorihtms than the simple brute force and the idea of memoization(using an array of 1000000 elements)
every problem has a short,sweet solution
that is just a bit far away.
that is just a bit far away.
#100 why compile error or time limit? :(
i use LCC-win32, the program can run, but why i get ce now? thanks
//3n+1
#include <stdio.h>
#define MAXNUM 60000 //cache
int table[MAXNUM];
int GetCount(unsigned long int n)
{
unsigned long int nn;
int result;
if (n<=MAXNUM && table[n-1]!=0)
return table[n-1];
if (n&1)
nn=n*3+1;
else
nn=n>>1;
result=1+GetCount(nn);
if (n<=MAXNUM)
table[n-1]=result;
return result;
}
void main()
{
int start,end;
int i;
int maxCount,thisCount;
for (i=1;i<MAXNUM;i++)
table=0;
table[0]=1;
while (1)
{
maxCount=0;
scanf("%d %d",&start,&end);
if (start==0 && end==0)
break;
for (i=start;i<=end;i++)
{
thisCount=GetCount(i);
if (thisCount>maxCount)
maxCount=thisCount;
}
printf("%d %d %d\n",start,end,maxCount);
}
}
//3n+1
#include <stdio.h>
#define MAXNUM 60000 //cache
int table[MAXNUM];
int GetCount(unsigned long int n)
{
unsigned long int nn;
int result;
if (n<=MAXNUM && table[n-1]!=0)
return table[n-1];
if (n&1)
nn=n*3+1;
else
nn=n>>1;
result=1+GetCount(nn);
if (n<=MAXNUM)
table[n-1]=result;
return result;
}
void main()
{
int start,end;
int i;
int maxCount,thisCount;
for (i=1;i<MAXNUM;i++)
table=0;
table[0]=1;
while (1)
{
maxCount=0;
scanf("%d %d",&start,&end);
if (start==0 && end==0)
break;
for (i=start;i<=end;i++)
{
thisCount=GetCount(i);
if (thisCount>maxCount)
maxCount=thisCount;
}
printf("%d %d %d\n",start,end,maxCount);
}
}
none
HELP 100 :..( wa/tle
could someone help me with #100? i've almost give up. i tested with many special cases but finally it does not pass 
the following program results in "time limit exceed"(as you can see, i even added some "constants" in the program, so the speed should be fast). if i remove "table[maxnum]" and the "constants", it still results in "tle", however, if i change
scanf("%d %d",&start,&end);
in main() into
if (scanf("%d %d",&start,&end)!=2) break;
it results in "wrong answer"
could someone help me? thank you very much!!!!!!!!
(code see below...
)

the following program results in "time limit exceed"(as you can see, i even added some "constants" in the program, so the speed should be fast). if i remove "table[maxnum]" and the "constants", it still results in "tle", however, if i change
scanf("%d %d",&start,&end);
in main() into
if (scanf("%d %d",&start,&end)!=2) break;
it results in "wrong answer"

could someone help me? thank you very much!!!!!!!!
(code see below...

Last edited by newhh2002 on Mon Jan 27, 2003 5:28 pm, edited 1 time in total.
none
programming guidelines:
no function longer than ten lines
clean identation
try it out!
in case your program was properly indented, use the C function of this board to post it so people can read it!
example:
[c]int main(int argc, char **argv)
{
init();
solve();
clean();
return EXIT_SUCCESS;
}
[/c]
no function longer than ten lines
clean identation
try it out!
in case your program was properly indented, use the C function of this board to post it so people can read it!
example:
[c]int main(int argc, char **argv)
{
init();
solve();
clean();
return EXIT_SUCCESS;
}
[/c]
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli
the problem 100 is very fallacious.
my program was accepted, yet it did not work.
explanation:
some of the intermediate results are greater than 2^32 thus using the C type "unsigned int" or any equivalent is WRONG.
this could lead to wrong results if the judge had chosed the input test data in a vicious (yet fair) way.
i really hope the judge changes the input data of this problem, so my program becomes WA, because it's all it deserves.
my program was accepted, yet it did not work.
explanation:
some of the intermediate results are greater than 2^32 thus using the C type "unsigned int" or any equivalent is WRONG.
this could lead to wrong results if the judge had chosed the input test data in a vicious (yet fair) way.
i really hope the judge changes the input data of this problem, so my program becomes WA, because it's all it deserves.
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli
i tried but still tleLarry wrote:just a note: start doesn't have to be bigger than end.
and please do a search on the forum before asking.. there are a few ways to optimize this problem..

i tried on my pentium 133, speed is not the problem because i used "constants" and "cache", but i can't pass the judge:``(
none
thank you for your advice, i'll post it againepsilon0 wrote:programming guidelines:
no function longer than ten lines
clean identation
try it out!
in case your program was properly indented, use the C function of this board to post it so people can read it!
example:
[c]int main(int argc, char **argv)
{
init();
solve();
clean();
return EXIT_SUCCESS;
}
[/c]

no function longer than ten lines.... well, i first thought #100 is a simple problem so i just decided to use main() and GetCount() (getcount() is a recursion function and i don't want main() to be recursive), i thought the fewer functions, the better. however, i added some "constants" to improve speed, so main() become bigger

none
[c]
//3n+1
#include <stdio.h>
#define MAXNUM 30000
int table[MAXNUM]; //for "cache" use, no need too big
int GetCount(long long n)
{
long long nn;
int result;
if (n<=MAXNUM && table[n-1]!=0) //result is found in "cache"
return table[n-1];
if (n&1)
nn=n*3+1;
else
nn=n>>1;
result=1+GetCount(nn);
if (n<=MAXNUM)
table[n-1]=result; //save to "cache"
return result;
}
void main()
{
int start,end;
int i;
int maxCount,thisCount;
for (i=1;i<MAXNUM;i++) //init cache
table=0;
table[0]=1; //end of init cache
while (1)
{
maxCount=0; //the result of a case is saved here, and is initialized to zero
scanf("%d %d",&start,&end); //wrong here? as mentioned at top
if (start==0 && end==0)
break; //according to "rule"
//start maybe bigger than end, so swap
if (start>end)
{
i=end;
end=start;
start=i;
}
//the following lines are "constants"
if (start<=837799 && end>=837799)
{
printf("%d %d %d\n",start,end,525);
continue;
}
if (start<=626331 && end>=626331)
{
printf("%d %d %d\n",start,end,509);
continue;
}
if (end<626331 && start<=511935 && end>=511935)
{
printf("%d %d %d\n",start,end,470);
continue;
}
if (end<511935 && start<=410011 && end>=410011)
{
printf("%d %d %d\n",start,end,449);
continue;
}
if (end<410011 && start<=230631 && end>=230631)
{
printf("%d %d %d\n",start,end,443);
continue;
} //end of "constants"
for (i=end;i>=start;i--)
{
thisCount=GetCount((long long)i);
if (thisCount>maxCount)
maxCount=thisCount;
}
printf("%d %d %d\n",start,end,maxCount);
}
}
[/c]
thanks for reading!!!!
//3n+1
#include <stdio.h>
#define MAXNUM 30000
int table[MAXNUM]; //for "cache" use, no need too big
int GetCount(long long n)
{
long long nn;
int result;
if (n<=MAXNUM && table[n-1]!=0) //result is found in "cache"
return table[n-1];
if (n&1)
nn=n*3+1;
else
nn=n>>1;
result=1+GetCount(nn);
if (n<=MAXNUM)
table[n-1]=result; //save to "cache"
return result;
}
void main()
{
int start,end;
int i;
int maxCount,thisCount;
for (i=1;i<MAXNUM;i++) //init cache
table=0;
table[0]=1; //end of init cache
while (1)
{
maxCount=0; //the result of a case is saved here, and is initialized to zero
scanf("%d %d",&start,&end); //wrong here? as mentioned at top
if (start==0 && end==0)
break; //according to "rule"
//start maybe bigger than end, so swap
if (start>end)
{
i=end;
end=start;
start=i;
}
//the following lines are "constants"
if (start<=837799 && end>=837799)
{
printf("%d %d %d\n",start,end,525);
continue;
}
if (start<=626331 && end>=626331)
{
printf("%d %d %d\n",start,end,509);
continue;
}
if (end<626331 && start<=511935 && end>=511935)
{
printf("%d %d %d\n",start,end,470);
continue;
}
if (end<511935 && start<=410011 && end>=410011)
{
printf("%d %d %d\n",start,end,449);
continue;
}
if (end<410011 && start<=230631 && end>=230631)
{
printf("%d %d %d\n",start,end,443);
continue;
} //end of "constants"
for (i=end;i>=start;i--)
{
thisCount=GetCount((long long)i);
if (thisCount>maxCount)
maxCount=thisCount;
}
printf("%d %d %d\n",start,end,maxCount);
}
}
[/c]
thanks for reading!!!!
none
finally i know! it's multiple input :`(
but why still WA?
[c]
//3n+1
#include <stdio.h>
#include <string.h>
#define MAXNUM 60000
int table[MAXNUM];
int GetCount(long long n)
{
long long nn;
int result;
if (n<=MAXNUM && table[n-1]!=0)
return table[n-1];
if (n&1)
nn=n*3+1;
else
nn=n>>1;
result=1+GetCount(nn);
if (n<=MAXNUM)
table[n-1]=result;
return result;
}
void main()
{
int start,end;
int i,pc,newp;
int maxCount,thisCount;
char line[20];
for (i=1;i<MAXNUM;i++)
table=0;
table[0]=1;
scanf("%d",&pc);
gets(line);
gets(line);
newp=0;
while (1)
{
maxCount=0;
if (gets(line))
{
if (strlen(line)==0 || sscanf(line,"%d %d",&start,&end)!=2)
{
newp=1;
continue;
}
}
else
break;
if (newp)
{
printf("\n");
newp=0;
}
if (start>end)
{
i=end;
end=start;
start=i;
}
if (start<=837799 && end>=837799)
{
printf("%d %d %d\n",start,end,525);
continue;
}
if (start<=626331 && end>=626331)
{
printf("%d %d %d\n",start,end,509);
continue;
}
if (end<626331 && start<=511935 && end>=511935)
{
printf("%d %d %d\n",start,end,470);
continue;
}
if (end<511935 && start<=410011 && end>=410011)
{
printf("%d %d %d\n",start,end,449);
continue;
}
if (end<410011 && start<=230631 && end>=230631)
{
printf("%d %d %d\n",start,end,443);
continue;
}
for (i=end;i>=start;i--)
{
thisCount=GetCount((long long)i);
if (thisCount>maxCount)
maxCount=thisCount;
}
printf("%d %d %d\n",start,end,maxCount);
}
}
[/c]
but why still WA?
[c]
//3n+1
#include <stdio.h>
#include <string.h>
#define MAXNUM 60000
int table[MAXNUM];
int GetCount(long long n)
{
long long nn;
int result;
if (n<=MAXNUM && table[n-1]!=0)
return table[n-1];
if (n&1)
nn=n*3+1;
else
nn=n>>1;
result=1+GetCount(nn);
if (n<=MAXNUM)
table[n-1]=result;
return result;
}
void main()
{
int start,end;
int i,pc,newp;
int maxCount,thisCount;
char line[20];
for (i=1;i<MAXNUM;i++)
table=0;
table[0]=1;
scanf("%d",&pc);
gets(line);
gets(line);
newp=0;
while (1)
{
maxCount=0;
if (gets(line))
{
if (strlen(line)==0 || sscanf(line,"%d %d",&start,&end)!=2)
{
newp=1;
continue;
}
}
else
break;
if (newp)
{
printf("\n");
newp=0;
}
if (start>end)
{
i=end;
end=start;
start=i;
}
if (start<=837799 && end>=837799)
{
printf("%d %d %d\n",start,end,525);
continue;
}
if (start<=626331 && end>=626331)
{
printf("%d %d %d\n",start,end,509);
continue;
}
if (end<626331 && start<=511935 && end>=511935)
{
printf("%d %d %d\n",start,end,470);
continue;
}
if (end<511935 && start<=410011 && end>=410011)
{
printf("%d %d %d\n",start,end,449);
continue;
}
if (end<410011 && start<=230631 && end>=230631)
{
printf("%d %d %d\n",start,end,443);
continue;
}
for (i=end;i>=start;i--)
{
thisCount=GetCount((long long)i);
if (thisCount>maxCount)
maxCount=thisCount;
}
printf("%d %d %d\n",start,end,maxCount);
}
}
[/c]
none
100, runtime error
can some body point me to the rite directn
it works fine on my machine, for the sample cases
error:
Your program has died with signal 11 (SIGSEGV). Meaning:
Invalid memory reference
Before crash, it ran during 0.027 seconds.
C++:
#include <iostream.h>
int arr[1000001] ;
int get(int d)
{
if (arr[d]!=0)
return arr[d];
else
if (d%2==0)
{ arr[d] = get(d/2)+1;
return arr[d];
}
else
{ arr[d] = get(3*d+1)+1;
return arr[d];
}
}
void main ()
{ int a, b;
int i;
int largest;
for (i=0; i<1000001; i++)
arr = 0;
arr[1]=1;
arr[2] =2;
while (cin>>a>>b)
{ if (a>b) break;
largest = get(a);
for (i=a; i<=b; i++)
{ if (get(i)>largest)
largest = get(i);
}
cout <<a<<" "<<b<<" "<<largest<<endl;
}
}
it works fine on my machine, for the sample cases
error:
Your program has died with signal 11 (SIGSEGV). Meaning:
Invalid memory reference
Before crash, it ran during 0.027 seconds.
C++:
#include <iostream.h>
int arr[1000001] ;
int get(int d)
{
if (arr[d]!=0)
return arr[d];
else
if (d%2==0)
{ arr[d] = get(d/2)+1;
return arr[d];
}
else
{ arr[d] = get(3*d+1)+1;
return arr[d];
}
}
void main ()
{ int a, b;
int i;
int largest;
for (i=0; i<1000001; i++)
arr = 0;
arr[1]=1;
arr[2] =2;
while (cin>>a>>b)
{ if (a>b) break;
largest = get(a);
for (i=a; i<=b; i++)
{ if (get(i)>largest)
largest = get(i);
}
cout <<a<<" "<<b<<" "<<largest<<endl;
}
}
-
- New poster
- Posts: 10
- Joined: Tue Feb 04, 2003 11:38 pm
Wrong Answer on p100 '_'
hi guys, i know you get a lot of postings on problem 100 ... but i've tried everything on this problem and i still get a wrong answer!!! : ( and lots of memory used, i know is because of the array but... Can anybody take a look at it and help me a little bit
[cpp]
#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
int main()
{
register unsigned int first =0;
register unsigned int last =0;
int* array = new int[1000000];
while(scanf("%d %d",&first, &last)==2)
{
register int count=1;
register int max=1;
if(first > last)
{
register unsigned int tmp=first;
first=last;
last=tmp;
}
for(register unsigned int i=first;i<=last;i++)
{
if(array == 0)
{
register unsigned int k=i;
count=1;
while(k!=1)
{
if(k%2 != 0) k=(3*k)+1;
else k/=2;
count++;
}
array=count;
}
else
count=array;
if(max<count)
max=count;
}
printf(" %d\n",max);
char c=getchar();
ungetc(c,stdin);
if(c=='\n')
printf("\n");
}
return 0;
}
[/cpp]

[cpp]
#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
int main()
{
register unsigned int first =0;
register unsigned int last =0;
int* array = new int[1000000];
while(scanf("%d %d",&first, &last)==2)
{
register int count=1;
register int max=1;
if(first > last)
{
register unsigned int tmp=first;
first=last;
last=tmp;
}
for(register unsigned int i=first;i<=last;i++)
{
if(array == 0)
{
register unsigned int k=i;
count=1;
while(k!=1)
{
if(k%2 != 0) k=(3*k)+1;
else k/=2;
count++;
}
array=count;
}
else
count=array;
if(max<count)
max=count;
}
printf(" %d\n",max);
char c=getchar();
ungetc(c,stdin);
if(c=='\n')
printf("\n");
}
return 0;
}
[/cpp]