시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 10 0 0 0.000%

문제

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 Ai,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 Ai,j such that X/Y is maximized.

입력

There is no input.

출력

Print an input to WA in the following format:

On the first line, print one integer N (2 ≤ N ≤ 100). Then print N−1 lines; the i-th line should contain N−i integers Ai,i+1, · · ·, Ai,N (1 ≤ Ai,j ≤ 100). If your output is not 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 min(25, X/(4Y)) points.

예제 입력 1


						

예제 출력 1

5
1 2 3 4
10 9 8
7 6
5

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 X/(4Y) = 18/(4×15) = 0.3, so this output will receive 0.3 point.

채점

  • 25점 이상을 획득해야 를 받는다.
  • 예제는 채점하지 않는다.