loj#P3515. 「CCO 2018 Day1」Wrong Answer
「CCO 2018 Day1」Wrong Answer
Cannot parse: undefinedms error parsing time
题目描述
译自 Canadian Computing Olympiad 2018 Day 1 Wrong Answer
Troy 为程序设计竞赛出了一道题(标题是 WA):
有一个爬塔游戏,塔有 层,并从 到 标号。有两个人物,初始他们都在第 层。对于 ,将一个人物从第 层移到第 层要 个金币。如果 ,则不允许人物移动。为了获得游戏胜利,每层塔(除了第 层)都必须有至少一个人物到过。为了获胜,至少要花费多少金币?
JP 是一个选手,他提交了如下的 Python 代码:
def Solve(N, A):
# A[i][j] 是从第 i 层移到第 j 层的花费
# N 是层数
x, y, sx, sy = 1, 1, 0, 0 # 初始化 x 和 y 为 1, sx 和 sy 为 0
for i in range(2, N + 1): # 从 2 到 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
Tory 确信 JP 的解法是错的。设对于这道题的一个输入,JP 的程序输出 但是最少花费的金币数为 。为了说明 JP 的解法错得有多离谱,请帮助 Troy 构造一个输入(包含 和 ),使得 最大。
输出格式与评分规则
本题为提交答案题
按以下格式提交一组题目 WA 的输入:
第一行一个整数 。
接下来 行,第 行包含 个整数 。
如果输入的格式不正确,将被判为答案错误,记 分。
否则,假设对于你的输入,JP 的程序输出 ,但是最少花费的金币数为 。你会得到 分,这里 是指不小于 的最小整数。
样例
样例输出
5
1 2 3 4
10 9 8
7 6
5
样例解释
赢下游戏的最优方案是,先让一个人物去第 层,然后另一个人物去第 层。一共花费 个金币。JP 的程序将返回 ,因此 ,因此这组输出会得 分。