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

tellmewhy
New poster
Posts: 7
Joined: Tue Feb 07, 2006 7:30 pm

Post by tellmewhy »

help again... can see wat wrong??

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

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo »

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

Post by tellmewhy »

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

Post by tellmewhy »

haha.... 100 is solved liao.... juz realised that i forgort to check one of the limit.... thks ppl :lol:
.....Life is just like a LM741........

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

100 Runtime Error

Post by acMustaine »

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

Post by lovems »

#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
I need your help.

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

oh!

Post by sds1100 »

저도한국인입니다 -_- ;;
움.. 보자하니 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

Post by sds1100 »

sorry
i can't your program miss

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

WHY WA?

Post by tmdrbs6584 »

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

Post by tmdrbs6584 »

I'm going CRAZY!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 »

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

Post by TailDrag »

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

Post by TailDrag »

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

Post by Ice-Eight »

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 :D

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 »

To use scanf, #include <cstdio>

Post Reply

Return to “Volume 1 (100-199)”