## CCO '18 P2 - Wrong Answer

View as PDF

Points: 12 (partial)
Time limit: 1.0s
Memory limit: 512M

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 1. 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 1) 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.