100 - The 3n + 1 problem

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

100 - The 3n + 1 problem

Post by jricker » Sat Oct 13, 2001 11:02 pm

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

Post by ali » Wed Oct 31, 2001 6:52 pm

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:

Post by jricker » Thu Nov 01, 2001 2:36 am

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

Post by ali » Thu Nov 01, 2001 8:43 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:

Post by jricker » Fri Nov 02, 2001 2:38 am

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

Post by PrometheusG » Mon Dec 31, 2001 9:44 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

Post by necropower » Fri Jan 11, 2002 5:51 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:

Post by jricker » Fri Jan 11, 2002 6:03 am

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

Post by edmanm » Sat Feb 09, 2002 1:14 am

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

Post by edmanm » Sat Feb 09, 2002 4:10 am

Just got accepted! Thanks for reading.

MegaS
New poster
Posts: 9
Joined: Tue Feb 05, 2002 2:00 am

Post by MegaS » Sun Feb 10, 2002 10:00 pm

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

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Mon Apr 15, 2002 4:26 pm

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

Post by jydy » Tue Apr 16, 2002 12:37 pm

thanks, Adrian!
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?

Post by jimbob » Mon Apr 29, 2002 5:21 am

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:

Post by Stefan Pochmann » Mon Apr 29, 2002 5:32 am

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

Post Reply

Return to “Volume 1 (100-199)”