100 - The 3n + 1 problem

[Krzysztof Duleba]

Actually this is a Pascal source code

[El-idioto]

See how unreadable this is? I didn't even notice at first glance

[Livven]

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]

[UFP2161]

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]

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]

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]

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.

[Karshikinpa]

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]

For the last input, I got a different answer:

Code: Select all

10 999999 525

[turuthok]

In your solve() function, don't you think you need to also put +1 in the else part of if (n < PROB_MAX) ???

-turuthok-

[Karshikinpa]

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]

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]

I just changed all the %d to %u. I still got WA though. Did I get WA because of the exit?

[UFP2161]

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]

thank you UFP2161. i'll keep trying.