Динамическое программирование

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

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

Входные данные
Вводятся два числа N и M — размеры таблицы (1≤N≤20, 1≤M≤20). Затем идет N строк по M чисел в каждой — размеры штрафов в килограммах за прохождение через соответствующие клетки (числа от 0 до 100).

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

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

Входные данные
Вводится одно число N (0<=N<=30).

Выходные данные
Вывести N строк треугольника Паскаля (числа выводятся через пробел).

Люди, покупающие какие-либо билеты, часто пытаются понять, на сколько счастливый билет им попался. При этом определения счастья бывают различные. В общественном транспорте Кирова для нумерации билетов используются числа от 1 до n. Витя считает билет счастливым, если его номер делится на сумму его цифр. Помогите Вите определить количество счастливых билетов.

Входные данные
На вход подается число n (1 ≤ n ≤ 10¹²).

Выходные данные
Выведите количество счастливых билетов в диапазоне от 1 до n.

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


Входные данные

В первой строке входного файла вводится одно натуральное число 𝑁≤100 — количество ступенек.
В следующей строке вводятся 𝑁 натуральных чисел, не превосходящих 100 — стоимость каждой ступеньки (снизу вверх).

Выходные данные

Выведите одно число — наименьшую возможную стоимость прохода по лесенке.

При переработке радиоактивных материалов образуются отходы трех видов — особо опасные (тип A), неопасные (тип B) и совсем не опасные (тип C). Для их хранения используются одинаковые контейнеры. После помещения отходов в контейнеры последние укладываются вертикальной стопкой. Стопка считается взрывоопасной, если в ней подряд идет более одного контейнера типа A. Стопка считается безопасной, если она не является взрывоопасной. Для заданного количества контейнеров N
 определить число безопасных стопок.

Входные данные
Одно число 1≤N≤20.

Выходные данные
Одно число — количество безопасных вариантов формирования стопки.

Примечание
В примере из условия среди стопок длины 2 бывают безопасные стопки типов AB, AC, BA, BB, BC, CA, CB и CC. Стопки типа AA являются взрывоопасными.

При переработке радиоактивных материалов образуются отходы двух видов — особо опасные (тип A) и неопасные (тип B). Для их хранения используются одинаковые контейнеры. После помещения отходов в контейнеры последние укладываются вертикальной стопкой. Стопка считается взрывоопасной, если в ней подряд идет более одного контейнера типа A. Стопка считается безопасной, если она не является взрывоопасной. Для заданного количества контейнеров N
 определить количество возможных типов безопасных стопок.

Входные данные
Одно число 1 ≤ N ≤ 20.

Выходные данные
Одно число — количество безопасных вариантов формирования стопки.

Примечание
В примере из условия среди стопок длины 2 бывают безопасные стопки типов AB, BA и BB. Стопки типа AA являются взрывоопасными.

Определите количество последовательностей из нулей и единиц длины N (длина - это общее количество нулей и едииниц), в которых никакие три единицы не стоят рядом.

Входные данные
Вводится натуральное число N, не превосходящее 40.

Выходные данные
Выведите количество искомых последовательностей. Гарантируется, что ответ не превосходит 2³¹ − 1.

Дизайн-студия Артемия Индюкова получила заказ на разработку очень пафосного лифта для нового небоскреба. За работу взялся сам Артемий, отличающейся, кстати, редкой неадекватностью. У него есть идея-фикс: для управления лифтом достаточно четырех кнопок. Кнопки должны быть следующие:
- Поднятся на A этажей вверх
- Поднятся на B этажей вверх
- Поднятся на C этажей вверх
- Спустится на первый этаж
Изначально лифт находится на первом этаже. Пассажир лифта использует первые три кнопки чтобы попасть на тот этаж, на который он хочет. Если пассажир пытается подняться вверх на A, B или C этажей, а такого этажа в здании не существует (т.е. пассажир хочет подняться выше N-го, последнего этажа), то лифт никуда не едет.
Заказчики проекта оказались с юмором и вместе с отказом от футуристичного дизайна решили оценить адекватность Артемия по шкале от 1 до N. Оценка адеватности равна количеству этажей, на которые можно попасть с первого с помощью такого лифта. Помогите им в этом.

Входные данные
Первая строка содержит число N – высоту небоскреба (1 <= N <= 500 000).

Вторая строка содержит три числа A, B и C, задающие параметры кнопок (1 <= A, B, C <= 100 000).

Выходные данные
Выведите единственное число — оценку адекватности Артемия Индюкова.

Бегемот – это шахматная фигура, которая живет на доске размером 100x100 клеток. За один ход бегемот перемещается на n клеток по горизонтали или вертикали и на m клеток в перпендикулярном направлении. Например, шахматный конь – это бегемотик, у которого n=2, m=1 (или наоборот). Раскрасьте доску, на которой живет бегемот, в два цвета (каждую клетку – в один из двух цветов), так чтобы любой ход из любой клетки приводил бегемота в клетку другого цвета.

Входные данные
Вводятся два натуральных числа n и m, не превосходящие 99.

Выходные данные
Выведите 100 строк по 100 цифр – 1 или 0, обозначающих клетки разного цвета (через пробел).

Приехав в Хоббитанию, белый маг Гэндальф принялся рассказывать Бильбо последние новости из Средиземья. Больше всего впечатлительного хоббита поразил рассказ о Большом огромном коллайдере - только представить себе гигантских размеров кольцо, зарытое под землей!

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

Бильбо хочет прокопать новые коридоры в норе, но так как копать будут только Фродо и сам Бильбо (не Гэндальф же!) , есть возможность прокопать только один или два новых коридора.

После этого последовательность из нескольких комнат будет названа коллайдером. При этом должны быть выполнены следующие условия: первая комната в этой последовательности соединена коридором со второй, вторая - с третьей, и так далее, наконец, последняя комната последовательности должна быть соединена с первой. Кроме того, каждая комната может входить в эту последовательность не более одного раза.

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

Входные данные
В первой строке входного файла содержится целое число n (3≤n≤100000) - число комнат в норе Бильбо.

В следующих n−1 строках содержатся по два целых числа - номера комнат, соединенных коридорами. Комнаты нумеруются от 1 до n.

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

На следующих одной или двух строках выведите пары номеров комнат, между которыми следует прокопать новые коридоры.

Если существует несколько возможных планов строительства коллайдера максимальной длины, выведите любой из них.

Примечание
В первом примере коллайдер состоит из комнат с номерами 1, 2, 3 и 4 (именно в этом порядке), во втором примере - 1, 3, 2, 4.

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

Чтобы ничего не перепутать, мастера договорились, что Олег будет только включать лампы, а Сергей только выключать.

Театральная сцена представляет собой прямоугольник W на L метров, внутри которого расположено N ламп подсветки.

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

Олег может перемещаться по сцене с максимальной скоростью V₁ метров в секунду, а Сергей − V₂ метров в секунду. Мастера могут находиться на сцене только в перерывах между действиями. Во время действия они могут переместиться в любую точку в пределах той части кулис, в которой они оказались перед началом действия.

Перед началом спектакля Олег и Сергей получили подробный сценарий, в котором указано количество действий M и для каждого действия свой набор ламп подсветки, которые должны быть включены. Лампы, которые не входят в этот набор, должны быть выключены. Перед первым действием Олег должен находиться в левой части кулис, а Сергей − в правой. Изначально включены лампы, необходимые для первого действия.

Задача Олега и Сергея − организовать работу так, чтобы суммарное время всех перерывов между действиями было бы минимальным.

Входные данные
На первой строке входного файла находится пять чисел − W,L,V₁,V₂ и N (1≤W,L≤50, 1≤V₁,V₂≤20, 1 ≤ N ≤ 15)− размеры сцены, максимальные скорости мастеров и число ламп подсветки соответственно.

Далее идут N строк с координатами ламп подсветки в метрах x_i,y_i (0<x_i<L, 0<y_i<W).

Следующая строка содержит число M(1≤M≤10000) − число действий в спектакле. Далее идут M строк, каждая из которых содержит число ламп подсветки, которые должны быть включены в соответствующем действии, и номера ламп подсветки. Все числа во входном файле целые.

Выходные данные
В выходной файл выведите единственное число − минимальное суммарное время перерывов между действиями в секундах с точностью 10^-5.

Требуется заполнить N элементов массива, пронумерованных числами от 1 до N (A[1]…A[N]), натуральными числами от 2 до N+1, использовав каждое число ровно один раз, так, чтобы значение каждого элемента массива делилось бы нацело на его номер (т.е. для каждого i A[i] делилось бы на i).

Напишите программу, которая для заданного N вычислит количество способов такого заполнения массива.

Входные данные
Вводится одно натуральное число N (1≤N≤60000).

Выходные данные
Выведите одно число — искомое количество способов заполнения массива.

Примечание
Массив можно заполнить единственным способом: 3 2
 

В правильном N-угольнике провели некоторые диагонали так, что он оказался разбит на треугольники. Изначально стороны N-угольника и все его диагонали черные.

Разрешается выбрать четырехугольник, в котором ровно одна диагональ, и при этом эта диагональ черного цвета (сам четырехугольник не обязан быть полностью черным) и проделать с ним следующее: заменить диагональ на противоположную (т.е. если сам четырехугольник был ABCD и в нем была диагональ AC, то она меняется на диагональ BD), после чего перекрасить стороны этого четырехугольника и новую диагональ в красный цвет.

Требуется определить, можно ли с помощью таких операций сделать так, чтобы все отрезки (т.е. стороны N-угольника и изображенные диагонали) стали красными, и не осталось бы ни одного черного отрезка. А если это возможно, то какое минимальное количество операций для этого требуется.

Входные данные
Вводится сначала число N (3≤N≤30000). Далее идет описание N–3 проведенных диагоналей. Каждая диагональ описывается двумя натуральными числами — номерами вершин, которые она соединяет. Гарантируется, что проведенные диагонали внутри N-угольника не пересекаются.

Выходные данные
Выведите минимальное число действий, необходимое для того, чтобы перекрасить весь N-угольник и все его диагонали. Если перекрасить многоугольник указанным способом невозможно, выведите одно число –1 (минус один).

Поверхность Земли в горной местности можно представить в виде ломаной линии. Вершины ломаной расположены в точках (x₁, y₁), (x₂, y₂),…,(x_N, y_N), при этом x_i<x_i+1.

Обычный горный маг находится в точке (x₁, y₁) и хочет попасть в точку (x_N, y_N). При этом он может перемещаться только пешком. Он может ходить по поверхности Земли (т.е. вдоль ломаной). А может сотворить в воздухе мост и пройти по нему. Мост может соединять две вершины ломаной: мост не может начинаться и заканчиваться не в вершине ломаной, и мост не может проходить под землей (в том числе не может быть туннелем в горе), но мост может каким-то своим участком проходить по поверхности земли. Длина моста не может быть больше R. Суммарно маг может построить не более K мостов.

Какое наименьшее расстояние придется пройти магу, чтобы оказаться в точке (x_N, y_N).

Входные данные
Вводится сначала натуральное число N (2≤N≤100). Затем водится натуральное число K (1≤K≤100) — максимальное количество мостов. Далее вводится целое число R (0≤R≤10000) — максимальная возможная длина моста. Далее вводятся координаты (x₁, y₁), (x₂, y₂),…,(x_N, y_N). Все координаты – целые числа, не превышающие по модулю 10000, для всех i от 1 до N–1: x_i<x_i+1.

Выходные данные
Выведите одно число — минимальную длину пути, которую придется пройти магу (как по земле, так и по мостам). Ответ выведите не менее чем с 5 цифрами после десятичной точки.

Вычислите n-й член последовательности, заданной формулами:

a_2n = a_n + 1 (n>0),
a_2n+2 = a_2n+1 - a_n (n>0),
a₀=1, a₁=1.

Входные данные
Вводится натуральное число n, не превосходящее 1000.

Выходные данные
Выведите ответ к задаче.

Вычислите n-й член последовательности, заданной формулами:

a_2n = a_n + a_n-1,
a_2n+1 = a_n – a_n-1,
a₀ = a₁ = 1.

Входные данные
Вводится одно натуральное число n (1≤n≤1000).

Выходные данные
Вывести одно число a_n.

Последовательность чисел Фибоначчи определяется следующим образом: F₀ = F₁ = 1,

F_n+1 = F_n+F_n-1. Напишите программу для вычисления последней цифры n-го члена последовательности.

Входные данные
В единственной строке входных данных записано натуральное число n (1≤n≤1000).

Выходные данные
Вывести последнюю цифру числа F_n.

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

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

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

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

Пример 1. Пусть у компании есть вагоны AA, AA, AB, BA, BA и локомотив AB. В поезде должно быть 4 вагона. Из данных вагонов можно сформировать только два различных поезда: BAAAABBA и BAABBAAA. Локомотив можно присоединить к поезду как с левого (используя сцепление B), так и с правого конца (используя сцепление A).

Пример 2. Пусть у компании есть только по одному вагону каждого типа (AA, AB, BA, BB) и локомотив AA, а поезд должен состоять из трёх вагонов. Существует три способа сформировать поезд: AAABBA, ABBAAA и ABBBBA.

Входные данные
В первой строке через пробел N - число вагонов, находящихся в распоряжении компании, и K - требуемая длина поезда в вагонах. Вторая строка описывает тип сцеплений локомотива. Следующие N строк описывают типы сцеплений вагонов. Описания даны как AB, AA, BB или BA.

Ограничения: 1 <= K <= N <= 40.

Выходные данные
В первой строке выводится слово "YES", если можно сформировать хотя бы один поезд, или "NO" - в противном случае.

Если поезд сформировать возможно, во второй строке должно указываться число способов это сделать.

{F_k} - бесконечная последовательность целых чисел, которая удовлетворяет условию Фибоначчи F_k = F_k - 1 + F_k - 2 (для любого целого k). Даны i, F_i, j, F_j, n (i <> j). Найти F_n. Пример части последовательности:

k	-2	-1	0	1	2	3	4	5	6
Fk	-5	4	-1	3	2	5	7	12	19

Ограничения: -1000 <= i, j, n <= 1000, -2 000 000 000 <= F_k <= 2 000 000 000 (k = min(i, j, n) ... max(i, j, n)).

Входные данные
В первой строке находятся числа i, F_i, j, F_j, n.

Выходные данные
Вывести одно число F_n.

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

Цель игры - убрать карты в таком порядке, чтобы минимизировать общее количество набранных очков.

Например, если карты содержат числа 10, 1, 50, 20 и 5, игрок может взять карту с числом 1, затем 20 и 50, получая очки

10 * 1 * 50 + 50 * 20 * 5 + 10 * 50 * 5 = 500 + 5000 + 2500 = 8000.

Если бы он взял карты в обратном порядке, то есть 50, затем 20, затем 1, количество очков было бы таким:

1 * 50 * 20 + 1 * 20 * 5 + 10 * 1 * 5 = 1000 + 100 + 50 = 1150.

Входные данные
В первой строке находится число карт N, во второй - разделённые пробелами N чисел на картах.

Ограничения: 3 <= N <= 100, числа на картах целые от 1 до 100.

Выходные данные
Вывести одно целое число - минимально возможное число очков.