1. Задания ІІІ тура NetOI-2014 (05.01-30.01) 2015 г.

Решения принимаются до 0 часов 31 января 2015 г.

Задача Diode2. Проблема энергосбережения является очень актуальной. И в этом смысле перспективными кажутся светодиодные светильники. Имеется светильник в виде прямоугольной матрицы NxM. В каждой ячейке находится светодиод, который может светиться или нет. Генеральный Конструктор (ГК) может избрать какую-то ячейку и сделать переключение - поменять состояние всех светодиодов в ее строке и ее столбце на противоположное. Таким образом, за одно переключение изменит свое состояние на противоположное N+M-1 светодиод. Выполняя такую операцию несколько раз, ГК хочет достичь состояния, чтобы все светодиоды светились.

Технические условия. Программа Diode2 читает с устройства стандартного ввода в первой строке 2 числа N и M (2<=N, M<=1000), а дальше N строк по М чисел в каждом - 0 или 1 через пробел: 0, если соответствующий светодиод светится, и 1 - если нет. Программа выводит на устройство стандартного вывода единственное число - минимальное количество переключений. Гарантируется, что N и M - четные числа.

Примеры

Задача Trainers. Учительница Галина Петровна и ее бывший ученик, а в настоящее время студент Вася готовят N школьников для участия в олимпиаде по информатике. Они подготовили по одной задаче и планируют объяснить их каждому школьнику. Из педагогических соображений они не могут работать вдвоем с одним школьником одновременно, и ни один из них одновременно не может работать с несколькими школьниками. Каждому школьнику требуется определенное время, чтобы понять и реализовать задачу. Найдите минимальное время от начала занятий, через которое все школьники будут уметь решать обе задачи.

Технические условия. Программа Trainers читает с устройства стандартного ввода число N - количество школьников, а дальше в той же строке через пробелы N целых чисел, где i- е число - время, необходимое i- му школьнику, чтобы понять и реализовать алгоритм (как первый, так и второй). Все входные данные принадлежат интервалу от 1 до 3·10⁵. Программа выводит на устройство стандартного вывода единственное число - искомую величину.

Примеры

Комментарии к примерам:

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).

Примеры

Задача Game2015. Два игрока играют в такую игру. Есть набор из N чисел, известных участникам. Первый должен найти наименьшее из них и увеличить его настолько, чтобы оно стало равным следующему за ним (по возрастанию) числу. Второй игрок действует наоборот: находит наибольшее число и уменьшает его настолько, чтобы оно стало равным следующему по убыванию числу. Игра длится, пока есть хотя бы 3 различных числа. Проигрывает тот игрок, который уже не может сделать очередной ход. Зная, что первый игрок всегда начинает игру, узнайте, кто победитель в игре и найдите значения наименьшего и наибольшего чисел, когда игра закончена.

Технические условия. Программа Game2015 читает с устройства стандартного ввода целое число N (1<=N<=10⁵) - количество чисел, а дальше через пробелы N целых чисел, каждое из которых меньше или равно 10⁵. Программа выводит на устройство стандартного вывода 1, если побеждает первый игрок, 2 - если второй, а дальше в той же строке через пробелы 2 числа - наименьшее и наибольшее числа, когда игра завершится.

Примеры

Комментарий. В первом примере 1-й игрок не может сделать начальный ход, следовательно второй является победителем.