Uva的3n + 1问题

我正在解决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  maxCycles) { maxCycles = numberOfCycles; } lowerBound++; } System.out.println(lowerInt +" "+ upperBound+ " "+ (maxCycles+1)); } }

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

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

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

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

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

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

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

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

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

这种方法本身并没有错，但有一些事情你必须考虑到。 首先，输入由一对对列表组成，您只处理第一对。 然后，您必须处理您的memoizing表限制。 您假设您将击中的所有数字都落在[1 … 1000001]范围内，但事实并非如此。 对于输入数字999999（低于上限的第一个奇数），第一个操作将把它变成3 * n + 1，这超出了memoization表的上限。

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

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

恩。

输入

10 1

产量

10 1 20

如果可能请使用此Java规范：阅读输入行http://online-judge.uva.es/problemset/data/p100.java.html

我认为在UVA判断中最重要的是1）获得输出完全相同，最后或任何地方没有额外的线。 2）我假设，永远不会抛出exception只是返回或中断没有输出外部边界参数。 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 (amax) 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; } }

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

 10 1

你应该打印 

 10 1 20 
 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 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(); 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.5秒内被接受。 我不得不删除包修饰符。 

  import java.util.*; public class Main { static Map 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) { } } }
Interesting Posts