## 100 - The 3n + 1 problem

Moderator: Board moderators

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
Actually this is a Pascal source code

El-idioto
New poster
Posts: 45
Joined: Mon Jul 14, 2003 9:42 pm
Location: Zoetermeer, The Netherlands
See how unreadable this is? I didn't even notice at first glance

Livven
New poster
Posts: 1
Joined: Sat Aug 09, 2003 4:57 pm
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]
I can talk to a computer. I speak C.

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
The cycle length of 1 is 1, not 4. Just put the while on top instead of on the bottom, and it should be correct. =)

phire
New poster
Posts: 1
Joined: Sun Aug 10, 2003 7:55 pm

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

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
I also think so,
these people most probably know the judges input/output file.
There is a very popular thread which explains how it is possible to get the judges input file.
There are also some site that actualy has judge's data file.

Ivor
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia
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.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.

Karshikinpa
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:

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``````
[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]

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
For the last input, I got a different answer:

Code: Select all

``10 999999 525``

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:
In your solve() function, don't you think you need to also put +1 in the else part of if (n < PROB_MAX) ???

-turuthok-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

Karshikinpa
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]

oneirata
New poster
Posts: 3
Joined: Tue Aug 19, 2003 1:24 pm
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]
``````

oneirata
New poster
Posts: 3
Joined: Tue Aug 19, 2003 1:24 pm
I just changed all the %d to %u. I still got WA though. Did I get WA because of the exit?

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
First, you need to get rid of those four printf statements at the beginning of main(). Second, you need to have a while loop to read the entire input file, since the input file has many lines of numbers, and you're only looking at the first line.

oneirata
New poster
Posts: 3
Joined: Tue Aug 19, 2003 1:24 pm
thank you UFP2161. i'll keep trying.