java - 《Sherlock》和《Counting》未被 HackerRank 接受

Question

这是关于《神探夏洛克和计数》的问题。 https://www.hackerrank.com/challenges/sherlock-and-counting

我使用 diffchecker 来比较我的代码生成的数千个结果与我使用 hackos 购买的结果。他们是一样的!尽管我的结果与使用 hackos 购买的结果相同，但我的代码返回错误。

我已经删除了 diffchecker 链接，因为它太大并卡住了选项卡，但我测试了前 2000 个结果，我的结果与使用 hackos 购买的结果相同。简而言之，我不明白为什么Hackerrank不接受我的代码？您可以尝试输入此代码并注意到您确实得到了与测试用例(使用hackos购买的)相同的结果，但不知何故它不接受它？

import java.io.*;
import java.util.*;
import java.math.*;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT.
        Your class should be named Solution. */
        Scanner in = new Scanner(System.in);
        int testcases = in.nextInt();
        /* Each individual test case */
        for(int index = 0; index < testcases; ++index)
        {
            long N = in.nextLong();
            long K = in.nextLong();
            /* Notice that we require i < N and i to be a positive integer.
            This is impossible if N == 1. Therefore, a simple test solves
            a big issue. */
            if(N <= 1){
                System.out.println(0);
            }
            /* Test if discriminant is negative. If it is, the number of
            integers is N - 1 because every number fits under the graph. */
            else if(N*N - 4*N*K < 0) 
            {
                System.out.println(N - 1);
            }
            /* Notice if the discriminant is zero, then necessarily
            N = 4 * K. In an alternate form, the quadratic will be
            written as i^2 - Ni + N^2/4, also recognized as (i - N/2)^2.
            Therefore, the answer is N - 2. */
            else if (N*N - 4*N*K == 0)
            {
                System.out.println(N - 1);
            }
            /* Test if discriminant is positive. If it is, the number of
            integers depends on the locus of solutions. */
            else if(N*N - 4*N*K > 0)
            {
                long solnOne = (long) (N + Math.sqrt(N*N - 4*N*K))/2;
                long solnTwo = (long) (N - Math.sqrt(N*N - 4*N*K))/2;
                if(solnOne > solnTwo){
                    long temp = solnOne;
                    solnOne = solnTwo;
                    solnTwo = temp;
                }
                long LeftBound = (long) solnOne;
                long RightBound = (long) solnTwo + 1;

                /* Now there may be possibilities such that the left solution
                is less than one and/or the right solution is greater than or equal
                to the bound. We must account for these possibilities. */

                /* Here, both bounds are unacceptable. Therefore, there is no
                solution. */
                if(LeftBound < 1 && RightBound >= N)
                {
                    System.out.println(0);
                }
                /* Here, only the right bound is acceptable. */
                else if(LeftBound < 1)
                {
                    System.out.println(N - RightBound);
                }
                /* Here, only the left bound is acceptable. */
                else if(RightBound >= N)
                {
                    System.out.println(LeftBound);
                }
                /* Both bounds are allowed! */
                else
                {
                    System.out.println(N - RightBound + LeftBound);
                }
            }
        }

    }
}

Answer 1

尝试N=9, K=2 。你的答案是5 .
有效值为 i = [1, 2, 3, 6, 7, 8] ，所以真正的答案是6 .

首先，你的solnOne总是>= solnTwo 。翻转它们和你的if(solnOne > solnTwo)永远不会是真的。

第二，转换为long 截断值。这就是为什么你这样做solnTwo + 1 ，但是当 solnTwo正好等于 6 ，+ 1会错过这个有效值。另外，您转换到 long 在除以 2 之前。哎呀!

相反，不要转换到 long :

double solnOne = (N - Math.sqrt(N*N - 4*N*K))/2;
double solnTwo = (N + Math.sqrt(N*N - 4*N*K))/2;
long LeftBound = (long) Math.floor(solnOne);
long RightBound = (long) Math.ceil(solnTwo);

此外，由于 HackerRank 可能会让您超时，因此性能很重要，因此为了帮助 JIT，请计算 N*N - 4*N*K仅一次并存储在变量中。 Math.sqrt(N*N - 4*N*K) 相同，自 sqrt()速度比较慢。

为了您自己的测试，您应该移动所有内容，从 if(N <= 1){ 开始，变成static long calc(long N, long K)方法。然后您可以针对它编写单元测试。