오답
시간 제한1초메모리 제한512 MB
두 캐릭터를 쓰는 그리디 풀이의 결과가 실제 최솟값에서 최대한 멀어지도록 비용 행렬을 만들어, 그 비율을 최대화하는 입력을 구성한다.
문제
Troy는 프로그래밍 대회에 다음과 같은 문제(제목: WA)를 출제했다.
1번부터 N번까지 번호가 붙은 N개의 레벨이 있는 게임이 있다. 두 캐릭터가 있고, 둘 다 처음에는 레벨 1에 있다. i < j일 때 캐릭터를 레벨 i에서 레벨 j로 옮기는 데 Ai,j개의 동전이 든다. i > j이면 캐릭터를 레벨 i에서 레벨 j로 옮길 수 없다. 게임에서 이기려면 레벨 1을 제외한 모든 레벨을 정확히 한 캐릭터가 방문해야 한다. 이길 때 필요한 동전의 최소 개수는 얼마인가?
JP는 참가자이고, 다음과 같은 파이썬 풀이를 제출했다.
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의 풀이가 틀렸다고 확신한다. WA의 어떤 입력에 대해 JP의 풀이가 X를 반환하지만 필요한 동전의 최소 개수는 Y라고 하자. JP의 풀이가 얼마나 틀렸는지 보여주기 위해, X/Y가 최대가 되는 입력 N과 Ai,j를 Troy가 찾도록 도와라.
입력
입력은 없다.
출력
WA의 입력을 다음 형식으로 출력한다.
첫째 줄에 정수 N (2 ≤ N ≤ 100)을 출력한다. 이어서 N−1개의 줄을 출력하는데, i번째 줄에는 N−i개의 정수 Ai,i+1, ..., Ai,N (1 ≤ Ai,j ≤ 100)을 출력한다. 출력 형식이 올바르지 않으면 채점기에서 예제 테스트에 대해 오답 판정을 받고 0점을 얻는다.
그렇지 않고, 입력에 대해 JP의 풀이가 X를 반환하지만 필요한 동전의 최소 개수가 Y라면 X/(4Y)점을 받는다.