100 - The 3n + 1 problem

[tellmewhy]

help again... can see wat wrong??

[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]

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

[tellmewhy]

haha.... 100 is solved liao.... juz realised that i forgort to check one of the limit.... thks ppl

[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;
}
}

Code: Select all

[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

[sds1100]

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

[sds1100]

sorry
i can't your program miss

[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]

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

[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]

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]

Nevermind, just submitted the code with only

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

and it got accepted.

[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

[chunyi81]

To use scanf, #include <cstdio>