Erste NZEC in Java-Code

Question

Ich versuche, das Problem http://www.codechef.com/APRIL12/problems/DUMPLING/

Ich erhalte Laufzeitfehler NZEC auf codechef zu lösen. Ich suchte im Internet, schaffte es aber nicht, meinen Code erfolgreich zu machen.

Dies ist mein Code:

import java.io.BufferedReader; 
import java.io.IOException; 
import java.io.InputStreamReader; 
import java.math.BigInteger; 

public class Main { 

    public BigInteger gcd(BigInteger a,BigInteger b){ 
     if(b.compareTo(BigInteger.valueOf(0)) == 0) 
      return a; 
     return gcd(b,a.mod(b)); 
    } 

    public static void main(String[] args) { 
     BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
     String str; 
     int t = 1; 
     Main obj = new Main(); 
     try{ 
      str = br.readLine(); 
      t = Integer.parseInt(str); 
     } 
     catch(IOException e){ 
      System.out.println("error"); 
     } 

     for(int w = 0; w < t; w++){ 
      BigInteger a = BigInteger.valueOf(1); 
      BigInteger b = BigInteger.valueOf(1); 
      BigInteger c = BigInteger.valueOf(1); 
      BigInteger d = BigInteger.valueOf(1); 
      BigInteger k = BigInteger.valueOf(1); 
      try{ 
       str = br.readLine(); 
       String s[] = str.split(" "); 
       a = new BigInteger(s[0]); 
       b = new BigInteger(s[1]); 
       c = new BigInteger(s[2]); 
       d = new BigInteger(s[3]); 
       k = new BigInteger(s[4]); 
      } 
      catch(IOException e){ 
       System.out.println("error"); 
      } 

      BigInteger g1,g2,num; 
      if(a.compareTo(b) < 0){ 
       num = a; 
       a = b; 
       b = num; 
      } 

      if(c.compareTo(d) < 0){ 
       num = c; 
       c = d; 
       d = num; 
      } 

      g1 = obj.gcd(a,b); 
      g2 = obj.gcd(c,d); 

      if(g1.compareTo(g2) < 0){ 
       num = g1; 
       g1 = g2; 
       g2 = num; 
      } 
      BigInteger g3 = obj.gcd(g1,g2); 

      BigInteger l = g1.divide(g3); 
      l = l.multiply(g2); 

      BigInteger res = k.divide(l); 
      BigInteger fin = res.multiply(BigInteger.valueOf(2)); 
      fin = fin.add(BigInteger.valueOf(1)); 
      System.out.println(fin); 
     } 
    } 

} 

kann jemand bitte sagen Sie mir, wo mache ich falsch?

Answer 1

unwahrscheinlich Szenarien Sperre, die nur Möglichkeiten mit diesem Programm einen von Null verschiedenen Exit-Code erhalten, die ich sehe, ist

• Division durch Null, aber das kann nicht geschehen, wenn der Eingang die Spezifikationen entspricht
• unerwartetes Eingabeformat, was zu einem NumberFormatException

führt Also arbeite ich von der letzteren Hypothese. Eine einfache Möglichkeit zu überprüfen wäre, die beiden catch(IOException e) durch catch(Exception e) zu ersetzen, wenn die Eingabe tatsächlich nicht in dem Format ist, das Sie erwarten, würden Sie dann eine "falsche Antwort" bekommen (aber ein WA nach der Änderung beweist die Hypothese nicht richtig).

Alle zusätzlichen Leerzeichen in der ersten Zeile würden NumberFormatException in Integer.parseInt(str) verursachen. Zusätzliche Leerzeichen in jeder späteren Zeile würden dazu führen, dass die String[], die von str.split(" ") erstellt wurde, mehr als fünf Elemente hat. Wenn eine solche vor der fünften Nummer in dieser Zeile auftritt, versucht das Programm, BigInteger.valueOf("") zu erstellen, was wiederum eine NumberFormatException verursacht. Daher würde ich eine robustere Eingabemethode empfehlen, zum Beispiel eine java.util.Scanner, die problemlos mit zusätzlichen Leerzeichen umgehen kann. Die hier zu verwendenden Methoden sind nextInt() für die Anzahl der Testfälle und nextLong() für den Rest.

Wenn diese Änderung zu einer Annahme führt, war die Ursache für das NZEC wahrscheinlich ein unerwartetes Eingabeformat.

---

Sie fragen

kann jemand bitte sagen Sie mir, wo mache ich falsch?

also werde ich noch einige Dinge aufzeigen, die nicht streng inkorrekt sind, aber schlechte Praxis/sinnlos.

public BigInteger gcd(BigInteger a,BigInteger b){ 
    if(b.compareTo(BigInteger.valueOf(0)) == 0) 
     return a; 
    return gcd(b,a.mod(b)); 
} 

Diese Methode sollte static sein. Es beinhaltet überhaupt keinen Zustand, also ein Objekt zu erschaffen, nur um es anzurufen, ist schlecht.

Ein weiterer Punkt, nicht relevant für kleine Zahlen wie die, die in dem Problem auftreten können, aber relevant, wenn Sie mit großen Zahlen befassen, ist, dass Sie es rekursiv gemacht haben. In der Regel führt Java (wenn überhaupt) keine Tail-Call-Optimierung durch, und der Aufruf-Stack kann normalerweise nur ein paar tausend Aufrufe verarbeiten, so dass Sie mit der rekursiven Implementierung ein StackOverflowError riskieren. (Da jedoch die Aufruftiefe für den euklidischen Algorithmus logarithmisch ist, betrifft dies nur größere Zahlen.)

catch(IOException e){ 
    System.out.println("error"); 
} 

Eine Ausnahme abfangen, nur um "Fehler" zu stdout zu drucken, ist schlecht. Wenn Sie etwas Sinnvolleres nicht tun können, fangen Sie es überhaupt nicht ein.

for(int w = 0; w < t; w++){ 
    BigInteger a = BigInteger.valueOf(1); 
    BigInteger b = BigInteger.valueOf(1); 
    BigInteger c = BigInteger.valueOf(1); 
    BigInteger d = BigInteger.valueOf(1); 
    BigInteger k = BigInteger.valueOf(1); 

einen Dummy-Wert der Variablen zuweisen sinnlos ist, werden sie sofort auf ihre wirklichen Werte gesetzt werden (oder das Programm sollte sterben, wenn das fehlschlägt).

try{ 
     str = br.readLine(); 
     String s[] = str.split(" "); 
     a = new BigInteger(s[0]); 
     b = new BigInteger(s[1]); 
     c = new BigInteger(s[2]); 
     d = new BigInteger(s[3]); 
     k = new BigInteger(s[4]); 
    } 
    catch(IOException e){ 
     System.out.println("error"); 
    } 

Pointless catch wieder.

if(a.compareTo(b) < 0){ 
     num = a; 
     a = b; 
     b = num; 
    } 

    if(c.compareTo(d) < 0){ 
     num = c; 
     c = d; 
     d = num; 
    } 

Ich vermute, Sie tauschen einen mod Betrieb zu vermeiden, dass die Dividende als der Divisor kleiner ist. Es gibt Orte, an denen solche Mikrooptimierungen wichtig sind, aber das gehört nicht dazu. Wenn Sie Grund hätten, sich um kleine Dinge wie diese zu kümmern, würde es viel mehr zu tun geben. Zum Beispiel kann das vorliegende Problem unter Verwendung von long gelöst werden (es gibt eine Stelle, an der der Algorithmus angepasst werden müsste, um einen möglichen Überlauf zu vermeiden), und die viel schnellere Arithmetik dieses primitiven Typs würde den kleinen Gewinn, den Sie von dem Swap erhalten könnten, in den Schatten stellen Hier.

Answer 2

Verwenden Sie BufferedReader anstelle der Scanner-Klasse, und statt try-catch zu verwenden, wird NumberFormatException ausgelöst und IOException ausgelöst. Dies ist der Fall, wenn Sie Try-Catch verwenden, erhalten Sie möglicherweise eine falsche Antwort.