P14995 [Nordic OI 2020] Apple Delivery

苹果农场主 Ingrid 刚刚收获了大量的苹果，打算分给自己和她的邻居们。她的邻里可以表示为一个无限的平面，其中每个整数坐标点上都恰好有一栋房子。Ingrid 的房子位于原点 $(0, 0)$。Ingrid 在分配苹果时有一个特别的策略。首先，她选定一个包含 $n$ 个非负整数 $r_1, r_2, \cdots, r_n$ 的列表。对于列表中的每个数，她会给半径 $r_i$ 内的每栋房子（包括她自己的房子）一个苹果，即所有坐标满足 $x^2 + y^2 \leq r_i^2$ 的房子。这样，Ingrid 的近邻们会比远邻们得到更多的苹果。 Ingrid 刚刚选定了半径列表，但随即出现了一个问题。她在分配苹果时总是将苹果放入立方体形状的盒子里，每个盒子能装八个苹果。因此，分发的苹果总数是八的倍数这一点非常重要。Ingrid 需要从列表中移除一些半径，使得给出的苹果总数变为八的倍数。这样做总是可行的，例如移除所有半径，但 Ingrid 不想显得贪婪，所以她希望以一种方式移除半径，使得她原本计划给出的苹果中未被分发的数量最少。你的任务是找出这个最小值。

- 第一行：整数 $N$，即半径的数量（$1 \leq N \leq 3 \cdot 10^5$）。 - 第二行：由空格分隔的整数 $r_1, r_2, \ldots, r_N$（$0 \leq r_i \leq 3 \cdot 10^5$）。

输出一个整数，表示 Ingrid 通过从列表中移除半径，使得分发的苹果总数变为八的倍数时，所能保留不分发的苹果数的最小值。

在半径分别为： - 0 内有 1 栋房子； - 1 内有 5 栋房子； - 2 内有 13 栋房子。 因此，在这些半径内总共有 26 栋房子。通过移除两个半径为 0 的项，剩下 24 栋房子。 ### 评分细则 你的解法将通过子任务进行测试。要获得一个子任务的分数，你需要通过该子任务中的所有测试用例。 | # | 分数 | 限制条件 | |:-:|:-:|:-:| | 1 | 15 | $n \leq 10$，且对所有 $i$ 有 $r_i \leq 300$ | | 2 | 25 | $n \leq 3000$，且对所有 $i$ 有 $r_i \leq 1000$ | | 3 | 15 | $n \leq 3 \cdot 10^5$，且对所有 $i$ 有 $r_i \leq 10^4$ | | 4 | 45 | 无额外限制。 | 翻译由 DeepSeek V3 完成