UVa's 3n + 1 - почему мой код превышает лимит времени?

Question

Вопрос объясняется ниже.

Рассмотрим следующий алгоритм:

1.  input n 
    2.  if n = 1 then STOP 
    3.    if n is odd then n = 3n+1 
    4.    else n=n/2 
    5.  GOTO 2 

Учитывая вход 22, следующая последовательность чисел будет распечатана:

22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 

Высказано предположение, что алгоритм выше будет прекращать (когда 1 печатается) для любого интегрального входного значения. Несмотря на простоту алгоритма, неизвестно, истинна ли эта гипотеза. Однако было подтверждено, что для всех целых чисел n таких, что 0 < n < 1,000,000 (и, фактически, для многих других чисел, чем это.) Учитывая ввод n, можно определить количество напечатанных номеров (включая 1). Для данного n это называется длиной цикла n. В приведенном выше примере длина цикла 22 составляет 16. Для любых двух чисел i и j вы должны определить максимальную длину цикла по всем номерам между i и j.

Sample Input: 1 10 
Sample Output: 1 10 20 

Это мое решение.

import java.io.IOException; 

public class Main{ 
    public static void main(String[]args) { 
     new N1().run(); 
    } 
    public static String readLine(int maxLength) { 
     byte[] bytes = new byte[maxLength]; 
     int length=0; 
     int input = 0; 
     while(length<maxLength) { 
      try { 
       input = System.in.read(); 
      } catch (IOException e) { 
       return null; 
      } 
      if(input=='\n') 
       break; 
      bytes[length] += input; 
      length++; 
     } 
     if(length==0) 
      return null; 
     return new String(bytes, 0, length); 
    } 
} 

class N1 implements Runnable { 

    @Override 
    public void run() { 
     String line = Main.readLine(100); 
     while(line!=null) { 
      solve(line); 
      line = Main.readLine(100); 
     } 
    } 
    private void solve(String input) { 
     String[] tokens = input.trim().split("\\s+"); 
     if(tokens.length!=2) 
      return; 
     int i=-1, j=-1; 
     try{ 
      i = Integer.parseInt(tokens[0]); 
      j = Integer.parseInt(tokens[1]); 
     }catch(Exception e) { 
      return; 
     } 
     if(i<=0||j<=0) 
      return; 
     int low, high; 
     low = (i<j) ? i :j; 
     high = i+j-low; 
     int max = -1; 
     for(int k=i;k<=j;k++) { 
      max = Math.max(max, CycleLength(k)); 
     } 
     System.out.println(i+" "+j+" "+max); 
     return; 
    } 
    private int CycleLength(int k) { 
     int length = 1; 
     long n = k; 
     while(n!=1) { 
      n = (n & 1)==0 ? n>>1 : n*3+1; 
      length++; 
     } 
     return length; 
    } 
} 

Выше моего решения для вопроса UVA 3n + 1. У меня нет проблем с работой с этим кодом на моем ноутбуке, и он отвечает quikly. Однако вердикт «превышен лимит времени» В чем проблема?

Answer 1

Ваш метод run() представляет собой бесконечный цикл, который вызывает readLine(), и readLine() не проверяет конец файла или конец ввода. Таким образом, программа пытается прочитать другую строку, даже когда достигнут конец файла или конец ввода. Так что он ждет навсегда, и время иссякнет.