100 - The 3n + 1 problem

[mf]

Ha! There's difference in problem description. If you look at website, they say input is between 1 and 999999 but if you check out pdf file the input is between 1 and 9999. I've downloaded pdf file and worked on it and that's why I get errors (I've assumed that max input is 9999 and in fact it is 999999). Where should I call this bug to? I've already written to them using "Contact us" panel, is it enough?

Yeah, that's a known bug, and unfortunately it hasn't yet been fixed for many years...

Basically, as judge's hardware was upgraded, the constraints of some problems (including this one) were raised, .html version and judge's input were adjusted (they're simple text files, so editing is easy), but nobody bothered fixing the .pdf versions (In the old version of judge's interface a few years ago we used to have a sticky note next to each problem, which mentioned the changes between .html and .pdf version, - that's why fixing the .ps and .pdf's was low priority back then)

I can only declare size of table equal 200000

I think memory limit is 32 Mb for (almost) every problem. Try to move the array out of the stack (make it global, static, or allocate dynamically with malloc), and then you shouldn't have any problems with its size.

[kcode]

Hi,
I am getting time limit exceeded for my solution,
but I think worst case (1 999999) is being computed in less than 3 sec.
Here is the code:

Code: Select all

#include <iostream>

using namespace std;

int main()
{
    int small;
    int big;
    int max;
    int n, len;
    register unsigned long long int x;
    int a;
    int b;

    while(1){
        cin >> a;
        cin >> b;
        if ( a < 0 || a > 1000000 || b < 0 || b > 1000000) continue;
        if (a == 0 || b == 0) continue;
        small = (a < b) ? a : b;
        big = (small == a) ? b : a; 
        max = 1;
    
        for (; small <= big; small++){
            x = small;
            len = 1;
            do{
                if (x % 2 == 0) x = x / 2;
                else x = (3 * x) + 1;
                len = len + 1;
            }while(x != 1);   
            
            if (len > max) max = len;
        }
        cout << a << " " << b << " " << max << endl;
    }
    return 0;
}

[mf]

Your program never terminates by itself, that's why it gets TLE.

Use 'while(cin >> a >> b)' or 'while (scanf("%d %d", &a, &b) == 2)' to read the input.

[kcode]

Now I am getting WA. Can't figure out the problem with the code!!
Please help.
(Code is pasted at 4th page, last reply)

Thanks

[Obaida]

Your code fails for this input:

Code: Select all

1 1

Output:

Code: Select all

1 1 1

Your output:

Code: Select all

1 1 4

[kcode]

Fixed the problem with case being 1 1.
Still getting WA...

[Obaida]

check your output for these also:
Input:

Code: Select all

1 2
1 3
1 4
2 2
2 3
2 1
3 1

[kcode]

Here is the output:

Code: Select all

1 2
1 2 4
1 3
1 3 8
1 4
1 4 8
2 2
2 2 2
2 3
2 3 8
2 1
2 1 4
3 1
3 1 8

[Obaida]

But my output is:

Code: Select all

1 2 2
1 3 8
1 4 8
2 2 2
2 3 8
2 1 2
3 1 8

[xiangyuyu]

Hello everyone, here is my code, a WA. It driving me mad
HELP!

Code: Select all

#include <iostream>

using namespace std;

int Cal(int& number) {
	if (1 == number) {
		return 1;
	} else if (0== (number % 2)) {
		number = number / 2;
	} else {
		number = 3 * number + 1;
	}
	return 0;
}
int CycleLength(int number) {
	int length = 0;
	while(1) {
		if (1 == Cal(number)) {
			length++;
			break;
		} else {
			length++;
		}
	}
	
	return length;
}

int main(int argc, char **argv)
{
	int min;
	int max;
	int maxlength = 1;
	cout << "Input the min number: " << endl;
	cin >> min;
	cout << "Input the max number: " << endl;
	cin >> max;

	bool convert = false;
	if (min > max) {
		convert = true;
		int temp = min;
		min = max;
		max = temp;
	}

	for( int i = min; i <= max; i++ ) {
		int tmp = CycleLength(i);
		maxlength = maxlength < tmp ? tmp : maxlength;
	}
	if(convert) {
  		cout << max << " " << min << " " << maxlength << endl;
	} else {
  		cout << min << " " << max << " " << maxlength << endl;
	}
	return 0;
}

[mf]

You are not supposed output garbage like "Input the min number: ", judge is only a dumb robot and won't appreciate that. Read the '"Output" section of problem statement and implement just exactly what it asks you to do, not more, not less.

The input contains not one, but several test cases. You need to process all of them.

Hi, can any one understand what is the problem with my code

feof is your problem. Check the return of value scanf instead.

[goinglee]

I do not know why my code is always WA when submission, could someoen help me, please?Thanks.
Below is my code:

#include <stdio.h>
#include <stdlib.h>
#define isInRange(x) (x>0 && x <1000000)
int process_problem(long input)
{
int number = 0;
while(input!=1)
{
number++;
if((input%2)==1)
input = input*3+1;
else
input = input/2;
}
/*if(input == 1)*/
number++;
return number;
}
int main()
{
long input_start=0, input_end=0; /*input pairs.*/
int cycle_length=0; /*output length.*/
int i=0,length=0;
/*freopen("100.in","r",stdin);*/
/*freopen("test.out","w",stdout);*/
while(!feof(stdin))
{
cycle_length = 0;
scanf("%d%d",&input_start,&input_end);
if(isInRange(input_start)&&isInRange(input_end))
{
if(input_start>input_end)
for(i = input_start ; i >= input_end ; i--)
{
length = process_problem(i);
if(cycle_length < length)
cycle_length = length;
}
else
for(i = input_start ; i <= input_end ; i++)
{
length = process_problem(i);
if(cycle_length < length)
cycle_length = length;
}
printf("%d %d %d", input_start, input_end, cycle_length);
printf("\n");
}
}
return 0;
}

[mf]

Don't ever use feof.
Check the return value of scanf instead.

[goinglee]

Don't ever use feof.
Check the return value of scanf instead.

I've got the right answer!!! The reason why I got failed is that I did not check the return value of scanf. Anyway, thank you very much.

[vizardo]

I got back Wrong Answer.. I'm not sure if it is that my code is wrong or there is sth wrong with java submission. Totally have no idea!

Code: Select all

import java.util.Scanner;

public class Main{
	
	public static long cycle_length(long num){
		long count = 1;
		
		while (num != 1){
			if (num%2 == 0){
				num = num / 2;
			}
			else{
				num = num * 3 + 1;
			}
			count++;
		}
		
		return count;
	}
	
	public static void main(String args[]){
		try{
			Scanner scanner = new Scanner(System.in);
			
			String str = scanner.nextLine();
			
			while (str != null && !str.equals("")){
				long i = Long.parseLong(str.split(" ")[0]);
				long j = Long.parseLong(str.split(" ")[1]);
				
				long a;
				long b;
				
				if (i < j){
					a = i;
					b = j;
				}
				else{
					a = j;
					b = i;
				}
				
				
				long max = 0;
				
				for (long k = a; k <= b; k++){
					long temp = cycle_length(k);
					if (max < temp){
						max = temp;
					}
				}
				
				System.out.println("" + i + " " + j + " " + max);
				
				str = scanner.nextLine();
			}
		}
		catch (Exception e){
			System.exit(0);
		}
	}
}