Завдання 2-го туру NetOI-2016

Розв'язки приймаються до 0 годин 19 грудня 2016 р.

Задача Bushways.  Великий Селекціонер (ВС) завершує роботу, він хоче виростити спеціальний  кущ для розведення шовкопряда. Кущ кращий від дерева: в нього буде багато гілок! Від кореня відходитимуть дві гілки (перший рівень розгалужень), від кожної з них – три (другий рівень), від кожної з цих трьох – по чотири (третій рівень), тобто на кожному наступному розгалуженні виростає на одну гілку більше. Оскільки кущ буде щільно вкритий листям, гусениці шовкопряду одержуватимуть достатню кількість їжі на коротких шляхах між розгалуженнями. Треба з’ясувати, скільки буде на кущі різних шляхів з довжиною t ділянок (ділянка – відстань між двома сусідніми розгалуженнями, у ідеального куща довжини всіх ділянок однакові, і їжі на всіх ділянках порівну).   Шлях шовкопряда проходить через кожну гілку один раз (вдруге нічого їсти!), а  стрибки через гілку неможливі (це ж гусениці!). Будь-які два шляхи відрізняються не менше ніж одною гілкою, якщо визначено шлях в один бік по гілці, шлях в інший бік не можливий (знову ж, не буде що їсти!) . Різні гусениці можуть мати спільні гілки у складі своїх шляхів (вони дуже повільно пересуваються і не чинитимуть перешкод одна одній, а їжа встигне вирости).

Технічні умови. Програма Bushways  зчитує з пристрою стандартного введення кількість гілок, що їх зможе «об’їсти» гусениця за своє життя (це 2 або 3) та кількість рівнів розгалужень  n – від 1 до 18 включно.

Програма виводить на пристрій стандартного виведення  результат – кількість різних шляхів гусениці. Зрозуміло, що починати свій маршрут гусениця може як з кореня куща, так і з будь-якого розгалуження чи верхівки куща.

Приклади                                               

Введення  2 3                   Виведення                73

Введення  3 2                   Виведення                6

Задача Channels.  Фермер Василь вирішив з'єднати свої три ставки каналами. У Василя є мапа його володінь, яка задається двовимірним масивом символів (N*M), де символ 'X' позначає клітинку, яка належить ставку. До того ж два символи 'X' належать одному і тому ж ставку, якщо вони є сусідніми по вертикалі або горизонталі (клітинки по діагоналі не є сусідніми).  Розглянемо приклад: 

 ...............

..XXXX....XXX..

..XXXXX.....X..

..XX.......XXX.

........XXXXX..

.ХXXX....XXX...
З метою економії Василь хоче збудувати канали сумарно мінімальної довжини. В наведеному вище прикладі, йому вигідно збудувати в 4 клітинках, вони позначені символом ‘*’ на рис. нижче.

...............

..XXXX....XXX..

..XXXXX.....X..

..XX..*....XXX.

..*...**XXXXX..

.ХXXX....XXX...
Допоможіть Василю визначити мінімальну сумарну довжину каналів. 

Технічні умови. Програма Channels читає з пристрою стандартного введення два цілих числа у першому рядку N, а в другому  M (1 ≤ N, M ≤ 50). Наступні N рядків описують мапу. Кожен рядок містить рядок з M символів “X” або “.”. Гарантується що у вхідних даних завжди 3 ставки.   Програма виводить на пристрій стандартного виведення єдине число – шукану величину. 

Приклад

Задача SSEQ. Нехай задано масив з цілих чисел a розміру n. Вам необхідно знайти довжину найбільшої неспадної послідовності що може містити лише числа t - 1, t, t + 1 для деякого наперед заданого t.

Технічні умови. Програма SSEQ читає з пристрою стандартного введення 2 числа - n, t (1<=n<=10⁶, -10⁹<=t<=10⁹)

 Другий рядок містить n чисел - елементи масиву a (-10⁹<=a_i<=10⁹). Програма виводить на пристрій стандартного виведення єдине число - відповідь на питання задачі.

Приклади

Введення

 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

Завдання підготували Й.Ентін, А.Зуєв, В.Мельник, Г.Непомнящий, І.Порубльов, Ю.Пасіхов