Uva 3n + 1 problem

Question

Uva 3n + 1 problem

I am solving the Uva 3n + 1 problem and I do not understand why the judge rejects my answer. The time limit was not exceeded, and all the test cases that I tried were correctly executed so far.

   import java.io.*;



public class NewClass{

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) throws IOException {

        int maxCounter= 0; 
        int input; 

        int lowerBound; 
        int upperBound; 
        int counter;
        int numberOfCycles;
        int maxCycles= 0;
        int lowerInt;
        BufferedReader consoleInput = new BufferedReader(new InputStreamReader(System.in));
        String line = consoleInput.readLine();
        String [] splitted =  line.split(" ");

        lowerBound = Integer.parseInt(splitted[0]);
        upperBound = Integer.parseInt(splitted[1]);


        int [] recentlyused =  new int[1000001];



if (lowerBound > upperBound )
{
    int h = upperBound;
    upperBound = lowerBound;
    lowerBound = h;

}
lowerInt = lowerBound;
        while (lowerBound <= upperBound)
        {
            counter = lowerBound;
            numberOfCycles = 0;


            if (recentlyused[counter] == 0)
            {
                while ( counter != 1 )
                {


                        if (recentlyused[counter] != 0)
                        {

                        numberOfCycles = recentlyused[counter] + numberOfCycles;
                        counter = 1;
                        }
                        else
                        {
                            if (counter % 2 == 0)
                            {
                            counter = counter /2;
                            }
                            else
                            {
                            counter = 3*counter + 1;
                            }
                            numberOfCycles++;
                        }

                }
            }
            else
            {

            numberOfCycles = recentlyused[counter] + numberOfCycles;
            counter = 1;
            }

            recentlyused[lowerBound] = numberOfCycles;



            if (numberOfCycles > maxCycles)
            {
            maxCycles = numberOfCycles;
            }

            lowerBound++;
        }
        System.out.println(lowerInt +" "+ upperBound+ " "+ (maxCycles+1));

    }


}

+3

java collatz

andandandand Jul 19 '09 at 21:30

source share

8 answers

AlbertoPL · Answer 1 · 2009-07-19T21:45:10+0000

Are you sure you accept all input? It looks like your program ends after reading only one line and then processes one line. You should be able to immediately accept the entire sample input.

sudhir shakya · Answer 2 · 2015-11-18T02:18:49+0000

I ran into the same problem. The following changes worked for me:

Changed the class name for Main.
Modifier removed publicfrom class name.

The following code gave a compilation error:

public class Optimal_Parking_11364 {
    public static void main(String[] args) {
        ...
    }
}

:

class Main {
    public static void main(String[] args) {
        ...
    }
}

. , .

David Rodríguez - dribeas · Answer 3 · 2009-07-19T22:11:00+0000

, memoizing-. , , , , ( ).

, , . -, , . memoizing. , , , [1... 1000001), . 999999 ( ) 3 * n + 1, memoization.

, , , , memoization , ( - ).

Sophy Pal · Answer 4 · 2011-01-23T07:41:45+0000

, , . , , , , , .

.

10 1

10 1 20

dekdev · Answer 5 · 2013-01-31T18:36:26+0000

, Java: http://online-judge.uva.es/problemset/data/p100.java.html

, UVA: 1) , . 2) , , . 3) 4) ,

, , https://gist.github.com/4676999

    /*

    Problem URL: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=36


    Home>Online Judge > submission Specifications 
    Sample code to read input is from : http://online-judge.uva.es/problemset/data/p100.java.html

    Runtime : 1.068
    */
    import java.io.*;
    import java.util.*;

    class Main
    {
        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')) 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[])  // entry point from OS
        {
            Main myWork = new Main();  // create a dinamic instance
            myWork.Begin();            // the true entry point
        }

        void Begin()
        {

            String input;
            StringTokenizer idata;
            int a, b,max;


            while ((input = Main.ReadLn (255)) != null)
            {
              idata = new StringTokenizer (input);
              a = Integer.parseInt (idata.nextToken());
              b = Integer.parseInt (idata.nextToken());

              if (a<b){
                  max=work(a,b);

              }else{
                  max=work(b,a);
              }
              System.out.println (a + " " + b + " " +max);
            }
        }

        int work( int a , int b){
            int max=0;
            for ( int i=a;i<=b;i++){
                int temp=process(i);
                if (temp>max) max=temp;
            }
            return max;
        }
        int process (long n){
            int count=1;
            while(n!=1){
                count++;
                if (n%2==1){
                    n=n*3+1;
                }else{
                    n=n>>1;
                }
            }

            return count;
        }
    }

Walter R · Answer 6 · 2013-08-14T20:36:32+0000

, , j , , :

10 1

10 1 20

user2558337 · Answer 7 · 2013-10-19T20:59:02+0000

package pandarium.java.preparing2topcoder;/*
 * Main.java
 *  java program model for www.programming-challenges.com
 */

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

class Main implements Runnable{
    static String ReadLn(int maxLg){  // utility function to read from stdin,
        // Provided by Programming-challenges, edit for style only
        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')) 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[])  // entry point from OS
    {
        Main myWork = new Main();  // Construct the bootloader
        myWork.run();            // execute
    }

    public void run() {
        new myStuff().run();
    }
}
class myStuff implements Runnable{
    private String input;
    private StringTokenizer idata;
    private List<Integer> maxes;

    public void run(){

        String input;
        StringTokenizer idata;
        int a, b,max=Integer.MIN_VALUE;


        while ((input = Main.ReadLn (255)) != null)
        {
            max=Integer.MIN_VALUE;
            maxes=new ArrayList<Integer>();
            idata = new StringTokenizer (input);
            a = Integer.parseInt (idata.nextToken());
            b = Integer.parseInt (idata.nextToken());

            System.out.println(a + " " + b + " "+max);

        }
    }
    private static int getCyclesCount(long counter){
        int cyclesCount=0;
        while (counter!=1)
        {
            if(counter%2==0)
                counter=counter>>1;
            else
                counter=counter*3+1;
            cyclesCount++;
        }
        cyclesCount++;
        return cyclesCount;
    }
    // You can insert more classes here if you want.
}

Rabiees · Answer 8 · 2017-07-09T16:56:33+0000

This decision is made within 0.5 s. I had to remove the package modifier.

   import java.util.*;

    public class Main {

    static Map<Integer, Integer> map = new HashMap<>();

    private static int f(int N) {
        if (N == 1) {
            return 1;
        }

        if (map.containsKey(N)) {
            return map.get(N);
        }

        if (N % 2 == 0) {
            N >>= 1;
            map.put(N, f(N));
            return 1 + map.get(N);
        } else {
            N = 3*N + 1;
            map.put(N, f(N) );
            return 1 + map.get(N);
        }
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        try {
            while(scanner.hasNextLine()) {
                int i = scanner.nextInt();
                int j = scanner.nextInt();

                int maxx = 0;
                if (i <= j) {
                    for(int m = i; m <= j; m++) {
                        maxx = Math.max(Main.f(m), maxx);
                    }
                } else {
                    for(int m = j; m <= i; m++) {
                        maxx = Math.max(Main.f(m), maxx);
                    }
                }
                System.out.println(i + " " + j + " " + maxx);
            }
            System.exit(0);
        } catch (Exception e) {

        }


    }
}

Uva 3n + 1 problem

More articles: