100 - The 3n + 1 problem

[jricker]

Hi all,

I've put together my own version of Problem 100 but its in PHP at the moment so I can't quite submit it yet until I convert it to Pascal but would love to hear some feedback on its execution:

http://www.justthefaqs.org/new/hailstones.php

Note: Large gaps between i and j will result in a long wait. Please be patient.

Thanks
Joel

<font size=-1>[ This Message was edited by: jricker on 2001-10-13 23:04 ]</font>

[ali]

fast, but
why restrict only until 1000, the problem input is for 10000,
and please pay attention this problem can be accept not ordered input.

regards,

ali

[jricker]

On 2001-10-31 17:52, ali wrote:
fast, but
why restrict only until 1000, the problem input is for 10000,

Actually it says, "All integers will be less than 10,000 and greater than 0.", so it should accept input up to 9999 right?

and please pay attention this problem can be accept not ordered input.

Not sure what you are referring to. Do you mean that this input is possible:

10 1

and if this is right then the output would according to the output instructions would be:

10 1 20

Joel

[ali]

Actually it says, "All integers will be less than 10,000 and greater than 0.", so it should accept input up to 9999 right?

you are right.

Not sure what you are referring to. Do you mean that this input is possible:

10 1

and if this is right then the output would according to the output instructions would be:

10 1 20

Joel

yes that is possible. and your output is correct.

ali

[jricker]

Hoohoo...

I recently learned enough C++ to be dangerous and submitted my solution to P100:

"Your C++ program has solved Ok the problem 100 (The 3n + 1 problem)
in 0.050 seconds with low memory spent.
Congratulations!"

Yea!

Thanks for the help regarding the handling of reverse input integers.

Joel

[PrometheusG]

I don't get it...
I got this one accepted many moons ago.
I rewrote it to use recursion, just to fool around, and now its not getting accepted! I've tried it on lots of test input and it gives me all the same answers as the one that got accepted...WHAT'S GOING ON?!?!?!

Here's the code:

const int MAXSIZE = 9999;
int array[MAXSIZE] = {0, 1};
int findNum(int n);

inline void SWAP(int &a, int &b, int &c)
{a^=b; b^=a; a^=b; c++;}

int main()
{
int first, second, max, swapped;
register int i;

for(i = MAXSIZE; i >= MAXSIZE / 2; i--)
findNum(i);

while(scanf("%d %d", &first, &second) == 2)
{
max = swapped = 0;

if (second < first)
SWAP(first, second, swapped);

for(i = second; i >= first; i--)
if (array > max)
max = array;

swapped
?printf("%d %d %dn", second, first, max)
:printf("%d %d %dn", first, second,max);
}

return 0;
}

int findNum(int n)
{
int num = 0;

while(n > MAXSIZE && ++num)
n % 2 ? n = 3 * n + 1 : n /= 2;

!array[n]
? n % 2
? array[n] = findNum(3 * n + 1) + 1
: array[n] = findNum(n / 2) + 1
:0;

return array[n] + num;
}

I'm guessing it has something to do with the recursion, but I can't see what the problem might be. Like I said, I've tried it on many, many test cases and I've always gotten the right answer. I thought it might be an OS thing, but it runs perfectly on Win98 and Linux.

Someone PLEASE tell me what I'm doing wrong!
I need help.

<font size=-1>[ This Message was edited by: PrometheusG on 2001-12-31 09:09 ]</font>

[necropower]

guys, i dont know what is wrong with this code of mine, could u help me ????
i tested it in all possible ways but i dont know WHY THE HECK it isnt working.. i guess i am not putting in the right output way, could u guys tell me whats wrong with it?
yje judge says that my answer is wrong, but i doubt it


____________________________________________________________________________________________________________________________________________________________________________________
#include <stdio.h>

main()
{
unsigned int flag,i,minimo, maximo, temp , maior, vetor[1000000];

flag = 0;
maior = 0;
scanf("%d",&minimo);
scanf("%d",&maximo);
if (minimo > maximo)
{
temp = maximo;
maximo = minimo;
minimo = temp;
flag = 1;
}

temp = i = minimo;

for(i = minimo ; i < (maximo + 1 ) ; i++)
{
for(temp = i ; temp != 1 ; )
{
if ((temp < 1000000)&&(vetor[temp] != 0 ))
{
vetor = vetor[temp] + vetor - 1;
temp = 1;
}
else
{
vetor = vetor + 1;
if ((temp % 2) != 0)
{
temp = (3 * temp) + 1;
}

else
temp = temp / 2;
}
}
vetor = vetor + 1;
if (vetor > maior)
maior = vetor;
}
if (flag == 0)
printf("%d %d %d n",minimo,maximo,maior);
else
printf("%d %d %d n",maximo,minimo,maior);

}

_______________________________________________________________________________________________________________________________________

[jricker]

I haven't actually dug into your logic to see if that works but at first glance, you need to be repeating your input until an EOF has been triggered.

Hope that helps,
Joel

[edmanm]

Okay, I started off on problem 100 and thought I had it solved pretty quickly. Using the sample input given on the problem page, I ran the program on my machine and it arrived at the same output listed in the Sample Output. Unfortunately, when I submitted it, the judge says I have a "wrong answer". Can anybody offer any tips?

[edmanm]

Just got accepted! Thanks for reading.

[MegaS]

Note that "between x and y" can be
from x to y (x<y) or form y to x (y<x)

[Adrian Kuegel]

There is no line in the problem description that describes the order in which min and max are given. You should swap the values if min>max.

[jydy]

thanks, Adrian!
finally, my first successful submit

[jimbob]

I'm having problems understanding how the judge enters input data. Specifically, I wrote the following to take two integers from standard input like '1<space>10<cr>', then it outputs the answer like '1<space>10<space>20<cr>'. What is the problem? Thank you for your help!

#include <iostream.h>

int cycles(int n)
{
int counter = 0;

while( n != 1)
{
if(n % 2 == 0)
n = n / 2;
else
n = n * 3 + 1;

counter++;
}

return counter + 1;
}


int main()
{
int i, j, cycle_count = 0;

cin >> i >> j;

for(int l = i;l <= j; l++)
{
int cycle_hold = 0;
cycle_hold = cycles(l);

if(cycle_hold > cycle_count)
cycle_count = cycle_hold;
}

cout << i << ' ' << j << ' ' << cycle_count << endl;

return 0;
}

[Stefan Pochmann]

Next time please give some info about the result you get. I believe you don't have problems understanding the input or output, that part looks good. I assume you get a wrong answer and refer you to my web page where you'll find a hint (at the bottom of the page).