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

入力全体を確実に受け入れるようにしていますか? あなたのプログラムは、1 行だけを読み取ってから 1 行を処理した後に終了するようです。サンプル入力全体を一度に受け入れることができる必要があります。

于 2009-07-19T21:45:10.880 に答える
0

可能であれば、この Java 仕様を使用してください: 入力行を読み取るために http://online-judge.uva.es/problemset/data/p100.java.html

UVA ジャッジで最も重要なことは、1) 出力を取得することです。まったく同じで、最後やどこにも余分な行はありません。2）私は、外側の境界パラメータの出力なしで例外をスローしないか、単にリターンまたはブレークしないと仮定しています。3) 出力では大文字と小文字が区別されます 4) 出力パラメータは、問題に示すようにスペースを維持する必要があります

上記のパターンに基づく考えられる解決策の 1 つがここにあります 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

出力が入力で指定された順序と同じであることを確認しましたか。最初の入力が 2 番目の入力よりも高かった場合、入力を交換している場所がわかりますが、結果を出力するときに入力に表示される順序を変更しないようにする必要もあります。

元。

入力

10 1

出力

10 1 20

于 2011-01-23T07:41:45.500 に答える
0

整数 i と j は、入力に現れたのと同じ順序で出力に現れなければならないことを考慮してください。

10 1

印刷する必要があります

10 1 20
于 2013-08-14T20:36:32.690 に答える
0

私の理解が正しければ、メモ化アプローチを使用しています。計算済みのすべての要素の完全な結果を格納するテーブルを作成して、既に知っている (以前に計算された) 結果を再計算する必要がないようにします。

アプローチ自体は間違っていませんが、考慮しなければならないことがいくつかあります。まず、入力はペアのリストで構成され、最初のペアのみを処理しています。次に、メモ化テーブルの制限に注意する必要があります。ヒットするすべての数値が [1...1000001) の範囲に収まると想定していますが、そうではありません。入力番号 999999 (上限を下回る最初の奇数) の場合、最初の操作で 3*n+1 に変換されますが、これはメモ化テーブルの上限をはるかに超えています。

考慮したい他のいくつかのことは、メモ化テーブルを半分にし、奇数のみを記憶することです。これは、ビット演算でほぼ無料で 2 除算演算を実装できるためです (偶数のチェックも 1 ビット演算にすぎません)。

于 2009-07-19T22:11:00.407 に答える
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 に答える