Ува 3n + 1 проблема - PullRequest
Новая
       11

Ува 3n + 1 проблема

3 голосов
/ 20 июля 2009

Я решаю проблему Увы 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));

    }


}

Ответы [ 8 ]

2 голосов
/ 20 июля 2009

Вы уверены, что принимаете весь ввод? Похоже, что ваша программа завершает работу после чтения только одной строки и последующей обработки одной строки. Вы должны быть в состоянии принять весь ввод пробы за один раз.

1 голос
/ 18 ноября 2015

Я столкнулся с той же проблемой. У меня сработали следующие изменения:

  • Изменено имя класса на Main.
  • Удален модификатор public из имени класса.

Следующий код выдал ошибку компиляции: 

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

Принимая во внимание, что после изменений был принят следующий код: 

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

Это была очень очень простая программа. Надеемся, что тот же трюк подойдет и для более сложных программ.

0 голосов
/ 09 июля 2017

Это решение принимается в течение 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) {

        }


    }
}
0 голосов
/ 20 октября 2013 
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.
}
0 голосов
/ 15 августа 2013

Обратите внимание, что целые числа i и j должны появляться в выходных данных в том же порядке, в котором они появились во входных данных , поэтому для: 

10 1

Вы должны напечатать 

10 1 20
0 голосов
/ 31 января 2013

Если возможно, используйте эту спецификацию Java: для чтения строк ввода http://online -judge.uva.es / Архив / данные / 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;
        }
    }
0 голосов
/ 23 января 2011

Убедитесь, что вывод был в том же порядке, который указан во входе.Я вижу, где вы меняете вход, если первый вход был выше, чем второй, но вам также нужно убедиться, что вы не изменили порядок, в котором он отображается при вводе результатов.

напр.

Вход

10 1

Выход

10 1 20

0 голосов
/ 20 июля 2009

Если я правильно понимаю, вы используете метод запоминания. Вы создаете таблицу, в которой храните полные результаты для всех уже рассчитанных элементов, поэтому вам не нужно пересчитывать результаты, которые вы уже знаете (вычисленные ранее).

Сам подход не ошибочен, но есть несколько вещей, которые вы должны принять во внимание. Во-первых, вход состоит из списка пар, вы обрабатываете только первую пару. Затем вы должны позаботиться об ограничении вашего стола для запоминания. Вы предполагаете, что все числа, по которым вы попадете, попадают в диапазон [1 ... 1000001), но это не так. Для введенного номера 999999 (первое нечетное число ниже верхнего предела) первая операция превратит его в 3 * n + 1, что намного превышает верхний предел таблицы запоминания.

Некоторые другие вещи, которые вы, возможно, захотите рассмотреть, делят пополам таблицу памятки и запоминают только нечетные числа, так как вы можете реализовать операцию деления на две, почти свободную с помощью битовых операций (и проверка на четность также является только одной битовой операцией) .

...