100 - The 3n + 1 problem

[zobayer]

You are resizing vector depending on 'a' but this is a very bad idea, because, in the ackermann sequence, a can grow very large. The number of terms might be small, but individual element can be very large even you start from a small one. Allocating so much memory is not possible most of the time, moreover you have declared your vector in main() function. Even if you have declared it in global space, still the problems remains, see, you have defined 'a' to be long long, so, you have suspected 'a' might be that big, then how could you dare to resize vector on 'a'.

Though memoization is not needed here, if you still want to do so, you can use the vector depending on the number of elements in the sequence, not by any specific element.

However, after correcting this, you will probably get Wrong Answer.

[bollu]

Please anyone help me.I getting WA.But my output has no problem.
#include<stdio.h>
long int task(long long int m)
{ int c=1;
do
{
if(m%2==1)
m=(3*m)+1;
else
m=m/2;
c++;
}while(m!=1);
c++;
return c;
}
int main()
{
long long int x,y,i,j,m,n,b,max=0;
long int task(long long int m);
while(scanf("%lld %lld",&x,&y)==2)
{ if(x<y)
{
i=x;j=y;
}
else
{
i=y;j=x;
}
for(m=i;m<=j;m++)
{
n=task(m);
if(max<n)
max=n;
}
printf("%lld %lld %lld\n",i,j,max);
max=0;
}
return 0;
}

[helloneo]

This may help..

http://acm.uva.es/board/viewtopic.php?f ... =15#p95469

[rezatorabi]

Hi, Sorry, I am new, so don't blame me for my question if it is stupid.
Here is a problem: http://uva.onlinejudge.org/index.php?op ... problem=36
It hasn't said that it is going to give us the number of inputs at first! so how should I handle the input. I used hasNextInt() but got time limit.

Thanks in Advance for Your Help...

public class Main {

public static void main(String[] args) {
int a,b,x,max=0,count;
Scanner in = new Scanner(System.in);
while(in.hasNextInt())
{
a = in.nextInt();
b = in.nextInt();
max = 0;
count = 1;
for(int i=a;i<=b;i++)
{
x=i;
count = 1;
while(true)
{
if(x == 1)
break;
if(x%2 == 0)
x = x/2;
else
x = 3*x+1;
count++;
}
if(count>max)
max = count;
}
System.out.println(a+" "+b+" "+max);

}
}

}

[sohel]

Are you sure you are getting TLE?

I added the "java.util.Scanner" header file to your code and it gets wrong answer.
Your approach for reading input is correct. Look at other threads related to problem #100 and you will find the reason for getting WA.

[rezatorabi]

Thanks sohel
You are right. It is WA.
But I can't understand what is wrong. Would you please give me the test case which you say it gives wrong answer.
It's is the final code:

import java.util.Scanner;

/**
*
* @author Reza
*/
public class Main {

public static void main(String[] args) {
// TODO code application logic here
int a,b,x,max=0,count,j,k;
Scanner in = new Scanner(System.in);
while(in.hasNext())
{
a = in.nextInt();
b = in.nextInt();
max = 0;
count = 1;
if(a>b)
{
k=a;
j=b;
}
else
{
k=b;
j=a;
}
for(int i=j;i<=k;i++)
{
x=i;
count = 1;
while(true)
{
if(x == 1)
break;
if(x%2 == 0)
x = x/2;
else
x = 3*x+1;
count++;
}
if(count>max)
max = count;
}
System.out.print(a+" "+b+" "+max);
}
}
}

[rezatorabi]

Solved!!

Thanks...

[jfvs]

Does anyone knows why Im getting WA with this code?

Code: Select all

#include <cstdio>
#include <map>

using namespace std;
map<int, int> mp;

int rec(int i){
	if(i == 1){
		return 1;
	}else if(mp.find(i) != mp.end()){
		return mp[i];
	}else {
		mp[i] = (i % 2 == 0)? rec(i / 2) + 1 : rec((3 * i) + 1) + 1;
		return mp[i];
	}
}

int calc(int n, int m){
	int max = -1;
	for(int i = n; i <= m; i++){
		if(mp.find(i) == mp.end()){
			mp[i] = rec(i);
		}
		max = (max < mp[i])? mp[i] : max;
	}
	return max;
}

int main(){
	int n = 0, m = 0;
	while(scanf("%d %d", &n, &m) != EOF){
		bool grater = false;
		grater = (n > m)? true : false;
		if(!grater)
			printf("%d %d %d\n", n, m, calc(n, m));
		else
			printf("%d %d %d\n", n, m, calc(m, n));
	}
	return 0;
}

thanks in advance

[fesoliveira]

there is my code:

Code: Select all

#include <stdio.h>
#include <stdlib.h>

main() {

    int x, y, j, temp, big, diff, n, i=0, cycles[100000];

    scanf("%d %d", &x, &y);

    if (!((x==1) && (x==y))) {


    if (x<y) {

    j = x;

    do {

        cycles[i] = func(j);
        i++;
        j++;

    }  while(j<=y);

    big = cycles[0];
    diff = y - x;

    for(n=0; n<diff; n++) {

        if (big<cycles[n])
            big = cycles[n];

    }

    printf("%d %d %d", x, y, big);

    }

    if (x>y) {

            temp = x;
            x = y;
            y = temp;




            j = x;

    do {

        cycles[i] = func(j);
        i++;
        j++;

    }  while(j<=y);

    big = cycles[0];
    diff = y - x;

    for(n=0; n<diff; n++) {

        if (big<cycles[n])
            big = cycles[n];
        }

        temp = x;
        x = y;
        y = temp;

    printf("%d %d %d", x, y, big);

    }

    if ((x!=1) && (x == y)) {

        j = x;

    do {

        cycles[i] = func(j);
        i++;
        j++;

    }  while(j<=y);

    big = cycles[0];
    diff = y - x;

    for(n=0; n<diff; n++) {

        if (big<cycles[n])
            big = cycles[n];

    }

    printf("%d %d %d", x, y, big);
    }
    }else {
        big = 1;
        printf("%d %d %d", x, y, big); }


    return 0;

    }






int func(i) {

    int k = 1;

    do {

        if (i%2){ i = 3*i + 1; }

        else { i = i/2;; }

        k++;

        if (i==1) { break; }

    } while(1);

        return k;

}

it return the reuslts as they want, but i keep getting WA... somenone?

[fesoliveira]

take a look at my code...

Code: Select all

#include <stdio.h>
#include <stdlib.h>

main() {

    int x, y, j, temp, big, diff, n, i=0, cycles[100000];
    int func(i);

    scanf("%d %d", &x, &y);

    if (!((x==1) && (x==y))) {


    if (x<y) {

    j = x;

    do {

        cycles[i] = func(j);
        i++;
        j++;

    }  while(j<=y);

    big = cycles[0];
    diff = y - x;

    for(n=0; n<diff; n++) {

        if (big<cycles[n])
            big = cycles[n];

    }

    printf("%d %d %d", x, y, big);

    }

    if (x>y) {

            temp = x;
            x = y;
            y = temp;




            j = x;

    do {

        cycles[i] = func(j);
        i++;
        j++;

    }  while(j<=y);

    big = cycles[0];
    diff = y - x;

    for(n=0; n<diff; n++) {

        if (big<cycles[n])
            big = cycles[n];
        }

        temp = x;
        x = y;
        y = temp;

    printf("%d %d %d", x, y, big);

    }

    if ((x!=1) && (x == y)) {

        j = x;

    do {

        cycles[i] = func(j);
        i++;
        j++;

    }  while(j<=y);

    big = cycles[0];
    diff = y - x;

    for(n=0; n<diff; n++) {

        if (big<cycles[n])
            big = cycles[n];

    }

    printf("%d %d %d", x, y, big);
    }
    }else {
        big = 1;
        printf("%d %d %d", x, y, big); }


    return 0;

    }






int func(i) {

    int k = 1;

    do {

        if (i%2){ i = 3*i + 1; }

        else { i = i/2;; }

        k++;

        if (i==1) { break; }

    } while(1);

        return k;

}

any hints why doesnt it works?

[Logaff]

hello, i tried to solve the first problem but i always get "wrong answer" but i dont know why. can anybody give me a short advice

Code: Select all

import java.io.*;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        long i = sc.nextInt();
        long t1 = i;
        long j = sc.nextInt();
        long t2 = j;
        if (i > j) {
            long c1 = i;
            long c2 = j;
            i = c2;
            j = c1;
        }
        long lleng = 0;
        for (long a = i; a <= j; a++) {
            long leng = 0;
            long n = a;
            while (n != 1) {
                leng++;
                if (n % 2 == 0) {
                    n = n / 2;
                } else {
                    n = 3 * n + 1;
                }
            }
            leng = leng + 1;
            if (leng > lleng) {
                lleng = leng;
            }
        }
        if (t1 < t2) {
            System.out.println(i + " " + j + " " + lleng);
        } else {
            System.out.println(j + " " + i + " " + lleng);
        }
    }
}

i get the same output like the given samples.

[jfvs]

first, I dont know if java can do it in time... and why are you doing this?

Code: Select all

long i = sc.nextInt();

use the sc.nextLong();

and at the end, you are doing this:

Code: Select all

         if (t1 < t2) {
            System.out.println(i + " " + j + " " + lleng);
        } else {
            System.out.println(j + " " + i + " " + lleng);
        }

try this instead

Code: Select all

System.out.println(t1 + " " + t2 + " " + lleng );

hope this helps

[Logaff]

thanks...but i get "wrong answer" again -.- i sucks really ....

[jfvs]

I just noticed something...

you just do the program so it would compute just 1 result, do it for multiple input, the uva test case file is very long, no just one line...

hope this helps

[Logaff]

do you mean that i should after the output was given ask for an other input? so like a while control structure?

edit: now i get a runtime error :-p