100  The 3n + 1 problem
Moderator: Board moderators

 Guru
 Posts: 584
 Joined: Thu Jun 19, 2003 3:48 am
 Location: Sanok, Poland
 Contact:
I need help here.... I am still learning C and learning how to use this site as well, and in problem 100 I always get WA but I think my code is correct!!! Please someone check it for me??
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdio.h>
main()
{
float largest = 0;
float temp;
float t,i,j,in,jn;
scanf("%f%f",&i,&j);
if (i > j)
{
in = j;
jn = i;
}
else
{ in = i;
jn = j;
}
for (t = in; t <= jn; t++)
{
temp = cyclelength(t);
if (largest < temp) largest = temp;
}
printf("%.0f %.0f %.0f",i,j,largest);
}
cyclelength(t)
float t;
{
float temp;
float count = 1;
temp = t;
do
{
if ((temp /2) == ((long int)(temp/2))) temp = temp/2;
else temp = 3*temp + 1;
count++;
} while (temp !=1);
return(count);
}
Thanks[/c]
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdio.h>
main()
{
float largest = 0;
float temp;
float t,i,j,in,jn;
scanf("%f%f",&i,&j);
if (i > j)
{
in = j;
jn = i;
}
else
{ in = i;
jn = j;
}
for (t = in; t <= jn; t++)
{
temp = cyclelength(t);
if (largest < temp) largest = temp;
}
printf("%.0f %.0f %.0f",i,j,largest);
}
cyclelength(t)
float t;
{
float temp;
float count = 1;
temp = t;
do
{
if ((temp /2) == ((long int)(temp/2))) temp = temp/2;
else temp = 3*temp + 1;
count++;
} while (temp !=1);
return(count);
}
Thanks[/c]
I can talk to a computer. I speak C.
Really strange timings on p 100 (and possibly others)
Hello,
I really wonder how can a timing of 00:00.00 be achieved, except if the sender has determined the exact input issued by the judge. It just doesn't make sense. Maybe those solutions should be reviewed by the administrators.
I really wonder how can a timing of 00:00.00 be achieved, except if the sender has determined the exact input issued by the judge. It just doesn't make sense. Maybe those solutions should be reviewed by the administrators.
I can't believe this question is being asked again!! My time is 0.000. BUT: I got it when judging system had a serious timing problem. First two times might not be 0.000 exactly because system had different precsion (time less 0.010 was considered 0.000). Now I tried to get zero time but my best was 0.006  and that is pure solution in C. I know that 0.002 is possible though I haven't achieved it. And I believe 0.000 is also possible though you may not agree!
Ivor
P.S. People, please read previous posts!
P.P.S. If you can't achieve what some people have achieved don't go criticizing them if you don't know enough about programming! There might be a lot more in the code than you can imagine.
Ivor
P.S. People, please read previous posts!
P.P.S. If you can't achieve what some people have achieved don't go criticizing them if you don't know enough about programming! There might be a lot more in the code than you can imagine.
There is a theory which states that if ever anyone discovers exactly what the Universe is for and why it is here, it will instantly disappear and be replaced by something even more bizarre and inexplicable.

 New poster
 Posts: 6
 Joined: Mon Jun 03, 2002 8:44 am
yet another WA 100 thread
I get WA. What's really getting to me is I've solved this problem before, and now it seems that no matter how I decide to code it, I get WA.
Can you tell me if you see anything wrong with my code anywhere? Don't post what my problem is quite yet if you see one, but I just can't seem to find one no matter what.
Also, for the following test data, here is what I get:
[cpp]#include <iostream>
using namespace std;
#define PROB_MAX 1000001
int* val;
int solve(long long n)
{
if (n < PROB_MAX && val[n] != 0) return val[n];
if (n % 2 == 0)
{
if (n < PROB_MAX) return (val[n] = solve(n/2)+1);
else return solve(n/2);
}
else
{
if (n < PROB_MAX) return (val[n] = solve(n*3+1)+1);
else return solve(n*3+1);
}
return 1;
}
int main()
{
int beg, end;
val = new int[PROB_MAX];
for (int i = 0; i < PROB_MAX; i++) val = 0;
val[1] = 1;
for (int i = 1; i < PROB_MAX; i++) solve(i);
while (cin >> beg >> end)
{
int m = 0;
if (beg < end)
{
for (int i = beg; i <= end; i++)
{
if (m < val) m = val;
}
}
else
{
for (int i = end; i <= beg; i++)
{
if (m < val) m = val;
}
}
cout << beg << ' ' << end << ' ' << m << endl;
}
}[/cpp]
Can you tell me if you see anything wrong with my code anywhere? Don't post what my problem is quite yet if you see one, but I just can't seem to find one no matter what.
Also, for the following test data, here is what I get:
Code: Select all
1 10
100 200
201 210
900 1000
5000 3000
10 999999
Code: Select all
1 10 20
100 200 125
201 210 89
900 1000 174
5000 3000 238
10 999999 339
using namespace std;
#define PROB_MAX 1000001
int* val;
int solve(long long n)
{
if (n < PROB_MAX && val[n] != 0) return val[n];
if (n % 2 == 0)
{
if (n < PROB_MAX) return (val[n] = solve(n/2)+1);
else return solve(n/2);
}
else
{
if (n < PROB_MAX) return (val[n] = solve(n*3+1)+1);
else return solve(n*3+1);
}
return 1;
}
int main()
{
int beg, end;
val = new int[PROB_MAX];
for (int i = 0; i < PROB_MAX; i++) val = 0;
val[1] = 1;
for (int i = 1; i < PROB_MAX; i++) solve(i);
while (cin >> beg >> end)
{
int m = 0;
if (beg < end)
{
for (int i = beg; i <= end; i++)
{
if (m < val) m = val;
}
}
else
{
for (int i = end; i <= beg; i++)
{
if (m < val) m = val;
}
}
cout << beg << ' ' << end << ' ' << m << endl;
}
}[/cpp]
For the last input, I got a different answer:
Code: Select all
10 999999 525

 New poster
 Posts: 6
 Joined: Mon Jun 03, 2002 8:44 am
thanks guys =)
it should have returned val[n], but i did forget a plus one somewhere else
here's the correct solve function:
[cpp]int solve(long long n)
{
if (n < PROB_MAX && val[n] != 0) return val[n];
if (n % 2 == 0)
{
if (n < PROB_MAX) return (val[n] = solve(n/2)+1);
else return solve(n/2)+1; //forgot this one
}
else
{
if (n < PROB_MAX) return (val[n] = solve(n*3+1)+1);
else return solve(n*3+1)+1; // and this one
}
return 1;
}
[/cpp]
it should have returned val[n], but i did forget a plus one somewhere else
here's the correct solve function:
[cpp]int solve(long long n)
{
if (n < PROB_MAX && val[n] != 0) return val[n];
if (n % 2 == 0)
{
if (n < PROB_MAX) return (val[n] = solve(n/2)+1);
else return solve(n/2)+1; //forgot this one
}
else
{
if (n < PROB_MAX) return (val[n] = solve(n*3+1)+1);
else return solve(n*3+1)+1; // and this one
}
return 1;
}
[/cpp]
I got WA too. "Your program has not solved the problem. It ran during 0.000 seconds."
Code: Select all
[c]
@BEGIN_OF_SOURCE_CODE
/* @JUDGE_ID: 34712FH 100 C */
#include <stdio.h>
#include <stdlib.h>
unsigned int calCycLen( unsigned int );
/* function to calculate cycle length */
unsigned int calCycLen( unsigned int pos )
{
unsigned int lenCount = 1;
/* the given algorithm to calculate cycle length */
if( pos == 1 )
lenCount = 1;
else
{
while( pos != 1 )
{
if( pos % 2 == 1 )
{
pos = pos * 3 + 1;
lenCount++;
}
else
{
pos = pos / 2;
lenCount++;
}
}
}
return lenCount;
}
unsigned int main( void )
{
unsigned int i, j, pos, maxCycLen;
printf( "This program solves the Valladolid Programming Problem 100\n" );
printf( "There're several cases this program will exit:\n" );
printf( "One or both integers less than 0 or greater than 1,000,000.\n" );
printf( "The first integer is greater than the second integer.\n\n" );
printf( "Enter two integers between 0 and 1,000,000 ( seperated by a space ):\n" );
/* inputs are integer i and integer j */
scanf( "%d %d", &i, &j );
/* cases that the program will exit */
if( ( i < 0  i > 1000000 )  ( j < 0  j > 1000000 ) )
exit( EXIT_SUCCESS );
else if( i > j )
exit( EXIT_SUCCESS );
/* find the maximum cycle length */
for( pos = i; pos <= j; pos++ )
{
if( pos == i )
maxCycLen = calCycLen( pos );
else if ( maxCycLen >= calCycLen( pos ) )
maxCycLen = maxCycLen;
else
maxCycLen = calCycLen( pos );
}
/* outouts are integer i,integer j and integer maximum cycle length */
printf( "%d %d %d", i, j, maxCycLen );
getchar();
getchar();
return 0;
}
@END_OF_SOURCE_CODE
[/c]