题目描述

有一个由$N(N+1)/2$个球组成的金字塔，如下图所示。让$(0,0)$表示金字塔顶部的球的坐标，$(x,y)$表示从顶部的第$x$层向左数第$y (0\leq y\leq x)$个球的坐标。

每个球都带有一个从$0$到$N(N+1)/2-1$的数字标签，每个球上的数字都不同。您可以在六个方向上对相邻的两个球进行交换操作。这里，当满足以下条件之一时，坐标为$(x_1,y_1)$和$(x_2,y_2)$的球在六个方向上是相邻的：

• $x_1=x_2-1$且$y_1=y_2-1$
• $x_1=x_2-1$且$y_1=y_2$
• $x_1=x_2$且$y_1=y_2-1$
• $x_1=x_2$且$y_1=y_2+1$
• $x_1=x_2+1$且$y_1=y_2$
• $x_1=x_2+1$且$y_1=y_2+1$

通过最多进行$10000$次操作，请将球排列好，使得除了最底层的每个球$(x,y) (0\leq x\leq N-2, 0\leq y\leq x)$之外，其下方的两个球$(x+1,y), (x+1,y+1)$的标签数字都小于它。请以尽可能少的操作次数实现这个目标。

评分

设$K$为操作次数，$E$为操作完成后违反条件的球对数。这里$E$是满足球$(x,y)$比球$(x+1,y') (y'\in\{y,y+1\})$的编号更大的所有$(x,y)$和$(x+1,y')$球对的总数。那么，您将获得以下分数。

• 如果$E=0$，得分为$100000-5K$。
• 如果$E>0$，得分为$50000-50E$。

共有150个测试用例，提交得分为每个测试用例的总分。如果您的提交产生非法输出或在某些测试用例中超出时间限制，则提交将被判定为WA。