## 100 - The 3n + 1 problem

Moderator: Board moderators

tellmewhy
New poster
Posts: 7
Joined: Tue Feb 07, 2006 7:30 pm
help again... can see wat wrong??

.....Life is just like a LM741........

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
just tell us the approach and maybe I can help, I don't like to debug other's code. By the way, for this problem you need to use DP or memorization or else it is easy to get tle. Also, if you want to do harder problems on uva, use c or c++. Java is prone to tle.

tellmewhy
New poster
Posts: 7
Joined: Tue Feb 07, 2006 7:30 pm
approach is simple.... juz read from input and plug them into the formula...

juz want to ask.. anyone got accepted using java for this problem?? juz want to know if there is a living soul who can do this problem..... i got the same problem when i'm solving 10014 too....
.....Life is just like a LM741........

tellmewhy
New poster
Posts: 7
Joined: Tue Feb 07, 2006 7:30 pm
haha.... 100 is solved liao.... juz realised that i forgort to check one of the limit.... thks ppl
.....Life is just like a LM741........

acMustaine
New poster
Posts: 2
Joined: Mon Jun 06, 2005 4:36 am

### 100 Runtime Error

I have proved my program with the test case 1 1000000 in Borland C++ 5.0... And i didn't get an error, but here i got RE... I haven't found a mistake yet, here is my code:

#include <fstream.h>
#include <stdlib.h>
#include <string.h>
#include <iostream.h>

#define ENTER '\n'
#define IN cin
#define OUT cout

// ifstream in("100.in");
// ofstream out("100.out");

unsigned long Numbers[1000000];
unsigned long A,B;

unsigned long Function(unsigned long A,unsigned long B) {
if(A > B) { unsigned long T = A; A = B; B = T; }

unsigned long D = 0,C,Cycle;

for(unsigned long i=A; i<=B; i++) {
if(!Numbers[i-1]) {
C = i;
Cycle = 1;

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

Numbers[i-1] = Cycle;
}

if(Numbers[i-1] > D) D = Numbers[i-1];
}

return D;
}

void main() {
char line[20];
Numbers[0] = 1;
while(1) {
IN.getline(line,sizeof(line));
if(!strcmp(line,"")) exit(0);

A = strtoul(strtok(line," "),NULL,10);
B = strtoul(strtok(NULL," "),NULL,10);

OUT << A << " " << B << " " << Function(A,B) << ENTER;
}
}

lovems
New poster
Posts: 1
Joined: Wed Mar 01, 2006 5:38 am
Location: KOREA,Kwang-ju

### 100 : help me i dont know why compile error

#include <stdio.h>

max_lengh(int a)
{
int count=1;
while(a !=1){
if( a%2 == 1)
a = a*3 +1;
else
a = a/2;
count += 1;
}a = count;
return a;
}

int main(void)
{
int a;
int o_a;
int b;
int count = 0;
int temp;
while(1)
{

scanf("%d",&a);

scanf("%d",&b);
/* swap if out of order */
if (b < a){
temp = a;
a = b;
b = temp;
}
o_a = a;

if( a >0 && a < 1000000 && b >0 && b < 1000000)
{
for (;a<b;a++){
if(count < max_lengh(a))
count = max_lengh(a);
}printf("%d %d %d\n",o_a,b,count);
count = 0;

}
}//end if

}

os : winxp
compiler : visual c

why this compile error??
i dont look at problem

sds1100
Learning poster
Posts: 95
Joined: Sat Dec 10, 2005 2:09 pm

### oh!

저도한국인입니다 -_- ;;
움.. 보자하니 int main 쓰 셨으매도 불구하고
return 0를 안쓰셨더군요 .
그리고 for(;j<=100;j++) 대충이런형태는
아마 컴파일에러날거같습니다 ;j<=부분떄문에요
움냐..
그거만 수정해주시면 될거같구요
제메일은 tjddlf202020@naver.com
이구. 이걸루 msn도합니다.

sds1100
Learning poster
Posts: 95
Joined: Sat Dec 10, 2005 2:09 pm
sorry

tmdrbs6584
Learning poster
Posts: 98
Joined: Sat Jan 21, 2006 12:45 pm
Location: Busan,Corea(Republic of)

### WHY WA?

#include<iostream.h>
int main(){
int n,v;
while(cin >> n >> v){
int max=0;
int i;
if(v>=n){
for(i=v;i<=n;i++){
int m=i;
int cnt=0;
while(1){
cnt++;
if(m==1) break;
if(m%2==1) m=3*m+1;
else m/=2;
}
if(cnt>max) max=cnt;
}
cout << n << " " << v << " " << max << endl;
}
else{
for(i=v;i<=n;i++){
int m=i;
int cnt=0;
while(1){
cnt++;
if(m==1) break;
if(m%2==1) m=3*m+1;
else m/=2;
}
if(cnt>max) max=cnt;
}
cout << n << " " << v << " " << max << endl;
}
}
return 0;
}

tmdrbs6584
Learning poster
Posts: 98
Joined: Sat Jan 21, 2006 12:45 pm
Location: Busan,Corea(Republic of)
I'm going CRAZY!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore
Which problem is this?

From your code, it looks like it's for problem 100.

This part of your code is wrong:

Code: Select all

``````if(v>=n){
for(i=v;i<=n;i++){
int m=i;
int cnt=0;
while(1){
cnt++;
if(m==1) break;
if(m%2==1) m=3*m+1;
else m/=2;
}
``````
If v >= n then you are going to have an infinite loop there since you loop from v to n. It should be from n to v. Alternatively just swap the values in and v and loop from v to n.

TailDrag
New poster
Posts: 2
Joined: Fri Mar 10, 2006 1:27 am
The only problem I have is a presentation error. I believe the error is an extra end line at the very end. The code is in C++ and all the outputs are as follows:

cout << i << " " << j << " " << max;

if(cin)
{
cout << endl;
}

The if statement is checked at the end of my while loop, after i and j are updated. The stream should fail at the end of file, and there should not be an end line after the last output (at least this is how I think it should be). Is the problem supposed to have and end line after every output? If so that is an easy fix, but if not, a little help to figure out a new method to limit it would be appreciated.

TailDrag
New poster
Posts: 2
Joined: Fri Mar 10, 2006 1:27 am
Nevermind, just submitted the code with only

cout << i << " " << j << " " << max << endl;

and it got accepted.

Ice-Eight
New poster
Posts: 2
Joined: Mon Mar 13, 2006 5:06 am

### Compile Error

Hi, I'm new to UVa, and I just submitted my solution to the first problem.
I get a compile error, but I'm not sure what the problem is.

Code: Select all

``````//100: The 3n+1 Problem

#include <iostream>
using namespace std;

int process(int m) {
int n = 1;
while(m != 1) {
n++;
if (m % 2 == 1) m = 3 * m + 1;
else m /= 2;
}
return n;
}

int main() {
int m, n;
while(scanf("%d %d", &m, &n) == 2) {
int max = 0;
int m1 = m;
int n1 = n;
if (m > n) {
m = n1;
n = m1;
}
while(m <= n) {
int r;
r = process(m);
if (r > max) max = r;
m++;
}
cout << m1 << " " << n1 << " " << max << endl;
}
}``````
If anyone could help me out, I would greatly appreciate it

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore
To use scanf, #include <cstdio>