只是做一些习题和运行做一些问题，不知道它的逻辑还是什么。我需要一些眼睛

Question

我总是回到这个问题，我从来没有解决过。我不知道为什么它给我这么多问题。我通常可以很好地通过前四个测试用例，然后失败或运行s 太慢了。我开始尝试它已经将近一年了，所以我决定给它一个新的面貌。我不在学校，这只是为了好玩，或者至少我认为是这样。我采用了几何方法，并使用了递归方法。我想知道是否有人可以指出我的逻辑出错的地方，一个会使逻辑失败的测试用例。当我手动计算时，我自己想出的每个测试用例似乎都是正确的。除非我的数学错了；我真的希望不是这样。

这就是问题所在：https://open.kattis.com/problems/a1paper

我有两行输入，第一行告诉我最小的纸张尺寸，A2,3,4,5,....下一行告诉我我的起始纸张数量尺码 2, 3, 4, n.

想法是确定将纸张粘在一起以获得 A1 纸所需的胶带量。

这是我的解决方案：

import java.util.Scanner;

public class A1Paper
{   
    private static Scanner scan = new Scanner(System.in);
    private static final double ABSOLUTE_ERROR = Math.pow(10.0, -5.0);

    public static void main(String[] args)
    {
        final double SHORT_SIDE = Math.pow(2.0, -5.0/4.0);
        final double LONG_SIDE = Math.pow(2.0, -3.0/4.0);
        final double A1_AREA = 2 * SHORT_SIDE * LONG_SIDE;

        int remainingSizes = scan.nextInt() - 1;
        scan.nextLine();

        Result result = process(remainingSizes, SHORT_SIDE, LONG_SIDE, A1_AREA);

        if (result != null)
            System.out.println(result.getTape());
        else
            System.out.println("impossible");

        scan.close();
        return;
    }

    private static Result process(int remainingSizes, double shortSide, double longSide, double remainingArea)
    {   
        if (withinAbsoluteError(remainingArea))
        {
            return null;
        }

        if (remainingSizes == 0)
            return null;

        int remainingSheets = scan.nextInt();

        int sheetsUsed = 0;

        if (remainingSheets > 0)
        {
            double sheetArea = shortSide * longSide;

            while (remainingSheets > 0 && !withinAbsoluteError(remainingArea))
            {   
                remainingSheets--;
                sheetsUsed++;
                remainingArea -= sheetArea;
            }
        }

        Result prevResult = process(remainingSizes - 1, longSide/2.0, shortSide, remainingArea);
        Result thisResult = null;

        if (prevResult == null)
        {
            if (sheetsUsed%2 != 0 || sheetsUsed == 0)
                return null;

            thisResult = new Result(sheetsUsed/2, sheetsUsed/2 * longSide);
        }
        else
        {
            sheetsUsed += prevResult.getSheets();

            if (sheetsUsed%2 !=0)
                return null;

            thisResult = new Result(sheetsUsed/2, prevResult.getTape() + (sheetsUsed/2 * longSide));
        }

        return thisResult;
    }

    private static boolean withinAbsoluteError(double remainingArea)
    {   
        if (remainingArea <= ABSOLUTE_ERROR && remainingArea >= -ABSOLUTE_ERROR)
            return true;
        else
            return false;
    }

    private static class Result
    {
        private int sheets;
        private double tape;

        public Result(int sheets, double tape)
        {
            this.sheets = sheets;
            this.tape = tape;
        }

        public int getSheets()
        {
            return sheets;
        }

        public double getTape()
        {
            return tape;
        }
    }
}

显然存在一个无法使用的测试用例，Kattis 不想给我测试用例，所以我很好奇是否有人知道。正如我所说，我想出的每个例子似乎都通过了。

我将在这里解释我的功能：

private static Result process(int remainingSizes, double shortSide, double longSide, double remainingArea)

第一次调用函数：

remainingSizes ：从输入流接收到的第一个 int。因为它给你最小尺寸的纸张，例如。 4 (A4) ，那么 3 就是剩余的尺寸 (A2, A3, A4)。

给出了大小为 A2 的短边和长边，并用于在第一次迭代时调用该函数：

final double SHORT_SIDE = Math.pow(2.0, -5.0/4.0);
final double LONG_SIDE = Math.pow(2.0, -3.0/4.0);

remainingArea: 最初传递给第一个函数调用时，需要达到A1的Area，或者是A2面积的两倍。

结束递归的两种情况，要么是在absoluteError范围内，要么是我们运行出了不同大小的纸张：

if (withinAbsoluteError(remainingArea))
            {
                return null;
            }

if (remainingSizes == 0)
                return null;

函数的下一部分接受 A2 sheets 的数量（在第一次调用中）。如果我们有 sheets，则计算 A2 的面积，并从剩余面积中减去，同时保持使用的 sheets 和剩余的 sheets 的计数。然后是对该方法的递归调用，将纸张切成两半以获得下一个尺寸 sheet，例如 A3.

int remainingSheets = scan.nextInt();

        int sheetsUsed = 0;

        if (remainingSheets > 0)
        {
            double sheetArea = shortSide * longSide;

            while (remainingSheets > 0 && !withinAbsoluteError(remainingArea))
            {   
                remainingSheets--;
                sheetsUsed++;
                remainingArea -= sheetArea;
            }
        }

        Result prevResult = process(remainingSizes - 1, longSide/2.0, shortSide, remainingArea);

此过程将继续，直到我遇到该区域或 sheet 中的运行。

在该方法的下一部分中，我确定使用的磁带量：

Result thisResult = null;

        if (prevResult == null)
        {
            if (sheetsUsed%2 != 0 || sheetsUsed == 0)
                return null;

            thisResult = new Result(sheetsUsed/2, sheetsUsed/2 * longSide);
        }
        else
        {
            sheetsUsed += prevResult.getSheets();

            if (sheetsUsed%2 !=0)
                return null;

            thisResult = new Result(sheetsUsed/2, prevResult.getTape() + (sheetsUsed/2 * longSide));
        }

        return thisResult;'

这里有两种可能，要么之前的调用返回null，没有页面，要么有页面。我的看法是，如果我通过函数调用返回，则必须有均匀数量的页面，因为我将它们粘在一起并制作更大的页面。

例如：

如果我有 1 - A2, 1 - A3, 2 - A4

然后将 2 - A4 沿其长边粘贴，将制作 A3，将其添加到我拥有的 A3 中，这就是 2 - A3。把那些 2-A3 粘在一起做成一个 A2，把它加到我有的那个上，那就是 2-A2。粗略地说，两个 A2 就是一个 A1。

我不知道这个解释是否完全清除了我的代码，抱歉，如果我让它变得比它必须的更混乱。

Answer 1

正如https://whosebug.com/users/1899640/that-other-guy所指出的，我没有正确使用问题中提供的公差。

给出的容差是最终答案。如果您必须对 0.00001 求和一百万次，则答案需要介于 9.99999 和 10.00001 之间。相反，您的代码表示如果答案为 0 也没关系，因为 0.00001 在容差范围内，因此需要对百万件中的 none 进行计数。这不是合理的推理。 – 那个人

只是做一些习题和运行做一些问题，不知道它的逻辑还是什么。我需要一些眼睛

Just doing some exercises and ran into some problems, don't know if its logic or what. I need some eyes

java

testcase

只是做一些习题和 运行 做一些问题，不知道它的逻辑还是什么。我需要一些眼睛

Just doing some exercises and ran into some problems, don't know if its logic or what. I need some eyes

java

testcase

只是做一些习题和运行做一些问题，不知道它的逻辑还是什么。我需要一些眼睛