Решения принимаются до 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-й игрок не может сделать начальный ход, следовательно второй является победителем.
Задание подготовили Й.Ентин,, В.Мельник, Г.Непомнящий, Ю.Пасихов