시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 (추가 시간 없음) | 256 MB | 158 | 59 | 40 | 39.604% |
선형대수학을 수강하는 기념으로 청응이가 효원이에게 $n\times n$ 행렬 $A$를 선물해줬다. 계산하기 편하라고 모든 항은 음이 아닌 정수이며, 0이 아닌 항이 $5n$개 이하인 행렬을 줬다. 선형대수학을 수강하는 기대속에 효원이는 $A^2$을 계산해봤고, 보니 $A+A^2$은 $A$보다 0인 항의 개수가 작거나 같다는 것을 확인했다. 마찬가지로 $A+A^2+A^3$은 $A+A^2$보다 $0$인 항의 개수가 작거나 같았다. 효원이는 이런 고민에 빠지게 되었다.
"어떤 $k$가 존재해서 $A+A^2+\cdots+A^k$은 $0$인 항이 아예 없을수도 있을까? 그런 $k$가 존재한다면 최솟값은 얼마일까?"
효원이는 청응이에게 이걸 물어봤더니 "$k$가 존재한다면 Cayley-Hamilton 정리에 따라 $n$보다 작거나 같을 건데..."라는 대답을 받았다. 이 답변에 만족하지 않은 효원이를 위해, $k$가 존재하는지, 존재한다면 최솟값을 출력하는 프로그램을 작성하시오.
첫 줄에는 행렬의 크기 $n$이 주어지며, $5\leq n\leq 1,000$을 만족한다.
둘째 줄부터 $(n+1)$번째 줄에 걸쳐 $n\times n$ 행렬 $A$가 주어진다. 각 줄에는 $n$개의 정수가 공백으로 구분되어 주어지며, $(i+1)$번째 줄의 $j$번째 수가 $a_{ij}$에 해당한다. 각 항은 $0\leq a_{ij}\leq 10^9$을 만족하며, $a_{ij}$ 중 $0$보다 큰 항이 $5n$개 이하이다.
조건을 만족하는 $k$가 존재한다면 최소 $k$를 출력하시오. 조건을 만족하는 $k$가 없다면 0을 출력하시오.
행렬의 크기가 $5\leq n\leq 50$인 경우만 주어진다.
추가 제한 조건이 없다.
5 3 1 0 0 1 0 0 0 8 0 2 0 1 0 1 0 0 0 0 1 1 5 4 0 0
3
5 0 0 0 0 5 0 0 0 4 0 0 0 3 0 0 0 2 0 0 0 1 0 0 0 0
0