4.5. Маршрут (6)

Дана матрица N  N, заполненная положительными числами. Путь по матрице начинается в левом верхнем углу. За один ход можно пройти в соседнюю по вертикали или горизонтали клетку (если она существует). Нельзя ходить по диагонали, нельзя оставаться на месте. Требуется найти максимальную сумму чисел, стоящих в клетках по пути длиной K клеток (клетку можно посещать несколько раз).

Ограничения: 2 ≤ N ≤ 20, элементы матрицы имеют значения от 1 до 9999, 1 ≤ K ≤ 20, все числа целые, время 2 с.

Ввод из файла INPUT.TXT. В первой строке находятся разделенные пробелом числа N и K. Затем идут N строк по N чисел в каждой.

Вывод в файл OUTPUT.TXT. Вывести в первой строке максимальную сумму, а во второй – соответствующий маршрут в виде координат клеток.

Пример

Ввод

5 7

1 1 1 1 1

1 1 3 1 9

1 1 6 1 1

1 1 3 1 1

1 1 1 1 1

Вывод

21

(1,1) (1,2) (1,3) (2,3) (3,3) (4,3) (3,3)

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

4.6. Золотоискатели (6)

За два года беспрерывной работы артель золотоискателей "Вперед к капитализму!", состоящая из трех человек, добыла N самородков. Несмотря на то, что до конца вахты оставался еще целый год, один из золотоискателей решил уехать - на Большой Земле у него родился сын. Артельщики решили выдать отъезжающему ровно третью часть добытого золота.

Вам надо написать программу, которая находит набор самородков, вес которого составляет третью часть от веса всего добытого золота, либо определить что это невозможно.

Ввод из файла INPUT.TXT. В первой строке записано целое число N - количество добытых самородков (1  N  500). Во второй строке заданы через пробел N целых чисел M_i (1  M_i  1000) - веса добытых самородков.

Вывод в файл OUTPUT.TXT. Если набор составить возможно, то в первой строке выведите K - количество самородков в наборе, а затем K чисел, задающих номера самородков, входящих в набор. Если существует несколько ответов, то выведите любой из них. Если набор составить невозможно, то выведите число 0.

Примеры

Ввод 1 Ввод 2

8 3

1 3 4 1 2 5 1 1 1 5 6

Вывод 1 Вывод 2

2 0

6 8

4.7. Скобочки (7)

Найти количество правильных скобочных форм из скобок "(” и ”)” заданной глубины. Задаются два целых числа: N – число открывающих скобок (т.е. 2N – длина выражения) и k – глубина (1 ≤ k ≤ N ≤ 50).

Ввод из файла INPUT.TXT. В единственной строке находятся числа N и k через пробел.

Вывод в файл OUTPUT.TXT. Вывести одно число - количество различных значений сумм.

Примеры

Ввод 1 Ввод 2

3 2 37 23

Вывод 1 Вывод 2

3 203685956218528

Подсказка. Обозначим через S_i количество форм с текущей глубиной k в позициях от 1 до i при условии, что большей глубины не было. Тогда для каждой такой формы существует S_{2N - i} способов правильного закрытия скобок. Значит, выражение S_iS_{2N - i} дает количество правильных форм, когда глубина k достигается в i-й позиции. Может показаться, что если известны все значения S_i, то достаточно просуммировать такие произведения для всех допустимых значений i, то есть при k ≤ i ≤ 2N - k. Это не совсем так, поскольку некоторые формы могут повторяться. Как с этим бороться?

4.8. Булева функция (6)

Недавно на уроке информатики ученики одного из классов изучили булевы функции. Напомним, что булева функция f сопоставляет значениям двух булевых аргументов, каждый из которых может быть равен 0 или 1, третье булево значение, называемое результатом. Для учеников, которые выразили желание более подробно изучать эту тему, учительница информатики на дополнительном уроке ввела в рассмотрение понятие цепного вычисления булевой функции f.

Если задана булева функция f и набор из N булевых значений a₁, a₂, ..., a_N , то результат цепного вычисления этой булевой функции определяется следующим образом:

• если N = 1, то он равен a₁;

• если N > 1, то он равен результату цепного вычисления булевой функции f для набора из (N–1) булевого значения f(a₁,a₂), a₃, …, a_N, который получается путем замены первых двух булевых значений в наборе из N булевых значений на единственное булево значение – результат вычисления функции f от a₁ и a₂.

Например, если изначально задано три булевых значения: a₁ = 0, a₂ = 1, a₃ = 0, а функция f – ИЛИ (OR), то после первого шага получается два булевых значения (0 OR 1) и 0, то есть 1 и 0. После второго (и последнего) шага получается результат цепного вычисления, равный 1, так как 1 OR 0 = 1.

В конце дополнительного урока учительница информатики написала на доске булеву функцию f и попросила одного из учеников выбрать такие N булевых значений a_i, чтобы результат цепного вычисления этой функции был равен единице. Более того, она попросила найти такой набор булевых значений, в котором число единиц было бы как можно большим.

Требуется написать программу, которая решала бы поставленную учительницей задачу. Использовать подход динамического программирования.

Ввод из файла INPUT.TXT. Первая строка содержит одно натуральное число N (2 ≤ N ≤ 100 000). Вторая строка содержит описание булевой функции в виде четырех чисел, каждое из которых – ноль или единица. Первое из них есть результат вычисления функции в случае, если оба аргумента – нули, второе – результат в случае, если первый аргумент – ноль, второй – единица, третье – результат в случае, если первый аргумент – единица, второй – ноль, а четвертый – в случае, если оба аргумента – единицы.

Вывод в файл OUTUT.TXT. Необходимо вывести строку из N символов, определяющих искомый набор булевых значений a_i с максимально возможным числом единиц. Если ответов несколько, требуется вывести любой из них. Если такого набора не существует, выведите в выходной файл слово No.

Примеры

Ввод 1 Ввод 2 Ввод 3

4 5 6

0110 0100 0000

Вывод 1 Вывод 2 Вывод 3

1011 11111 No

Пояснения к примерам

В первом примере процесс вычисления цепного значения булевой функции f происходит следующим образом:

1011 → 111 → 01 → 1

Во втором примере вычисление цепного значения булевой функции f происходит следующим образом:

11111 → 0111 → 111 → 01 → 1

В третьем примере получить цепное значение булевой функции f, равное 1, невозможно.

7. Заметание