100 - The 3n + 1 problem
Moderator: Board moderators
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>
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>
Actually it says, "All integers will be less than 10,000 and greater than 0.", so it should accept input up to 9999 right?On 2001-10-31 17:52, ali wrote:
fast, but
why restrict only until 1000, the problem input is for 10000,
Not sure what you are referring to. Do you mean that this input is possible:and please pay attention this problem can be accept not ordered input.
10 1
and if this is right then the output would according to the output instructions would be:
10 1 20
Joel
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
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
-
- 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>
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>
-
- 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);
}
_______________________________________________________________________________________________________________________________________
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);
}
_______________________________________________________________________________________________________________________________________
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?
-
- Guru
- Posts: 724
- Joined: Wed Dec 19, 2001 2:00 am
- Location: Germany
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;
}
#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;
}
-
- A great helper
- Posts: 284
- Joined: Thu Feb 28, 2002 2:00 am
- Location: Germany
- Contact: