Задание 2-го тура NetOI-2016
Решения принимаются до 0 часов 19 декабря 2016 г.
Задача Bushways. Великий Селекционер (ВС) завершает работу, он хочет вырастить специальный куст для разведения шелкопряда. Куст лучше дерева: у него будут много веток! От корня будут отходить две ветки (первый уровень разветвлений), от каждой из них - три (второй уровень), от каждой из этих трех - по четыре (третий уровень), то есть на каждом следующем разветвлении вырастает на одну ветку больше. Поскольку куст будет плотно покрыт листьями, гусеницы шелкопряда будут получать достаточное количество еды на коротких путях между разветвлениями. Необходимо выяснить, сколько будет на кусте разных путей с длиной t участков (участок - расстояние между двумя соседними разветвлениями, у идеального куста длины всех участков одинаковые, и еде на всех участках поровну). Путь шелкопряда проходит через каждую ветку один раз (во второй раз нечего есть!), а прыжки через ветку невозможны (это же гусеницы!). Любые два пути отличаются не меньше чем одной веткой, если определен путь в одну сторону по ветке, путь в другую сторону невозможен (опять же, не будет что есть!). Разные гусеницы могут иметь общие ветки в составе своих путей (они очень медленно передвигаются и не будут препятствовать друг другу, а еда успеет вырасти).
Технические условия. Программа Bushways считывает с устройства стандартного ввода количество веток, которые сможет «объесть» гусеница за свою жизнь (это 2 либо 3) и количество уровней разветвлений n – от 1 до 18 включительно.
Программа выводит на устройство стандартного вывода результат – количество различных путей гусеницы. Разумеется, что начинать свой маршрут гусеница может как с корня куста, так и с любого разветвления или верхушки куста.
Примеры
Ввод 2 3 Вывод 73
Ввод 3 2 Вывод 6
Задача Сhannels. Фермер Василий решил соединить свои три пруда каналами. У Василия есть карта его владений, которая задается двухмерным массивом символов (N*M), где символ 'X' помечает клеточку, которая принадлежит пруду. К тому же два символа 'X' принадлежат одному и тому же пруду, если они являются соседними по вертикали или горизонтали (клеточки по диагонали не являются соседними). Рассмотрим пример:
...............
..XXXX....XXX..
..XXXXX.....X..
..XX.......XXX.
........XXXXX..
.ХXXX....XXX...
С целью экономии Василий хочет построить каналы суммарно минимальной длины. В вышеприведенном примере, ему выгодно построить в 4 клеточках, они обозначены символом '*' на рис. ниже.
...............
..XXXX....XXX..
..XXXXX.....X..
..XX..*....XXX.
..*...**XXXXX..
.ХXXX....XXX...
Помогите Василию определить минимальную суммарную длину каналов.
Технические условия. Программа Сhannels читает с устройства стандартного ввода два целых числа в первой строке N, а во второй M (1 ≤ N, M ≤ 50). Следующие N строк описывают карту. Каждая строка содержит строку из M символов “X” либо “.”. Гарантируется, что во входных данных всегда 3 пруда. Программа выводит на устройство стандартного вывода единственное число – искомую величину.
Пример
|
Ввод |
Вывод |
|
6 15 ............... ..XXXX....XXX.. ..XXXXX.....X.. ..XX.......XXX. ........XXXXX.. .ХXXX....XXX... |
4 |
Задача SSEQ. Пусть задано массив из целых чисел a размером n. Вам необходимо найти длину наибольшей неубывающей последовательности, содержащей только числа t - 1, t, t + 1 для некоторого наперед заданного t.
Технические условия. Программа SSEQ читает с устройства стандартного ввода 2 числа - n, t (1<=n<=106, -109<=t<=109)
Вторая строка содержит n чисел - элементы массива a (-109<=ai<=109). Программа выводит на устройство стандартного вывода единственное число - ответ на вопрос задачи.
Примеры
Ввод
10 0
-1 1 -1 1 –1 1 0 -1 1 1
Вывод
6
Ввод
10 1
1 1 1 1 1 0 0 0 0 -1
Вывод
5
Ввод
10 4
3 4 4 4 4 4 3 4 5 3
Вывод
8
Задача MSL. Есть прямоугольная таблица размером N строк на М столбиков. В каждой клеточке записано целое число. По ней нужно пройти сверху вниз, начиная с любой клетки верхней строки, дальше каждый раз, переходя в одну из "нижних соседних" клеток (иными словами, из клетки с номером (i, j) можно перейти или на (i + 1, j - 1), или на (i + 1, j), или на (i + 1, j + 1) В случае j = М последний из трех описанных вариантов становится невозможным, а в случае j = 1 - первый) и закончить маршрут в какой-либо клетке нижней строки.
Напишите программу, которая будет находить максимально возможную счастливую сумму значений пройденных клеток среди всех допустимых путей. Всем известно, что счастливыми являются натуральные числа, в десятичной записи которых содержатся только счастливые цифры 4 и 7. Например, числа 47, 744, 4 является счастливыми, а 0, 5, 17, 467 такими не является. Обратите внимание, что счастливой должна быть именно сумма, а не отдельные слагаемые.
Технические условия. Программа MSL читает с устройства стандартного ввода через пробел числа N и M (1<=N,M<=12), далее з каждой из последующих N строк по M разделенных пробелом целых неотрицательных чисел (каждое содержит в десятичной записи не больше 12 цифр) – значения клеток таблицы. Программа выводит на устройство стандартного вывода единственное натуральное число – максимальную счастливую сумму либо -1, если среди маршрутов нет ни одного со счастливой суммой.
Пример
Ввод
3 4
3 0 10 10
5 0 7 4
4 10 5 4
Вывод
7
Задача MSLPRIM. Есть прямоугольная таблица размером N строк на М столбиков. В каждой клеточке записано целое число. По ней нужно пройти сверху вниз, начиная с любой клетки верхней строки, дальше каждый раз, переходя в одну из "нижних соседних" клеток (иными словами, из клетки с номером (i, j) можно перейти или на (i + 1, j - 1), или на (i + 1, j), или на (i + 1, j + 1) В случае j = М последний из трех описанных вариантов становится невозможным, а в случае j = 1 - первый) и закончить маршрут в какой-либо клетке нижней строки.
Напишите программу, которая будет находить максимально возможную счастливую сумму значений пройденных клеток среди всех допустимых путей. Всем известно, что счастливыми являются натуральные числа, в десятичной записи которых содержатся только счастливые цифры 4 и 7. Например, числа 47, 744, 4 является счастливыми, а 0, 5, 17, 467 такими не является. Обратите внимание, что счастливой должна быть именно сумма, а не отдельные слагаемые.
Технические условия. Программа MSLPRIM читает с устройства стандартного ввода через пробел числа N и M (1<=N,M<=77), далее з каждой из последующих N строк по M разделенных пробелом целых неотрицательных чисел (каждое не превышает 77) – значения клеток таблицы. Программа выводит на устройство стандартного вывода единственное натуральное число – максимальную счастливую сумму либо -1, если среди маршрутов нет ни одного со счастливой суммой.
Пример
Ввод
3 4
8 2 10 4
22 2 15 25
1 14 9 1
Вывод
44
Задание подготовили Й.Энтин, А.Зуев, В.Мельник, Г.Непомнящий, И.Порублев, Ю.Пасихов