Canadian Computing Olympiad: 2018 Day 1, Problem 2

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

There is a game with ~N~ levels numbered from ~1~ to ~N~. There are two characters, both are initially at level ~1~. For ~i < j~, it costs ~A_{i,j}~ coins to move a character from level ~i~ to level ~j~. It is not allowed to move a character from level ~i~ to level ~j~ if ~i > j~. 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 ~X~ but the minimum number of coins needed is ~Y~. To show how wrong JP's solution is, help Troy find an input ~N~ and ~A_{i,j}~ such that ~\dfrac X Y~ 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 ~N~ ~(2 \le N \le 100)~.

Then print ~N-1~ lines; the ~i~-th line should contain ~N-i~ integers ~A_{i,i+1}, \dots, A_{i,N}~ ~(1 \le A_{i,j} \le 100)~.

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 ~X~ but the minimum number of coins needed is ~Y~. Then you will receive ~\left\lceil \min\left(25,\dfrac{X}{4Y}\right) \right\rceil~ points where ~\lceil Z \rceil~ is the smallest integer that is not less than ~Z~.

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 ~(1)+(2+7+5) = 15~ coins. JP's solution returns 18. Thus ~\dfrac{X}{4Y} = \dfrac{18}{4 \times 15} = 0.3~, so this output will receive ~\lceil 0.3 \rceil = 1~ point.