CCO '18 P2 - Wrong Answer

View as PDF

Points: 12 (partial)
Time limit: 0.6s
Memory limit: 1G

Author:
Problem type

Troy made the following problem (titled WA) for a programming contest:

There is a game with levels numbered from to . There are two characters, both are initially at level . For , it costs coins to move a character from level to level . It is not allowed to move a character from level to level if . To win the game, every level (except level ) must be visited by exactly one character. What is the minimum number of coins needed to win?

JP is a contestant and submitted the following Python solution.

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 is certain that JP's solution is wrong. Suppose for an input to WA, JP's solution returns but the minimum number of coins needed is . To show how wrong JP's solution is, help Troy find an input and such that is maximized.

Input Specification

There is no input.

Output Specification

Print an input to WA in the following format:

On the first line, print one integer .

Then print lines; the -th line should contain integers .

If your output is not in the correct format, it will get an incorrect verdict on the sample test in the grader and score 0 points.

Otherwise, suppose that for your input, JP's solution returns but the minimum number of coins needed is . Then you will receive points where is the smallest integer that is not less than .

Sample Output

5
1 2 3 4
10 9 8
7 6
5

Explanation for Sample Output

The optimal way to win the game is for one character to visit level 2 and the other character to visit levels 3, 4 and 5. This costs coins. JP's solution returns 18. Thus , so this output will receive point.