시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 21 | 8 | 6 | 35.294% |
영선이는 미적분학 시험을 준비하고 있다. 오늘 시험공부하고 있는 내용은 N개의 명제가 모두 동치임을 증명하는 것이다. 명제는 0번부터 N-1번까지 번호가 매겨져 있다.
모든 명제의 쌍 x와 y에 대해서, 영선이는 "x이면 y이다"를 증명할 수 있다. 하지만, 이러한 증명은 모두 서로 다른 난이도를 가지고 있다.
오늘 해볼 것은 모든 명제를 직접 또는 간접적으로 서로를 함축하고 있다는 것을 증명하는 것이다. 예를 들어, N = 3인 경우에 가능한 한 가지 방법은 0 => 1, 1 => 0, 0 => 2, 2 => 0을 증명하는 것이다. 또다른 방법으로는 0 => 1, 1 => 2, 2 => 0을 증명하는 것이다.
모든 명제를 서로 함축하고 있게 증명할 때, 가장 어려운 난이도와 쉬운 난이도의 차이의 최솟값을 구하는 프로그램을 작성하시오.
첫째 줄에 명제의 개수 N (1 ≤ N ≤ 50)이 주어진다.
둘째 줄부터 N개의 줄에는 증명의 난이도가 주어진다. i번 줄의 j번 정수는 i => j를 증명하는 난이도이다.
난이도는 0보다 크거나 같고, 150,000보다 작거나 같은 정수이고, i번째 줄의 i번째 수는 0이다.
모든 명제를 서로 함축하고 있게 증명할 때, 가장 어려운 난이도와 쉬운 난이도의 차이의 최솟값을 출력한다.
4 0 11 13 13 10 0 12 13 10 10 0 11 12 10 10 0
1
5 0 1000 1000 1000 1000 1 0 1000 1000 1000 1 1 0 1000 1000 1 1 1 0 1000 1 1 1 1 0
999
4 0 136946 89305 28946 40152 0 150000 85407 122920 110420 0 32811 2092 79717 53028 0
50771