Troy 为一场编程竞赛设计了以下题目(题名为 WA):
有一个包含 $N$ 个关卡的游戏,关卡编号从 1 到 $N$。有两个角色,初始时都在第 1 关。对于 $i < j$,将一个角色从第 $i$ 关移动到第 $j$ 关的代价为 $A_{i,j}$ 个金币。不允许将角色从第 $i$ 关移动到第 $j$ 关(其中 $i > j$)。为了赢得游戏,除了第 1 关以外的每一个关卡都必须恰好被一个角色访问。赢得游戏所需的最少金币数量是多少?
JP 是一名参赛选手,提交了以下 Python 代码:
def Solve(N, A):
# A[i][j] is cost of moving from level i to level j
# N is the number of levels
x, y, sx, sy = 1, 1, 0, 0 # Initialize x and y to 1, sx and sy to 0
for i in range(2, N + 1): # loop from 2 to N
if sx + A[x][i] < sy + A[y][i]:
sx += A[x][i]
x = i
else:
sy += A[y][i]
y = i
return sx + sy
Troy 确信 JP 的解法是错误的。假设对于某个输入,JP 的解法返回值为 $X$,而赢得游戏所需的最少金币数量为 $Y$。为了展示 JP 的解法有多么错误,请帮助 Troy 找到一组输入 $N$ 和 $A_{i,j}$,使得 $\frac{X}{Y}$ 最大化。
输入格式
无输入。
输出格式
输出一个 WA 题目的输入,格式如下:
第一行输出一个整数 $N$ ($2 \le N \le 100$)。 接下来输出 $N-1$ 行;第 $i$ 行应包含 $N-i$ 个整数 $A_{i,i+1}, \dots, A_{i,N}$ ($1 \le A_{i,j} \le 100$)。
如果你的输出格式不正确,将在评测系统中获得错误判决(incorrect verdict),得分为 0 分。
否则,假设对于你的输入,JP 的解法返回 $X$,而赢得游戏所需的最少金币数量为 $Y$。你将获得 $\lceil \min(25, \frac{X}{4Y}) \rceil$ 分,其中 $\lceil Z \rceil$ 表示不小于 $Z$ 的最小整数。
样例
样例输出 1
5 1 2 3 4 10 9 8 7 6 5
说明
赢得游戏的最优方式是一个角色访问第 2 关,另一个角色访问第 3、4、5 关。这花费了 $(1) + (2 + 7 + 5) = 15$ 个金币。JP 的解法返回 18。因此 $\frac{X}{4Y} = \frac{18}{4 \times 15} = 0.3$,所以该输出将获得 $\lceil 0.3 \rceil = 1$ 分。