QOJ.ac

QOJ

时间限制: 1 s 内存限制: 2048 MB 总分: 25

#2725. 错误答案

统计

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$ 分。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.