Codeforces Round #804 (Div. 2)
23:27:07 |
Educational Codeforces Round 131 (Rated for Div. 2)
4 өдрийн дараа |
Codeforces Round #805 (Div. 3)
6 өдрийн дараа |
Codeforces Round #806 (Div. 4)
8 өдрийн дараа |
F. Шидэт матриц
хугацааны хязгаарлалт 5 секунд
санах ойн хязгаарлалт 512 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Танд $n × n$ хэмжээтэй $A$ матриц өгөгдсөн.
Хэрвээ матриц нь сөрөг биш элементүүдтэй ба бүх $i, j, k$ гурвалын хувьд тэгш хэмтэй (буюу $a_{ij} = a_{ji}$), $a_{ii} = 0$ and $a_{ij} ≤ max(a_{ik}, a_{jk})$ байвал энэ матрицыг шидэт матриц гэнэ.
Матрицыг шидэт мөн эсэхийг тодорхойл.
Оролт гаралт нь маш их хэмжээтэй байж болох тул оролт гаралтын хурдан функцүүдийг ашиглана уу. Жишээ нь: C++ хэлэнд "cin/cout"-ийн оронд "scanf/printf"-ийг ашиглах, $Java$ хэлэнд "Scanner/System.out"-ийн оронд "BufferedReader/PrintWriter"-ийг ашиглана уу.
Оролт
Эхний мөрөнд бүхэл тоон утга $n$ ($1 ≤ n ≤ 2500$) байх ба энэ нь $A$ матрицын хэмжээ юм.
Дараагийн $n$ ширхэг мөр бүрт $n$ ширхэг бүхэл тоон утга $a_{ij}$ ($0 ≤ a_{ij} < 10^{9}$) байх ба $A$ матрицын элементүүд юм.
Өгөгдсөн матриц нь заавал тэгш хэмтэй байх албагүй ба санамсаргүйгээр үүсгэгдсэн ч байж болно.
Гаралт
Хэрвээ өгөгдсөн матриц $A$ нь шидэт матриц байвал "MAGIC" гэж хэвлэ. Бусад тохиолдолд "NOT MAGIC" гэж хэвлэ.
Орчуулсан: Г.Мэндбаяр
Жишээ тэстүүд
Оролт
3 0 1 2 1 0 2 2 2 0
Гаралт
MAGIC
Оролт
2 0 1 2 3
Гаралт
NOT MAGIC
Оролт
4 0 1 2 3 1 0 3 4 2 3 0 5 3 4 5 0
Гаралт
NOT MAGIC