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

У исполнителя Счетовод три команды, которым присвоены номера:
1. прибавь A
2. умножь на B
3. умножь на С
Программа для Счетовода – это последовательность команд. Сколько есть программ, которые число S преобразуют в число F?
Гарантируется, что имеется хотя бы одна программа, которая получает из числа S число F.

Входные данные
Программа получает на вход пять чисел: A, B, С, S, F (1 <= A, B, C <= 10, 1 <= S <= 100, 1 <= F <= 10³, B и C - различные числа)

Выходные данные
Выведите ответ на задачу.  Гарантируется, что ответ не превышает 263.

Примеры

№	Входные данные	Выходные данные
1	1 2 3 1 18	96

У исполнителя Счетовод две команды, которым присвоены номера:
1. прибавь A
2. умножь на B
Программа для Счетовода – это последовательность команд. Сколько есть программ, которые число S преобразуют в число F?
Гарантируется, что имеется хотя бы одна программа, которая получает из числа S число F.

Входные данные
Программа получает на вход четыре числа: A, B, S, F (1 <= A, B <= 10, 1 <= S <= 100, 1 <= F <= 10³)

Выходные данные
Выведите ответ на задачу. Гарантируется, что ответ не превышает 263.
 

Примеры

№	Входные данные	Выходные данные
1	1 2 1 10	14

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

 

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

В первой строке записаны два числа N и M - размеры таблицы (1<=N<=100, 1<=M<=100). Далее записаны N строк по M чисел в каждой - размеры штрафов в у.е. за прохождение через соответствующие клетки (каждое число от 0 до 100).

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

Первая строка выходных данных содержит максимальную возможную сумму, вторая – маршрут, на котором достигается эта сумма. Маршрут выводится в виде последовательности, которая должна содержать N-1 букву D, означающую передвижение вниз и M-1 букву R, означающую передвижение направо. Если таких последовательностей несколько, необходимо вывести ровно одну (любую) из них.

 

Примеры

№	Входные данные	Выходные данные
1	5 5 9 9 9 9 9 3 0 0 0 0 9 9 9 9 9 6 6 6 6 8 9 9 9 9 9	74 D D R R R R D D

Дан граф из n вершин и m ориентированных ребер. В каждой вершине записана некоторая строчная латинская буква. 
Определим величину пути как наибольшее количество раз, которое какая-то буква встречалась на этом пути. Например, если буквы на пути образуют строку «abaca», то величина этого пути равна 3.
Ваша задача — найти путь с наибольшей величиной.

Входные данные:
Первая строка содержит два целых числа n, m (1 ≤ n, m ≤ 200000), означающих, что в графе n вершин и m ориентированных ребер.
Вторая строка содержит строку s, состоящую только из строчных латинских букв. Символ номер i — это буква, записанная в вершине номер i.
Далее следуют m строк. Каждая из этих строк содержит два целых числа x, y (1 ≤ x, y ≤ n), описывающих ориентированное ребро из x в y. Обратите внимание, x может быть равно y, и могут быть несколько ребер между x и y.
Кроме того, граф может быть несвязным.

Выходные данные:
Выведите одно число — максимальную величину пути. Если существуют пути со сколь угодно большой величиной, выведите -1.

Примеры:
 

Входные данные	Выходные данные
5 4 abaca 1 2 1 3 3 4 4 5	3
6 6 xzyabc 1 2 3 1 2 3 5 4 4 3 6 4	-1
10 14 xzyzyzyzqx 1 2 2 4 3 5 4 5 2 6 6 8 6 5 2 10 3 9 10 9 4 6 1 10 2 8 3 7	4

Дан ориентированный взвешенный ациклический граф. Требуется найти в нем кратчайший путь
из вершины s в вершину t.

Входные данные:
Первая строка входного файла содержит четыре целых числа n, m, s и t - количество вершин, ребер графа, начальная и конечная вершина соответственно (1 <= n <= 100000; 0 <= m <= 200000; 1 <= s, t <= n).
Следующие m строк содержат описания ребер по одной на строке. 
Ребро номер i описывается тремя целыми числами b_i, e_i и w_i - началом, концом и длиной ребра соответственно (1 <= b_i, e_i <= n; |w_i| <= 1000). 
Граф не содержит циклов и петель.

Выходные данные:
Первая строка выходного файла должна содержать одно целое число - длину кратчайшего пути из s в t. 
Если пути из s в t не существует, выведите "Unreachable".

Примеры:
 

Входные данные	Выходные данные
2 1 1 2 1 2 -10	-10
2 1 2 1 1 2 -10	Unreachable

Сегодня в замке Эна проходит фестиваль пирогов, в котором участвуют n пекарен, каждая из которых имеет свой уникальный номер от 1 до n.
Некоторые пекарни соединены между собой двусторонними дорогами, но таким образом, что если из пекарни i можно дойти до пекарни j, то существует ровно один маршрут между ними.

Когда Эн ест пироги в i-й пекарне, то он получает A_i удовольствия. А если проходит по дороге между некоторыми пекарнями с номерами v и u, то вкусный аромат пирогов приносит Эну C_v,u удовольствия.

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

Помогите Эну определить максимально возможное удовольствие, которое он сможет получить.

Входные данные:
В первой строке дано число n (1 <= n <= 50000) - количество пекарен, и число k - количество существующих дорог между пекарнями.
Во второй строке дано n чисел A_i (0 <= A_i <= 10000) - удовольствие от пирогов i-й пекарне.
Далее следует k строк, в каждой по 3 числа v, u, C (1 <= v, u <= n; v ≠ u; 0 <= C <= 10000), означающие, что существует дорога между пекарнями с номерами v и u, и аромат на этой дороге приносит C удовольствия.

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

Примеры:
 

Входные данные	Выходные данные
2 1 1 1 1 2 1	3
8 7 1 5 4 6 10 1 2 2 1 2 1 2 3 10 2 4 1 4 5 1 4 6 2 6 7 2 6 8 3	37

Пояснения:
В первом примере нужно начать в 1-й пекарне (1 удовольствие), пройти по дороге между 1-й и 2-й пекарнями (1 удовольствие) и посетить 2-ю пекарню (1 удовольствие). Суммарное удовольствие - 1+1+1 = 3.
Во втором примере нужно начать в 5-й пекарне (10 удовольствия), пройти по дороге между 5-й и 4-й пекарнями (1 удовольствие), посетить 4-ю пекарню (6 удовольствия), пройти по дороге между 4-й и 2-й пекарнями (1 удовольствие), посетить 2-ю пекарню (5 удовольствия), пройти по дороге между 2-й и 3-й пекарнями (10 удовольствия), посетить 3-ю пекарню (4 удовольствия). Суммарное удовольствие - 10+1+6+1+5+10+4 = 37.

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

Входные данные:
В первой строке дано число n - количество вершин в дереве.
Далее идет n-1 строка, в каждой из которых дается по два числа a_i и b_i (1 <= a_i, b_i <= n) - ребра дерева.

Выходные данные:
Выведите одно число - размер максимального паросочетания данного дерева.

Примеры:
 

Входные данные	Выходные данные
4 1 2 2 3 3 4	2

Пояснение:
В максимальное паросочетание данного дерева будут входить ребра 1-2 и 3-4.

На межрегиональной олимпиаде по программированию роботов соревнования проводятся в один тур и в необычном формате. Задачи участникам раздаются последовательно, а не все в самом начале тура, и каждая i-я задача (1 ≤ i ≤ n) становится доступной участникам в свой момент времени s_i. При поступлении очередной задачи каждый участник должен сразу определить, будет он ее решать или нет. В случае, если он выбирает для решения эту задачу, то у него есть t_i минут на то, чтобы сдать ее решение на проверку, причем в течение этого времени он не может переключиться на решение другой задачи. Если же участник отказывается от решения этой задачи, то в будущем он не может к ней вернуться. В тот момент, когда закончилось время, отведенное на задачу, которую решает участник, он может начать решать другую задачу, ставшую доступной в этот же момент, если такая задача есть, или ждать появления другой задачи. При этом за правильное решение i-й задачи участник получает c_i баллов.

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

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

Входные данные
Первая строка содержит одно целое число n (1 ≤ n ≤ 10⁵) количество задач на олимпиаде.

Последующие n строк содержат описания задач, по три числа на каждой строке: si момент появления i-й задачи в минутах, t_i время, отведенное на ее решение в минутах, и ci сколько баллов получит участник за решение этой задачи (1 ≤ s_i, t_i, c_i ≤ 10⁹).

Выходные данные
Первая строка  должна содержать одно число – максимальное количество баллов, которое сможет получить Артур на олимпиаде.

Вторая строка должна содержать одно целое число m - количество задач, которые надо решить при оптимальном выборе.

Третья строка должна содержать m разделенных пробелом целых чисел - номера этих задач в порядке их решения. Задачи пронумерованы, начиная с единицы, в порядке их описания во входном файле.

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

Примеры

№	Входные данные	Выходные данные
1	2 1 1 1 2 2 2	3 2 1 2
2	3 1 2 1 3 2 1 2 4 3	3 1 3

Ресторан получил n заказов на проведение банкета. Каждый заказ характеризуется двумя величинами: моментом начала банкета l_i и моментом конца r_i (l_i ≤ r_i).

Руководство ресторана может либо принять заказ, либо отвергнуть его. Какое наибольшее количество заказов может быть принято?

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

Входные данные:
В первой строке находится целое число n (1 ≤ n ≤ 200000) — количество заказов. В каждой из следующих n строк находится пара целых чисел l_i, r_i (0 ≤ l_i ≤ r_i ≤ 10⁹).

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

Примеры:
 

Входные данные	Выходные данные
2 7 11 4 7	1
5 1 2 2 3 3 4 4 5 5 6	3
6 4 8 1 5 4 7 2 5 1 3 6 8	2

В сообщении, состоящем из одних русских букв и пробелов, каждую букву заменили её порядковым номером в русском алфавите (А – 1, Б – 2, …, Я – 33), а пробел – нулем. 
Требуется по заданной последовательности цифр найти количество исходных сообщений, из которых она могла получиться.

Входные данные:
В первой строке содержится последовательность из не более чем 70 цифр.

Выходные данные:
Выведите одно число - количество возможных сообщений.

Пример:
 

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

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

В коллекции принца n бриллиантов, каждый характеризуется весом w_i и стоимостью v_i. 
Принц хочет подарить наиболее дорогие бриллианты, однако король умен и не примет бриллиантов суммарного веса больше R. С другой стороны, принц будет считать себя жадным всю оставшуюся жизнь, если подарит бриллиантов суммарным весом меньше L.

Помогите принцу выбрать набор бриллиантов наибольшей суммарной стоимости, чтобы суммарный вес был в отрезке [L, R].

Входные данные:
Первая строка содержит число n (1 <= n <= 32), L и R (0 <= L <= R <= 10¹⁸).
Следующие n строк описывают бриллианты и содержат по два числа - вес и стоимость соответствующего бриллианта (1 <= wi, vi <= 10¹⁵).

Выходные данные:
Первая строка вывода должна содержать k - количество бриллиантов, которые нужно подарить принцессе. 
Вторая строка должна содержать номера даримых бриллиантов.
Бриллианты нумеруются от 1 до n в порядке появление во входных данных.

Если составить подарок принцессе невозможно, то выведите 0 в первой строке вывода.

Примеры:
 

Входные данные	Выходные данные
3 6 8 3 10 7 3 8 2	1 2

Дано число n. Вам необходимо сгенерировать все правильные скобочные последовательности, содержащие n пар скобок.

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

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

 

Для биномиальных коэффициентов (числа сочетаний из n по k) хорошо известна рекуррентная формула: \(C^k_n=C^{k-1}_{n-1}+C^{k}_{n-1}\), \(C^0_n = C^n_n=1\).
Входные данные
Вводится 2 числа - n и k.

Выходные данные
Необходимо вывести  значение  \(С^k_n\) .
 

Примеры

№	Входные данные	Выходные данные
1	4 2	6

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


Входные данные
Вводятся два числа N и M - размеры таблицы (1<=N<=10, 1<=M<=10).

Выходные данные
Выведите искомое количество вариантов.
 

Примеры

№	Входные данные	Выходные данные
1	2 3	3

 

Домовой Кузьма очень любит играть в шашки на доске 8х8. Когда никто не хочет с ним играть, он просто сидит и думает. Например, сейчас он пытается посчитать сколько есть вариантов провести белую шашку в дамки, если она находится одна на доске?
(Белая шашка ходит по диагонали на одну клетку вверх-вправо или вверх-влево. Шашка проходит в дамки, если попадает на верхнюю горизонталь.)

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

Вводятся два числа от 1 до 8: номер номер столбца (считая слева) и строки (считая снизу), где изначально стоит шашка.

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

Выведите одно число - количество вариантов.

 

 

Примеры

№	Входные данные	Выходные данные
1	3 7	2
2	1 8	1
3	3 6	4

 

Когда-то в далеком детстве мы все с удовольствием играли в игру "Камушки" или "Пять камешков", кто как называл. Для игры нужны были обычные камешки, которые можно было запросто найти на улице. Играть можно было в любом месте, Для игры нужна была небольшая ровная площадка утоптанной земли или ровный пол крыльца или беседки. 
Первый шаг игры заключался в следующем. На землю перед собой бросаются все пять камешков. Выбирался один из них. Это биток. Этот камешек подбрасывается в воздух и, пока он летит, необходимо поднять один из оставшихся на земле камешков и успеть подхватить этой же рукой летящий. Подобранный камешек откладывается в сторону и действие повторяется для всех оставшихся камешков.
На следующих шагах количество камешков, которые надо подхватить увеличивается. Последним шагом был экзамен, когда необходимо было подбросить все собранные камешки в воздух и поймать их тыльной стороной ладони, а затем опять подбросить, и поймать открытой ладонью. Сколько камешков в итоге оставалось, столько баллов и получаешь. Ход переходит к следующему игроку, который также повторяет все шаги. Далее запускался новый тур игры. Выигрывал тот, кто набирал больше всего баллов за все туры.
Многие ребята усложняли игру самыми разными способами.
Допустим у ребят есть бесконечное число камешков лежащих на земле. В конце тура им необходимо поймать в ладони не все камешки, а ровно столько, чтобы общее число баллов у них увеличилось на 1 или удвоилось или утроилось. Перед началом игры у всех уже имеется 1 балл. Победителем будет считаться тот, кто быстрее наберет N баллов.
Будем считать, что у всех играющих достаточно опыта игры, и они всегда доходят до экзамена с нужным им числом камней (чтобы была возможность нужное число баллов увеличить на 1, удвоить или утроить).

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

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

Программа получает на вход одно число, не превосходящее 10⁶.

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

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

 

 

Примеры

№	Входные данные	Выходные данные
1	1	0
2	5	3
3	32718	17

 

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

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

На вход программы поступает целое число N  (\(1<=N<=100\) ).

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

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

 

 

Примеры

№	Входные данные	Выходные данные
1	1	2

 

Слинки — игрушка-пружина, созданная в 1943 году в США Ричардом Джеймсом. В нашей стране она называлась просто Радуга. Все дети любили ее запускать со ступенек, считая у кого она спустится ниже.
Обычно "Радуга" в руках детей спускалась на следующую ступеньку, на ступеньку через одну или через 2. (Например, если Радугу запускали с 10-ой ступеньки, то она могла остановиться на 9-ой, 8-ой или 7-ой.)
Допустим на лестнице N ступенек. Определите число всевозможных "маршрутов" Радуги с вершины лестницы на землю.

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

Вводится одно число \(0 < N < 31\).

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

Выведите одно число — количество "маршрутов" Радуги.

 

 

Примеры

№	Входные данные	Выходные данные
1	4	7

 

Обеденный перерыв Гомера Симпсона составляет T миллисекунд. Один гамбургер Гомер съедает за N миллисекунд, один чизбургер - за M. Какое количество гамбургеров и чизбургеров нужно съесть, чтобы потраченное время было как можно больше, не превышая T. При равенстве потраченного времени необходимо максимизировать суммарное количество съеденных гамбургеров и чизбургеров.

Ограничения: 1 <=M, N, T, <= 1000000 , все числа целые.

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

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

Ввод	Вывод
1 2 1000	1000
2 1 1000	1000
3 6 1000	333 1