在Java代码中获取NZEC

Question

我试图解决这个问题http://www.codechef.com/APRIL12/problems/DUMPLING/

我在codechef上遇到运行时错误NZEC.我在互联网上搜索但没有设法让我的代码成功.

这是我的代码:

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);
        }
    }

}

任何人都可以告诉我,我在哪里做错了？

Answer 1

除非出现不太可能出现的情况,否则使用该程序获取非零退出代码的唯一可能性就是

• 除以零,但如果输入符合规范则不会发生
• 意外的输入格式导致a NumberFormatException

所以我正在研究后一种假设.一个简单的方法来检查将代替两个catch(IOException e)用catch(Exception e),如果输入的确不是你所期望的格式,你会得到一个"错误答案",那么(但改变后得到一个WA并不能证明假设是正确的) .

在第一行任何额外的空格会导致NumberFormatException在Integer.parseInt(str).任何后续行上的额外空格将导致String[]创建的str.split(" ")具有五个以上的元素,如果在该行上的第五个数字之前发生任何此类,则程序将尝试创建BigInteger.valueOf(""),这再次导致a NumberFormatException.所以我建议使用更强大的输入法,例如java.util.Scanner可以毫无问题地处理额外的空格.这里使用的方法是nextInt()测试用例的数量和nextLong()其余的.

Scanner scn = new Scanner(System.in);
int t = scn.nextInt();
for(int w = 0; w < t; w++){
    BigInteger a = BigInteger.valueOf(scn.nextLong());
    BigInteger b = BigInteger.valueOf(scn.nextLong());
    BigInteger c = BigInteger.valueOf(scn.nextLong());
    BigInteger d = BigInteger.valueOf(scn.nextLong());
    BigInteger k = BigInteger.valueOf(scn.nextLong());

    BigInteger g1,g2,num;
    ...

如果这种变化导致接受,那么NZEC的原因可能是意外的输入格式.

你问

任何人都可以告诉我,我在哪里做错了？

所以我会指出一些不是严格错误的东西,但不好的做法/毫无意义.

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

那个方法应该是static.它不涉及任何状态,因此必须创建一个对象只是为了调用它是不好的.

另一点,与那些可能出现在问题中的小数字无关,但如果处理大数字则相关,那就是你使它递归.Java通常(如果有的话)不执行尾调用优化,并且调用堆栈通常只能处理几千个调用,因此您可能会面临StackOverflowError递归实现的风险.(但由于欧几里德算法的调用深度是对数的,因此只涉及更大的数字.)

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

捕获异常只是为了向stdout打印"错误"是不好的.如果你不能做一些更有意义的事情来处理它,就不要抓住它.

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");
    }

毫无意义catch.

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

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

我怀疑你交换以避免mod股息小于除数的操作.有些地方这种微观优化很重要,但这不是其中之一.如果你有理由关心这样的小事,那还有很多工作要做.例如,可以使用long(有一个地方需要调整算法以避免可能的溢出)来解决手边的问题,并且该原始类型的更快的算法会使您从交换中获得的小增益相形见绌.