3

我正在解决 Uva 的 3n+1 问题，但我不明白为什么法官拒绝我的回答。没有超过时间限制，到目前为止我尝试过的所有测试用例都运行正常。

   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));

    }


}
4

8 回答 8

2

你确定接受整个输入吗？看起来您的程序在仅读取一行后终止，然后处理一行。您需要能够一次接受整个样本输入。

于 2009-07-19T21:45:10.880 回答
1

我遇到了同样的问题。以下更改对我有用：

  • 将类名更改为 Main。
  • 从类名中删除了public修饰符。

以下代码给出了编译错误：

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

而在更改之后，以下代码被接受：

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

这是一个非常非常简单的程序。希望同样的技巧也适用于更复杂的程序。

于 2015-11-18T02:18:49.933 回答
0

如果我理解正确，您正在使用一种记忆方法。您创建一个表格，在其中存储您已经计算的所有元素的完整结果，这样您就不需要重新计算您已经知道（之前计算过的）的结果。

方法本身并没有错，但是您必须考虑几件事。首先，输入由一对列表组成，您只处理第一对。然后，您必须注意您的记忆表限制。您假设您将达到的所有数字都在 [1...1000001) 范围内，但事实并非如此。对于输入数字 999999（低于上限的第一个奇数），第一个操作会将其变为 3*n+1，这远远超出了记忆表的上限。

您可能需要考虑的其他一些事情是将记忆表减半并且只记忆奇数，因为您可以通过位操作几乎免费地实现除以二的操作（并且检查偶数也只是一位操作）。

于 2009-07-19T22:11:00.407 回答
0

请考虑整数 i 和 j 必须按照它们在输入中出现的顺序出现在输出中，因此：

10 1

你应该打印

10 1 20
于 2013-08-14T20:36:32.690 回答
0 
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.
}
于 2013-10-19T20:59:02.600 回答
0

您是否确保输出与输入中指定的顺序相同。如果第一个输入高于第二个，我会看到您在哪里交换输入，但是您还需要确保在打印结果时不要更改它在输入中出现的顺序。

前任。

输入

10 1

输出

10 1 20

于 2011-01-23T07:41:45.500 回答
0

如果可能，请使用此 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;
        }
    }
于 2013-01-31T18:36:26.727 回答
0

该解决方案在 0.5 秒内被接受。我不得不删除包修饰符。

   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) {

        }


    }
}
于 2017-07-09T16:56:33.953 回答