100 - The 3n + 1 problem

Moderator: Board moderators

jricker
New poster
Posts: 4
Joined: Sat Oct 13, 2001 2:00 am
Contact:

100 - The 3n + 1 problem

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
New poster
Posts: 2
Joined: Wed Oct 31, 2001 2:00 am
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
New poster
Posts: 4
Joined: Sat Oct 13, 2001 2:00 am
Contact:
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
New poster
Posts: 2
Joined: Wed Oct 31, 2001 2:00 am
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
New poster
Posts: 4
Joined: Sat Oct 13, 2001 2:00 am
Contact:
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
New poster
Posts: 1
Joined: Mon Dec 31, 2001 2:00 am
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
New poster
Posts: 20
Joined: Wed Dec 26, 2001 2:00 am
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
New poster
Posts: 4
Joined: Sat Oct 13, 2001 2:00 am
Contact:
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
New poster
Posts: 13
Joined: Sat Feb 09, 2002 2:00 am

100 - Help submitting my first problem...

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
New poster
Posts: 13
Joined: Sat Feb 09, 2002 2:00 am
Just got accepted! Thanks for reading.
MegaS
New poster
Posts: 9
Joined: Tue Feb 05, 2002 2:00 am
Note that "between x and y" can be
from x to y (x<y) or form y to x (y<x)
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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
New poster
Posts: 5
Joined: Sun Apr 07, 2002 2:00 am
finally, my first successful submit
jimbob
New poster
Posts: 5
Joined: Mon Apr 29, 2002 5:16 am
Location: Greeley, CO

100, how does the input work?

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
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
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).