Визначник#762

Визначник

1 секунда

64 мегабайти

Складна

Гра Визначник проводиться двома гравцями на $3 \times 3$ 3 \times 3 полі. Гравці по черзі вписують одну цифру у порожні клітини, причому кожна цифра використовується лише один раз.

Наприклад, у певній позиції поточний гравець може обирати з цифр $1, 2, 4, 5, 6, 7, 8$ 1, 2, 4, 5, 6, 7, 8 для розміщення у будь-яку порожню клітину.

Після заповнення всіх клітин обчислюється визначник $D$ поля за формулою:

D = A_{11} A_{22} A_{33} + A_{12} A_{23} A_{31} + A_{13} A_{21} A_{32} - A_{11} A_{23} A_{32} - A_{12} A_{21} A_{33} - A_{13} A_{22} A_{31}

D = A_{11}A_{22}A_{33} + A_{12}A_{23}A_{31} + A_{13}A_{21}A_{32} - A_{11}A_{23}A_{32} - A_{12}A_{21}A_{33} - A_{13}A_{22}A_{31}

Якщо визначник більший за нуль ( $D > 0$ D > 0), перемагає гравець, який почав гру. Якщо визначник менший за нуль ( $D < 0$ D < 0), перемагає другий гравець. Якщо визначник дорівнює нулю ( $D = 0$ D = 0), гра завершується внічию.

Ваше завдання — визначити результат гри для заданої позиції, якщо обидва гравці діють оптимально.

Вхідні дані

Вхід складається з трьох рядків, у кожному з яких записані числа, розділені пробілами, що представляють поточний стан клітин поля. Клітина з $0$ означає, що вона порожня, будь-яке інше число вказує на вже записану цифру.

Вихідні дані

У першому рядку виведіть результат гри: $0$ — якщо буде нічия, $1$ — якщо переможе гравець, який почав гру (увага: це не обов'язково гравець, чий хід зараз), або $2$ — якщо переможе гравець, який ходив другим.

Приклади

Приклад 1