100 - The 3n + 1 problem

[Ardeshir81]

Thank You @brianfry713
BUT when I did that I get another problem.
When I check "My Submissions" it says "running" and after a while it writes : "Submission Error"
This is the modified code :

Code: Select all

//All input integers will be less than 1,000,000 and greater than 0 .
//There will be 2 inputs , i and j , for all integers from i to j we should get the Cycle-Length of '3n + 1' formula and return the maximum .

#include <iostream>

using std :: cout ;
using std :: cin ;
using std :: endl ;

int main ()
{
    int i , j , CL = 1 , maxCL , tmp ; //CL is the Cycle-Length of the current number and maxCL is the maximum Cycle-Length and tmp is the temporary number which the operation will be done on .
    cin >> i >> j ;
    while (i > 0 && j > 0)
    {
        cout << i << " " << j << " " ; //We do not use an extra variable for numbers between i and j , we use the i itself in the for loop , so we'll lose the i at the end of the program .
        if (i > j)
        {
            int swapij ;
            swapij = i ;
            i = j ;
            j = swapij ;
        }
        maxCL = 0 ;
        for ( ; i <= j ; i ++)
        {
            tmp = i ;
            while (tmp > 1)
                if (tmp %2 == 0)
                {
                    tmp /= 2 ;
                    CL ++ ;
                }
                else
                {
                    tmp = tmp * 3 + 1 ;
                    CL ++ ;
                }
            if (CL > maxCL)
            maxCL = CL ;
            CL = 1 ;
        }
        cout << maxCL << endl ;
        cin >> i >> j ;
    }
    return 0 ;
}

THNX

[brianfry713]

Your code doesn't terminate. Instead try something like:
while(cin >> i >> j) {

[Ardeshir81]

THANK YOU!
It's accepted.
BUT how the problem describes algorithms is different from what it wants.
In the book it didn't say something like "cin >>I >> j" , so me (and probably most begginers) think they should just get two inputs and terminate the program.

[brianfry713]

The Input

The input will consist of a series of pairs of integers i and j, one pair of integers per line. All integers will be less than 1,000,000 and greater than 0.

You should process all pairs of integers and for each pair determine the maximum cycle length over all integers between and including i and j.

You can assume that no operation overflows a 32-bit integer.

The Output

For each pair of input integers i and j you should output i, j, and the maximum cycle length for integers between and including i and j. These three numbers should be separated by at least one space with all three numbers on one line and with one line of output for each line of input. The integers i and j must appear in the output in the same order in which they appeared in the input and should be followed by the maximum cycle length (on the same line).

Sample Input

1 10
100 200
201 210
900 1000

Sample Output

1 10 20
100 200 125
201 210 89
900 1000 174

[dreign]

Can anyone help me with optimization ,I keep getting time limited exceeded?
my code is below :

#include<stdio.h>
long A[1000001];
long barr(long n)
{
if(n==1)
return 1;

if (n<1000001)
{
if (A[n]!=0)
return (A[n]);
else
{
long k;
k=n%2 ? (3*n+1) : n/2 ;
A[n]=1+barr(k);
return(A[n]);
}
}
else
{
long k;
k=n%2 ? (3*n+1) : n/2 ;
return(1+barr(k));
}
}

int main()
{
long maxi=1;
long a,b;
while(scanf("%ld%ld",&a,&b))
{
maxi=1;
long a1,a2;
if(a>b){
a1=b;
a2=a;
}
else
{
a1=a;
a2=b;
}
for (long i=a1;i<=a2;i++)
{
long damn;
damn=barr(i);
if(damn>maxi)
{
maxi=damn;
}
}
printf("%ld %ld %ld\n",a,b,maxi);
}
}

[brianfry713]

Try solving it without recursion. You can see an AC code at:
http://uva.onlinejudge.org/data/p100.c.html

[SifatRuet12]

why does this code show compile error.I'm running it succesfully in codeblocks.


#include<stdio.h>
int m_cycle_len(int n)
{
int cnt=0;
while(1)
{
if(n==1){
cnt++;
break;
}
else if(n%2==0){
cnt++;
n=n/2;
}
else if(n%2==1){
cnt++;
n=n*3+1;}

}
return cnt;

}

int main()
{ unsigned int a,k,i,j,m;

while(scanf("%u %u",&j,&k)){
m=0;
for(i=j;i<=k;i++){
a=m_cycle_len(i);
if(a>m)
m=a;
}
printf("%u %u %u\n",j,k,m);
}
return 0;
}

[brianfry713]

You can click my submissions to see the reason for a compile error.

Also change:
while(scanf("%u %u",&j,&k)){
to:
while(scanf("%u %u",&j,&k) == 2){

And consider what would happen if i > j

[SifatRuet12]

Thank u for ur suggestion,accepted. @ Brianfry713

[JimE]

I have been trying this problem ad nauseum using Pascal, my preferred language. I eventually gave up and copied the sample C code given and it worked, off course. I then tried the sample Pascal answer and it failed!!!!!!!

Can any one verify that Pascal as a language works?? I use Delphi and it worked on anything I could throw at it. However using that code results in various errors at compilation, time outs, run time errors, wrong answers , etc.

Very frustrating. I might have to go back to C/C++ or give this site a miss.

Jim

If anyone is interested, here is my Delphi code.:

program UVA100(input, output);
{$APPTYPE CONSOLE}
uses
SysUtils;
const
MAX_CYCLE = 10000;
var
idx : Integer;
carray : array[1..MAX_CYCLE] of integer;
procedure Solve;
var
v : Int64;
i,j,n,
lval, hval,
cycle,
maxcycle : Integer;

begin
{$DEFINE ONLINE_JUDGE}
{$IFNDEF ONLINE_JUDGE}
assign(input, 'input.txt');
reset(input);
assign(output, 'output.txt');
rewrite(output);
while NOT Eof(input) do
{$ELSE}
while NOT Eof do
{$ENDIF}
begin
ReadLn(i,j);
maxcycle := 0;
Write(i,' ',j);
if i > j then
begin
lval := j;
hval := i;
end
else
begin
lval := i;
hval := j;
end;
for n:= lval to hval do
begin
cycle := 1;
v := n;
while v > 1 do
begin
if v <= MAX_CYCLE then //it might be in array
begin
if carray[v] > 0 then //we have it cached
begin
cycle := cycle + carray[v] - 1;
break; //all done
end;
end;
if (v mod 2) = 1 then
v := 3*v + 1
else
v := v div 2;
cycle := cycle + 1;
end;
if (n <= MAX_CYCLE) AND (carray[n] = 0) then
carray[n] := cycle ;

if cycle > maxcycle then
maxcycle := cycle;
end;
WriteLn(' ',maxcycle);
end;
{$IFNDEF ONLINE_JUDGE}
close(input);
close(output);
{$ENDIF}
end;
begin
for idx := 1 to MAX_CYCLE do
carray[idx] := 0;
Solve;
end.

[ProgramGuruCpp]

I, too, have submitted seemingly correct code, only to receive Wrong Answer

I am using C++ and I am certain my code works fine, but I am curious as to why some people approach it differently.
Mainly, I see many programs use classes to solve the problem, but why? How does that approach differ from others that do not use classes (i.e. my code)?

Here's my code:

Code: Select all

#include <iostream>

int algorithm(unsigned long n)
{
	int cycleLength = 1;
	while (n != 1)
	{
		if (n%2 == 1)
		{
			n = 3*n + 1;
		}
		else
		{
			n /= 2;
		}
		cycleLength++;
	}
	return cycleLength;
}

int main()
{
	unsigned long i, j;
	int result;
	int highest = 1;
	bool swap = false;
	
	while(std::cin >> i >> j)
	{
		if (i > j)
		{
			int temp = j;
			j = i;
			i = temp;
			swap = true;
		}
		
		for (int temp = i; j > temp; temp++)
		{
			result = algorithm(temp);
			if (result > highest)
			{
				highest = result;
			}
		}
		if (!swap)
		{
			std::cout << i << " " << j << " " << highest << "\n";
		}
		else
		{
			std::cout << j << " " << i << " " << highest << "\n";
		}
	}
	return 0;
}

[vincaslt]

I'm having WA in Pascal, even though I seem to pass any test I make myself... Tried switching starting values, tried giving huge values, but still, it works just fine. I ran tests other people gave, and it ACed them all, so I think it might have something to do with the way I output data, is it correct? Here's the code:

Code: Select all

program UVA100;
    { Cache for storing known cycle count data. }
    var Cache : array [1..999999] of Int64;

    {
        Returns the higher of two values
    }
    function GetMax(A : Int64; B : Int64) : Int64;
    begin
        if A > B then GetMax := A else GetMax := B;
    end;

    {
        Returns the lower of two values
    }
    function GetMin(A : Int64; B : Int64) : Int64;
    begin
        if A < B then GetMin := A else GetMin := B;
    end;

    {
        Checks whether the number is even, and
        returns True if it is.
    }
    function IsEven(N : Int64) : Boolean;
    begin
        IsEven := False;
        if N mod 2 = 0 then
            IsEven := True;
    end;

    {
        Returns the next value according to the algorithm.
        If number is even: divides by 2,
        if number is odd: returns 3n + 1.
    }
    function GetNext(N : Int64) : Int64;
    begin
        if IsEven(N) then
            GetNext := N div 2
        else
            GetNext := N * 3 + 1;
    end;

    {
        Gets algorithm cycles count for a specified number.
    }
    function GetCyclesCount(T : Int64) : Int64;
    begin
        { Only cache values which will be used in other iterations. }
        if (T < 1000000) and (Cache[T] > 0) then
            { Get value from cache. }
            GetCyclesCount := Cache[T]
        else begin
            { Get the result through iteration }
            GetCyclesCount := 1 + GetCyclesCount(GetNext(T));
            { If value can be used in later iterations, cache the value. }
            if T < 1000000 then Cache[T] := GetCyclesCount;
        end;
   	end;

	var Min, Max : Int64; // Boundaries.
        I : Int64; // Dummy variable for calculating.
        MaxCyclesCount : Int64; // Maximum count of cycles, result.

begin
    { Set the value that would stop iterations. }
    Cache[1] := 1;
    { While there is data to fetch. }
    While not EOF do begin
        { Read values from input. }
        Read(Min, Max);
        { Reset max cycles count for every algorithm iteration. }
        MaxCyclesCount := 0;

        { Execute algorithm for every value in range, also swap values,
        if they are in wrong order. }
        for I := GetMin(Min, Max) to GetMax(Min, Max) do begin
            { Check if the new cycles count is the highest yet. }
            MaxCyclesCount := GetMax(MaxCyclesCount, GetCyclesCount(I));
        end;

        { Output the result. }
        WriteLn(Min, ' ', Max, ' ', MaxCyclesCount);
	end;
end.

[brianfry713]

ProgramGuruCpp, your code doesn't match the sample I/O.

[zeroproto]

Hi, this is my first question here so i'm still trying to get the form/correct way of writing code for it to be accepted to bear with me.
The problem is that the judge keeps returning a runtime error with the only information that i should exit my code correctly, and i have no idea what that means since there is no such thing in the java sample code. Here is my code

Code: Select all

import java.io.*;
import java.util.*;
class Bridge {
	static void func (int i, int j)
	{ 	
		int max=-999; int x;
		int change=1;
		if(i>j)
			change=-1;
		for(int k=i; k-1!=j; k+=change)
		{
			int count=1;
			x=k;
			while(x!=1)
			{
				if(x%2==0)
				{
					x=x/2;
				}
				else
				{
					x=3*x+1;
				}
				//System.out.print(x+" ");
				count++;
				
				if(count>max)
					max=count;
			}
			//System.out.println("\n count is "+count);
		}
		
		System.out.println(i+" "+j+" "+max);
	}
	void begin()
	{
		//Scanner scan = new Scanner(System.in);
		Scanner scan = new Scanner(new BufferedInputStream(System.in));
		int i = scan.nextInt();
		scan = new Scanner(System.in); 
		int j = scan.nextInt();
		
		func(i,j);	
	}
	public static void main (String args[])
	{
		Bridge mywork = new Bridge();
		mywork.begin();
	}
}

I tried to make it as simillar to the sample code as possible, with the obvious exceptions of using Scanner input, and the different logic. It runs in the IDE perfectly and works properly on all the test cases and it doesn't matter which input is larger than the other. I've tried messing with the code to get it accepted but nomatter what i do, it always gets me a runtime error. what's the problem here?

[brianfry713]

Use class Main.

See: http://uva.onlinejudge.org/index.php?op ... &Itemid=30