Розв'язки приймаються до 0 годин 31 січня 2015 р.
Задача Diode2. Проблема енергозбереження є дуже актуальною. І в цьому сенсі перспективними видаються світлодіодні світильники. Хай ми маємо світильник у вигляді прямокутної матриці NxM. У кожній комірці знаходиться світлодіод, який може світитися або ні. Генеральний Конструктор (ГК) може обрати якусь комірку і зробити перемикання - поміняти стан усіх світлодіодів у її рядку та її стовпці на протилежний. Таким чином, за одне перемикання змінять свій стан на протилежний N+M-1 світлодіод. Виконуючи таку операцію певну кількість разів, ГК хоче досягнути стану, аби всі світлодіоди світилися.
Технічні умови. Програма Diode2 читає з пристрою стандартного введення у першому рядку 2 числа N і M (2<=N,M<=1000), а далі N рядків по М чисел у кожному - 0 чи 1 через пропуск: 0, якщо відповідний світлодіод світиться, і 1 – якщо ні. Програма виводить на пристрій стандартного виведення єдине число – мінімальну кількість перемикань. Гарантується, що N і M – парні числа.
Приклади
| Введення | Виведення |
|
2 2 |
2 |
|
4 4 |
9 |
Задача Trainers. Вчителька Галина Петрівна та її колишній учень, а нині студент Вася готують N школярів для участі в олімпіаді з інформатики. Вони підготували по одній задачі і планують пояснити їх кожному школяру. З педагогічних міркувань вони не можуть працювати вдвох з одним школярем одночасно, і жоден із них одночасно не може працювати з кількома школярами. Кожен школяр потребує певний час, аби зрозуміти та реалізувати задачу. Знайдіть, через який мінімальний час від початку занять усі школярі вмітимуть розв'язувати обидві задачі.
Технічні умови Програма Trainers читає з пристрою стандартного введення число N - кількість школярів, а далі у тому ж рядку через пропуски N цілих чисел, де i-е число - час, необхідний для того аби зрозуміти та реалізувати алгоритм (як перший, так і другий), i-му школяру. Всі вхідні дані належать інтервалу від 1 до 3·105 Програма виводить на пристрій стандартного виведення єдине число - шукану величину.
Приклади
| Введення | Введення | Введення |
| 3 2 2 2 | 3 4 1 2 | 4 1 3 2 1 |
| Виведення | Виведення | Виведення |
| 6 | 8 | 7 |
Комментарі до прикладів:
1. Кожен школяр потребує 2 одиниці часу, аби зрозуміти та реалізувати алгоритм. Один з можливих графіків занять: Галина Петрівна пояснює свою задачу послідовно школярам 1, 2, 3, а Вася – 3, 1, 2.
2: Один з оптимальних графіків: Галина Петрівна працює з школярами 2, 3 та 1 відповідно, але з паузою в 1 одиницю часу між 3 і 1. Вася буде працювати зі школярами 1, 3, 2 без пауз.
Задача Lettline. До порожнього рядка додаємо першу літеру латинського алфавіту. Потім рядок «подвоюємо» та додаємо наступну літеру алфавіту, одержавши рядок ‘aab’. Далі повторюємо ці дії – до появи у рядку заданої літери Finish. Зокрема, якщо Finish=’c’, буде рядок ‘aabaabc’. Яка літера буде розташована на позиції номер N (відрахунок позицій – зліва направо, від початку рядка, номер першого в рядку символу 1)?
Технічні умови. Програма Lettline читає з пристрою стандартного введення інформації N, а у новому рядку – останню додану літеру Finish. Усі літери – рядкові. Програма виводить літеру, яка знаходиться на позиції номер N. Якщо такої позиції у послідовності немає, програма виводить 0.
Приклади
Введення
27
d
Виведення
0
Введення
3
e
Виведення
b
Задача Azs. У країні є N міст, які з’єднані між собою дорогами так, що із кожного міста у кожне місто можна потрапити лише одним маршрутом, а на кожній дорозі, там де вона входить в місто збудовано АЗС (тобто, якщо місто сполучене з іншими містами трьома дорогами, то АЗС теж 3). Король країни вирішив, що бюджет дозволяє побудувати ще М нових міст, і, відповідно, М доріг. Причому початкові умови про один маршрут між будь-якою парою міст та кількість АЗС відповідно кількості доріг потрібно було зберегти. Придворний програміст написав програму, яка може рахувати добуток кількостей усіх АЗС (тобто знаходить число (АЗС(першого_міста) х АЗС(другого_міста) х … АЗС(N-1_міста) х АЗС (N_міста) ). Допоможіть Придворному Будівельному Управлінню побудувати міста і дороги таким чином, аби результатом роботи програми Придворного Програміста було максимальне число.
Технічні умови. Програма Azs читає із пристрою стандартного введення у першому рядку два цілих числа N і M. Далі N-1 рядок по два числа (1<=a;b<=N) – номери міст, що з’єднані дорогою. Програма виводить максимально можливий добуток кількостей АЗС у кожному з міст по модулю 1000000007. (2<=N<=100000, 0<=M<=100000).
Приклади
| Введення | Виведення |
| 2 1 1 2 |
2 |
| 2 0 1 2 |
1 |
Задача Game2015. Два гравці грають у таку гру. Є набір з N чисел, які відомі учасникам. Перший повинен знайти найменше з них і збільшити його настільки, щоб воно стало рівним наступному за ним (за зростанням) числу. Другий гравець діє навпаки: знаходить найбільше число і зменшує його настільки, аби воно стало рівним наступному за спаданням числу. Гра триває, поки є хоча б 3 різних числа. Програє той гравець, який вже не може зробити черговий хід. Знаючи, що перший гравець завжди розпочинає гру, дізнайтеся, хто переможець в грі і значення найменшого та найбільшого числа, коли гру закінчено.
Технічні умови. Програма Game2015 читає з пристрою стандартного введення ціле число N (1<=N<=105) – кількість чисел, а далі через пропуски N цілих чисел, кожне з яких менше або дорівнює 105. Програма виводить на пристрій стандартного виведення 1, якщо перемагає перший гравець, 2 – якщо другий, а далі в тому ж рядку через пропуски 2 числа - найменше та найбільше число, коли гра завершиться.
Приклади
|
Введення |
Введення |
Введення |
|
3 3 3 3 |
4 3 1 2 1 |
7 2 1 3 3 5 4 1 |
|
Виведення |
Виведення |
Виведення |
|
2 3 3 |
2 1 2 |
2 2 3 |
Коментар. У першому прикладі 1-й гравець не може зробити початковий хід, отже другий є переможцем.
Завдання підготували Й.Ентін,, В.Мельник, Г.Непомнящий, Ю.Пасіхов