Получение ошибки времени выполнения для онлайн-программиста

Question

Итак, вот мой код для the 3n+1 problem on UVa. Он отлично работает на моем ПК в Eclipse AFAIK, однако я все время получаю ошибку времени выполнения от судьи UVa. К сожалению, судья не говорит мне, какие материалы он использует, и не предоставляет никакой информации, кроме «RuntimeException», когда он терпит неудачу. Это ту же структуру, что и ACM's ICPC, для любопытных.

Я уверен, что рекурсия не должна переполнять стек, так как максимальная длина цикла всех чисел от 1 до 1000000 составляет всего 525. Кроме того, кеш 1000000 целых чисел должен быть всего 4 МБ.

package Collatz; 

import java.util.Arrays; 
import java.util.Scanner; 

class Main{ 
    public static void main(String[] args) { 
     Scanner in = new Scanner(System.in); 
     int[] cache = buildCache(1000000); 
     while (in.hasNextLine()) { 
      Scanner line = new Scanner(in.nextLine()); 
      if (!line.hasNextInt()) continue; 
      int a = line.nextInt(); 
      int b = line.nextInt(); 
      int c = a; 
      int d = b; 
      if (c > d) { 
       int temp = c; 
       c = d; 
       d = temp; 
      } 
      int max = 0; 
      for (int i = c - 1; i <= d - 1; i++) { 
       max = Math.max(max, cache[i]); 
      } 
      System.out.format("%d %d %d\n", a, b, max); 
      line.close(); 
     } 
     in.close(); 
    } 

    public static int[] buildCache(int n) { 
     int[] cache = new int[n]; 
     Arrays.fill(cache, 0); 
     cache[0] = 1; 
     for (int i = 1; i < n; i++) { 
      search(i + 1, cache); 
     } 
     return cache; 
    } 

    public static int search(long i, int[] cache) { 
     int n = cache.length; 
     if (i == 1) { 
      return 1; 
     } else if (i <= n && cache[(int)(i - 1)] > 0) { 
      return cache[(int)(i - 1)]; 
     } else { 
      long j = (i % 2 == 1) ? (3 * i + 1) : (i/2); 
      int result = search(j, cache) + 1; 
      if (i <= n) { 
       cache[(int)(i - 1)] = result; 
      } 
      return result; 
     } 
    } 
} 

Answer 1

ОК. Я, наконец, нашел проблему. Это заявление пакета. Программа принимается после ее удаления ... Немного ошибка для меня, когда код копирования-вставки из моей IDE в форму отправки. Но есть интересные обсуждения здесь и спасибо всем!

Answer 2

Логика здесь переполнит стек. Он выполняет поиск следующего числа в последовательности перед кэшированием результата функции на текущем.

int result = search(j, cache) + 1; 
    if (i <= n) { 
     cache[(int)(i - 1)] = result; 
    } 
    return result;