시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 (추가 시간 없음) 256 MB158594039.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을 출력하시오.

서브태스크 1 (30점)

행렬의 크기가 $5\leq n\leq 50$인 경우만 주어진다.

서브태스크 2 (70점)

추가 제한 조건이 없다.

예제 입력 1

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

예제 출력 1

3

예제 입력 2

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

예제 출력 2

0

출처

University > 광주과학기술원 > 광주과학기술원 HOLICS 알고리즘 대회 2018 F번

  • 문제를 만든 사람: cea
  • 문제의 오타를 찾은 사람: jh05013

채점 및 기타 정보

  • 예제는 채점하지 않는다.