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):

有一个爬塔游戏,塔有 NN 层,并从 11NN 标号。有两个人物,初始他们都在第 11 层。对于 i<ji<j,将一个人物从第 ii 层移到第 jj 层要 Ai,jA_{i,j} 个金币。如果 i>ji>j,则不允许人物移动。为了获得游戏胜利,每层塔(除了第 11 层)都必须有至少一个人物到过。为了获胜,至少要花费多少金币?

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 的程序输出 XX 但是最少花费的金币数为 YY。为了说明 JP 的解法错得有多离谱,请帮助 Troy 构造一个输入(包含 NNAi,jA_{i,j}),使得 XY\frac{X}{Y} 最大。

输出格式与评分规则

本题为提交答案题

按以下格式提交一组题目 WA 的输入:

第一行一个整数 N (2N100)N\ (2\le N\le 100)
接下来 N1N-1 行,第 ii 行包含 NiN-i 个整数 Ai,i+1,,Ai,N (1Ai,j100)A_{i,i+1},\ldots, A_{i,N}\ (1\le A_{i,j}\le 100)

如果输入的格式不正确,将被判为答案错误,记 00 分。

否则,假设对于你的输入,JP 的程序输出 XX,但是最少花费的金币数为 YY。你会得到 4min(25,X4Y)4\cdot \lceil \min(25, \frac{X}{4Y})\rceil 分,这里 Z\lceil Z \rceil 是指不小于 ZZ 的最小整数。

样例

样例输出

5
1 2 3 4
10 9 8
7 6
5

样例解释

赢下游戏的最优方案是,先让一个人物去第 22 层,然后另一个人物去第 3,4,53,4,5 层。一共花费 (1)+(2+7+5)=15 (1) + (2 + 7 + 5) = 15 个金币。JP 的程序将返回 1818,因此 X4Y=184×15=0.3\frac{X}{4Y}=\frac{18}{4\times 15}=0.3,因此这组输出会得 40.3=44\cdot \lceil 0.3\rceil =4 分。