100 - The 3n + 1 problem

[wmqwj]

HI, passworder

In your algorithm, you assumed that i < j , and that's not correct
input might look like this:

Code: Select all

 20 1 

in this case .. your algorithm fails...
try to swap the input to match your algorithm, but remember when you write the answer
write the input in the same order you took it,
and you'll get AC

Input

Code: Select all

1 10
100 200
201 210
900 1000
1000 900

Output

Code: Select all

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

Good Luck,

[rajib_sust]

u r code fail when i > j also make wrong answer for long data
it make overflow for int that why give wrong output

[nFec]

Hi there,

I am trying to submit this problem the whole day.
All of my local testing goes very well, no exceptions no problems.

The first times I tried to submit i got Runtime Errors, when I catched all exceptions I naturally got Wrong Answer cause at least one case didn't get handled.

So here's my code:

Code: Select all

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) {
		
		long[] currentNumbers = new long[2];
		BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
			
			try {
				while(stdin.ready()) {
					String[] stringNumbers = stdin.readLine().split(" ");
					currentNumbers[0] = Long.parseLong(stringNumbers[0]);
					currentNumbers[1] = Long.parseLong(stringNumbers[1]);
					long longestcycle = calculateLongestCycle(currentNumbers);
					System.out.println(currentNumbers[0] + " " + currentNumbers[1] + " " + longestcycle);
				}
			} catch (NumberFormatException e) {
				System.exit(1);
			} catch (IOException e) {
				System.exit(1);
			} catch (Exception ex) {
				System.exit(1);
			}
		System.exit(0);
	}

	private static long calculateLongestCycle(long[] numbers) {
		long longest = 1;
		for(long n = Math.min(numbers[0], numbers[1]); n <= Math.max(numbers[0], numbers[1]); n++) {
			long currentLength = calculateLength(n);
			if(currentLength > longest) {
				longest = currentLength;
			}
		}
		return longest;	
	}
	
	private static long calculateLength(long n) {
		long counter = 1;
		while(n != 1) {
			if(n%2 == 0) {
				n = n/2;
			} else {
				n = 3*n + 1;
			}
			counter++;
		}
		return counter;
	}	
}

Using this input file:

Code: Select all

1 1
1 2
2 1
2 2
3 2
2 3
3 3
4 3
3 4
4 4
5 4
4 5
5 5
6 5
5 6
6 6
1 10
1 100
1 1000
1 10000
1 100000
999999 1000000

My code returns:

Code: Select all

till$ java _3nplus1/Main < 10_.txt 
1 1 1
1 2 2
2 1 2
2 2 2
3 2 8
2 3 8
3 3 8
4 3 8
3 4 8
4 4 3
5 4 6
4 5 6
5 5 6
6 5 9
5 6 9
6 6 9
1 10 20
1 100 119
1 1000 179
1 10000 262
1 100000 351
999999 1000000 259

Which seems perfectly ok to me.
And of course, the example in and output match perfectly.

I guess, I have a problem with how the input is specified. Dunno.

Please help

[lnr]

There is related volume for this.

[talz13]

I finally got TO getting a WA, after multiple REs... I guess the judge doesn't like packages.

Anyway, here's my code that gets WA:

Code: Select all

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args)
	{
		Main myWork = new Main();
		myWork.begin(args);
	}
	
	void begin(String[] args)
	{
		ArrayList<long[]> numbers = null;
		if (args.length > 0)
		{
			numbers = new ArrayList<long[]>();
			numbers.add(parseLongs(args[0]));
		}
		else
			numbers = getInput();
		long displayInt = 0;
		for ( int i = 0; i < numbers.size(); i ++)
		{
			displayInt = countCycles(numbers.get(i));
			System.out.println(numbers.get(i)[0] + " " + numbers.get(i)[1] + " " + displayInt);
		}
	}
	
	private static ArrayList<long[]> getInput(String[] input)
	{
		String currentLine = null;
		ArrayList<long[]> numberPairs = new ArrayList<long[]>();
		
//		while ((currentLine = Main.ReadLn (255)) != null && currentLine.length() > 1)
//		{
//			numberPairs.add(parseLongs(currentLine));
//		}
		while ((currentLine = getLine("")) != null)
		{
			numberPairs.add(parseLongs(currentLine));
		}
		return numberPairs;
	}
	
	private static ArrayList<long[]> getInput()
	{
		String[] input = new String[0];
		return getInput(input);
	}
	
	private static long[] parseLongs(String input)
	{
        StringTokenizer tokenizer = new StringTokenizer(input);
        long num1 = Long.parseLong(tokenizer.nextToken());
        long num2 = Long.parseLong(tokenizer.nextToken());
        long returnArray[] = new long[2];
        returnArray[0] = num1;
        returnArray[1] = num2;
        return returnArray;
	}
	
	private static int countCycles(long[] input)
	{
		int currentCycles = 0;
		int maxCycles = 0;
		long[] bounds = new long[2];
		for (int i = 0; i < input.length; i++)
		{
			bounds[i] = input[i];
		}
		// Make sure bounds are sorted:
		Arrays.sort(bounds);
		
		// start with lower bound, loop until upper bound:
		for (long i = bounds[0]; i <= bounds[1]; i++)
		{
			long result = i;
			currentCycles = 1;
			
			while (result != 1)
			{
				if ((result & 1) > 0)
				{
					result = 3 * result + 1;
				}
				else
				{
					result = result / 2;
				}
				currentCycles++;
			}
			if (currentCycles > maxCycles)
			{
				maxCycles = currentCycles;
			}
		}
		return maxCycles;
	}
	
	private static String getLine (String prompt)
	{
		System.out.print (prompt);
		String result = new String();
		System.out.flush();
		try
		{
			BufferedReader in = new BufferedReader (new InputStreamReader(System.in));
			result = in.readLine();
			if (result == null || result.equals(""))
				return null;
		}
		catch (IOException ex)
		{
			System.err.println("An IOException ocurred: ");
		}
		return result;
	}
	
	private static String ReadLn (int maxLg)  // utility function to read from stdin
    {
        byte lin[] = new byte [maxLg];
        int lg = 0, car = -1;
        String line = "";

        try
        {
            while (lg < maxLg)
            {
                car = System.in.read();
                if ((car < 0) || (car == '\n'))
                {
                	car = -1;
                	break;
                }
                lin [lg++] += car;
            }
        }
        catch (IOException e)
        {
            return (null);
        }

        if ((car < 0) && (lg == 0)) return (null);  // eof
        return (new String (lin, 0, lg));
    }
	
	private static long[] parseInts(String input)
	{
		long[] returnLong = new long[2];
		ArrayList<String> tempArrayList = new ArrayList<String>();
		String[] tempArray = null;
		
		tempArray = input.split(" ");
		if (tempArray.length > 0)
		{
			for (int i = 0; i < tempArray.length; i++)
			{
				if (tempArray[i].length() > 0)
					tempArrayList.add((String) tempArray[i]);
			}
		}
		tempArray = (String[]) tempArrayList.toArray(new String[tempArrayList.size()]);
		if (tempArray.length != 2)
			return null;
		
		for ( int i = 0; i < 2; i++)
		{
			try
			{
				returnLong[i] = Long.parseLong(tempArray[i]);
			}
			catch (NumberFormatException e)
			{
				System.out.println("Error processing input!  Not a valid long!");
			}
		}
		return returnLong;
	}
}

I have tried, on my build:
extraneous spaces, before and after and in between a set of numbers
boundary conditions (1 1000000 works)
out of order values (i.e. 50 10)
not outputting anything extra, as far as i can tell

[preeteesh]

Hi Below is my code, i am always getting WA for it, it works fine on my local end...



#include <iostream>
#include <string>
#include <set>

using namespace std;


void func(int start_num, int end_num)
{
set<int> numbers_used;

int count = 0;
int total_count = 0;

for(int i=end_num; i>=start_num; i--)
{
count = 0;
int num = i;
if(!numbers_used.empty())
if(numbers_used.find(num)!=numbers_used.end()) // means it was able to find
continue;
if( num == 1)
{
count++;
numbers_used.insert(num);
continue;
}
while ( num != 1)
{
if(num >= start_num && num <= end_num)
numbers_used.insert(num);
// num is even
if( num % 2 == 0 )
{
num = num/2;
count++;
}
// Num is odd
else
{
num = 3*num + 1;
count++;
}
}
if( num == 1)
{
count++;
}
if(count > total_count)
{
total_count = count;
}
}

std::cout << start_num << " " << end_num << " " << total_count;
std::cout << "\n";

}



int main(int argc, char* argv[])
{
char input[500], *tokout;
int num;

char choice;
std::string line;

while ( (choice = cin.get()) != EOF)
{
line = line + choice;
}

cout<<endl;

while ( line.find('\n') != -1 )
{
std::string newline = line;
size_t pos;
pos = line.find('\n');
newline = newline.substr(0,pos);
line = line.substr(pos+1);
tokout = strtok((char *)newline.c_str()," "); //gets the first number
int count = 0;
int start_num = 0;
int end_num = 0;
while ( tokout != NULL ) //while loop to get the rest of the numbers
{
if(count == 0)
start_num = atoi(tokout);
else
end_num = atoi(tokout);
//cout << tokout << endl; //prints the first number
tokout = strtok(NULL," ");
count++;
}
func(start_num, end_num);

}

return 0;
}

Can someone tell me what can be cause of it, please help. I am using Visual studio 2005 to compile..!

[amitwadhwa]

I am not able to find the problem in the following code. The test cases are running fine and the output is consistent with the simple algorithm solution.
Can somebody point me to the problem in the following code. I am getting a Wrong Answer (WA). TIA.

Code: Select all

import java.io.IOException;
import java.util.StringTokenizer;

class Main {	
	 static String ReadLn (int maxLg)  // utility function to read from stdin
	    {
	        byte lin[] = new byte [maxLg];
	        int lg = 0, car = -1;
	        try
	        {
	            while (lg < maxLg)
	            {
	                car = System.in.read();
	                if ((car < 0) || (car == '\n')) break;
	                lin [lg++] += car;
	            }
	        }
	        catch (IOException e)
	        {
	            return (null);
	        }

	        if ((car < 0) && (lg == 0)) return (null);  // eof
	        return (new String (lin, 0, lg));
	    }
	 public static void main(String[] args) {
		 Main myWork = new Main();  // create a dynamic instance
		 myWork.Begin();
	 } 
	 void Begin(){
		 String s;
		 int a,b, min, maxx;
		 StringTokenizer idata;
 	     while ( (s = Main.ReadLn(255)) != null ) {
 	    	 idata = new StringTokenizer (s);
 	          a = Integer.parseInt (idata.nextToken());
 	          b = Integer.parseInt (idata.nextToken());
 	          if(a>b) { min = b; maxx =a;} else {min=a; maxx=b;}
			  System.out.println(a+" "+b+" "+p1(min,maxx));
 	    }				  
	 }

	public int p1(int i, int j){
		int arr[]= new int[j-i+1];		
		int cycleLength=0;
		int max=0;
		int n=0;
		for(int I=i;I<j;I++){
			arr[I-i]=0;
			n=I;
			cycleLength=1;
			while(n>1){
				cycleLength++;
				if (n%2 != 0)
					n=3*n+1;			
				else {
					n>>=1;
	                if(n>i  && n < I){
	                	cycleLength+=arr[n-i]-1;
	                	break;
	                }
				}
			}
			arr[I-i]=cycleLength;
			if(cycleLength>max)
				max=cycleLength;		
		}
		return max;
	}
}

[amitwadhwa]

Sorry my mistake... had to do I<=j :-/

[amitwadhwa]

I have noticed that the system seems to give very large times for java solutions!

For Problem 100
Java naive algorithm was not accepted and Java solution with modified algo using DP algo gave 1.190 sec.
With C++, Naive algo: 1.170, and the DP algorithm: 0.300 secs

I used the Java input function as shown in the sample Java example code in the forum (Btw.. even a copy paste of that solution gives me a RTE)

[Irhadce]

i tried to solve problem 100 and did like you all said I removed the swapping part so i get runtime error plus my solution is in FAQ part(in how to write you source code in UVA) and still get runtime error am i missing something?
here is the code:
#include <stdio.h>

int cycle(m)
int m;
{
int i = 1;

while (m != 1){
if (m % 2 == 0){
m = m/2;
}
else{
m = 3*m+1;
}
i++;
}
return i;
}
main()
{
int m,n,max,temp;
int mOriginal,nOriginal;
int i;
while (scanf("%d %d",&m,&n)==2){
mOriginal = m;
nOriginal = n;
max = cycle(m);
for(i=m+1;i<=n;i++) {
temp = cycle(i);
if (temp > max)
max = temp;
}
printf("%d %d %d\n",mOriginal,nOriginal,max);
}
}

[mf]

Please put the code in [code]...[/code] tags, and post in an existing thread about this problem next time.

You've missed 'return 0' at the end of main().
Non-zero return value from main() is interpreted by the judge as a runtime error.

[Irhadce]

Code: Select all

#include <stdio.h>

int cycle(m)
int m;
{
int i = 1;

while (m != 1){
if (m % 2 == 0){
m = m/2;
}
else{
m = 3*m+1;
}
i++;
}
return i;
}
main()
{
int m,n,max,temp;
int mOriginal,nOriginal;
int i;
while (scanf("%d %d",&m,&n)==2){
mOriginal = m;
nOriginal = n;
max = cycle(m);
for(i=m+1;i<=n;i++) {
temp = cycle(i);
if (temp > max)
max = temp;
}
printf("%d %d %d\n",mOriginal,nOriginal,max);
}
}

Irhadce
    New poster
     
    Posts: 1
    Joined: Sat Nov 15, 2008 5:11 pm

        * Private message

[Obaida]

Then you should use return 0; with int main(), like

Code: Select all

int main()
{
    return 0;
}

And try to pass this Input, you code failed here.
Input:

Code: Select all

10 1

Output

Code: Select all

20

[Anunnaki]

I keep getting TL, and I don't understand why. Can someone look at my code and tell me if they see something?

Code: Select all

#include <iostream>
#include <string>
#include <sstream>
#include <vector>

using namespace std;

int nCalc (int i, int j)
{
    int n, a = 0;
    vector<int> x;

    do
    {
            int di = i;

            for (n = 0; di != 1; n++)
            {

                    if (n == 0)
                    {
                            continue;
                    }

                    if ((di % 2) != 0)
                    {
                            di = (3 * di) + 1;
                            continue;
                    }
                    else
                    {
                            di = di/2;
                    }
            }

            if (i == 1)
                    n = 1;

            x.push_back(n);

            for (int counter = 0; counter < x.size(); counter++)
            {
                    if (x[counter] > a)
                            a = x[counter];
            }

            i++;
    }while(i <= j);

    return a;
}

bool errorCheck(int i, int j)
{
    int const min = 1, max = 1000000;

    bool valid;

    if ((i < min) || (i > max))
    {
            cout << "\nError: Invalid input. Starting integer must be between " << min << " and " << max << ". Try again.\n\n";
            valid = false;
    }

    else if ((j < min) || (j > max))
    {
            cout << "\nError: Invalid input. Ending integer must be between " << min << " and " << max << ". Try again.\n\n";
            valid = false;
    }

    else
            valid = true;

    return valid;
}

int main()
{
    int i, j, n;
    vector<int> cycle;
    string input;
    vector<string> instr;
    string const sentinel = "end";
    bool valid;

        cout << "Input Integers (enter nothing when finished):\n\n";

        instr.clear();
        cycle.clear();

        for (int counter = 0; ; counter++)
        {
            do
            {
                    getline(cin, input);

                    if (input == "\0")
                    {
                            break;
                    }

                    stringstream(input) >> i >> j;

                    valid = errorCheck(i, j);

            }while(!valid);

            if (input == "\0")
            {
                    break;
            }

            else
            {
                    n = nCalc(i, j);
                    cycle.push_back(n);
            }

            instr.push_back(input);

        }

        cout << "\n\n";

        for (int counter = 0; counter < instr.size(); counter++)
        {
                cout << instr[counter] << " " << cycle[counter] << "\n";
        }

    cout << "\n\nPress ANY key to continue...";
    getchar();

    return 0;
}

[mf]

Try giving your program an input with i=1, j=1000000 - it'll take many hours to complete, which is too much. Time limit is only 3 seconds.

And don't print any extra messages, because your program's output is checked automatically by a quite dumb robot. Only output what problem statement tells you - a line with three numbers in it, for each input case.

Also you don't have to do any error checking. Even if there's any error in the input (and there isn't), nobody will read any of those error messages. If you want to get a feedback from judge on these errors, use assert() macro.