Пальці#3690
У відомій грі "камінь-ножиці-папір" діють прості правила. Кожен з двох гравців обирає одне з трьох положень руки: камінь, ножиці або папір. Після цього обидва гравці одночасно показують свої вибори, і переможець визначається за такими правилами: якщо вибори співпали (наприклад, камінь-камінь), то це нічия; інакше камінь перемагає ножиці, ножиці перемагають папір, а папір перемагає камінь. У деякій модифікації гри беруть участь більше предметів, і виникає питання, чи є така гра справедливою. Тобто, чи не виявляється, що деякі положення мають перевагу над іншими. Вважатимемо гру справедливою, якщо кожне положення має нічию з самим собою, виграє рівно у половини інших положень і програє іншій половині. Дано опис гри, потрібно визначити мінімальну кількість пар положень, для яких потрібно змінити напрямок виграшу, щоб гра стала справедливою.
Непарне число (1 \le N \le 100) - кількість предметів. Далі йде матриця N \times N, що описує результати для різних пар предметів. означає виграш, - нічию, - програш. На головній діагоналі завжди стоять . Якщо в деякій комірці стоїть , то в обов'язково стоїть .
Мінімальна кількість пар предметів, для яких потрібно змінити переможця, щоб гра стала справедливою.
Приклад 1