Ліміт часу: 1 с
Ліміт пам'яті: 64 Мбт
Приватний підприємець і податковий інспектор грають в наступну гру: Є матриця NxN в яку записані цілі числа P (0<=P<=1000000) - прибутки підприємця за певні періоди. Далі кожен гравець по черзі викреслює останній рядок, або останній стовпчик матриці, при умові, що сума чисел в цьому рядку/стовпчику парна. Учасник, який не зможе зробити хід (все вже викреслено, або сума в останньому рядку та останньому стовпчику непарна) програє гру. Напишіть програму, яка визначить хто виграє гру, при найоптимальнішій грі обох гравців.
Вхідні дані:
Перше число - T (T<=10)- кількість описів ігор. Далі йде T блоків. Кожен блок описує відповідну гру. Перше число блоку - N - розмір матриці. (0<N<=1000), далі міститься N*N чисел - матриця гри.
Вихідні дані:
У вихідний потік запишіть T чисел, по одному на кожен рядок. 1 - якщо виграє перший гравець, і 0 - якщо перший гравець програє.
Вхідні дані:
Перше число - T (T<=10)- кількість описів ігор. Далі йде T блоків. Кожен блок описує відповідну гру. Перше число блоку - N - розмір матриці. (0<N<=1000), далі міститься N*N чисел - матриця гри.
Вихідні дані:
У вихідний потік запишіть T чисел, по одному на кожен рядок. 1 - якщо виграє перший гравець, і 0 - якщо перший гравець програє.
Приклад вхідних та вихідних даних.
| Приклад вхідних даних: | Приклад вихідних даних: |
| 2 3 7 9 4 1 3 3 9 4 1 3 5 5 0 1 7 1 2 2 5 | 1 0 |
Задача B-Обласна олімпіада
Ліміт часу: 1 с
Ліміт пам'яті: 64 Мбт
Обласна олімпіада з інформатики, це не лише випробування для учасників. Кожного разу перед командою журі постає ціла низка важких завдань. Деякі з них відомі заздалегідь, деякі виникають в процесі олімпіади, і потребують негайного рішення. Команда журі складається з N людей, кожен з яких може виконувати певний набір функцій з різною результативністтю. Наприклад KAV найкраще може скласти тести до задач, SSF - найкраще підходить на функцію голови експертної комісії. PSS - найкраще розбирається в комп'ютерних мережах і недопустить можливість доступу з комп'ютера одного учасника до іншого, тощо. Кожному члену журі можна призначити лише одну роботу. Найголовніша задача кожної олімпіади полягає в тому, щоб голова журі RVA розподілив обов'язки між членами журі найкращим чином.
Вхідні дані:
В першому рядку міститься ціле число N (1<n<=100)- кількість членів журі. Далі йде N*N чисел які описують матрицю робіт. Число Aij (1<=Aij<=10000) - показує, з якою ефективністтю член журі під номером i виконає роботу під номером j.
Вихідні дані:
Виведіть єдине число - найбільшу сумарну ефективність, яку можна досягнути для заданої олімпіади
Приклад вхідних та вихідних даних.
| Приклад вхідних даних: | Приклад вихідних даних: |
| 3 3 6 8 7 1 9 3 5 6 | 20 |
Задача C-Кодекс
Ліміт часу: 1 с
Ліміт пам'яті: 64 Мбт
В деякій країні парламент вирішив прийняти інформаційний кодекс, яким дуже сильно обмежував використання інтернету. Відтепер перевіряючий зможе коли завгодно читати чужу електронну пошту, на відвідування сайтів необхідно брати дозволи, і крім того користувачам становлено річний ліміт завантаженої інформації 1 Гб. Звісно це дуже обурило користувачів інтернету, і вони вийшли на мітинг, мітингували довго і нудно, і зрозуміли, що необхідно змінити тактику боротьби за свободу Інтернета. В координаційному штабі інтернетчиків визрів план цифрового звільнення, що передбачав хакерський взлом комп'ютерів парламенту. Як відомо комп'ютери в парламенті цієї країни об'єднані в специфічну мережу з наступними характеристиками:
1) Кожен комп'ютер з'єднаний з певною кількісттю інших, і може передати їм інформацію;
2) Між будь-якими двома комп'ютерами є лише 1 шлях передачі інформації;
3) Отримавши доступ до комп'ютера можна взяти під контроль його і всі комп'ютери з якими він безпосередньо з'єднаний.
Задача координаційного штабу інтернетчиків, визначити найменшу кількість комп'ютерів, які треба взламати, аби отримати повний доступ до мережі парламенту.
Вхідні дані:
У першому рядку число N - кількість комп'ютерів в парламенті. У другому рядку число M - кількість міжкомп'ютерних з'єднань. В кожному з наступних M рядків міститься по 2 числа - номера комп'ютерів у з'єднанні. (1<N<=10000)
1) Кожен комп'ютер з'єднаний з певною кількісттю інших, і може передати їм інформацію;
2) Між будь-якими двома комп'ютерами є лише 1 шлях передачі інформації;
3) Отримавши доступ до комп'ютера можна взяти під контроль його і всі комп'ютери з якими він безпосередньо з'єднаний.
Задача координаційного штабу інтернетчиків, визначити найменшу кількість комп'ютерів, які треба взламати, аби отримати повний доступ до мережі парламенту.
Вхідні дані:
У першому рядку число N - кількість комп'ютерів в парламенті. У другому рядку число M - кількість міжкомп'ютерних з'єднань. В кожному з наступних M рядків міститься по 2 числа - номера комп'ютерів у з'єднанні. (1<N<=10000)
Вихідні дані:
Єдине число - мінімальна кількість комп'ютерів, яку необхідно взламати.
Приклад вхідних та вихідних даних.
| Приклад вхідних даних: | Приклад вихідних даних: |
| 8 7 1 2 2 3 3 4 4 5 2 6 4 7 4 8 | 2 |
