Time limit = 5 секунд(ы)
За новыми смартфонами на отечественной операционной системе "Аврора" выстроилась очередь из N человек, каждый из которых хочет купить 1 телефон. На всю очередь работала только одна касса, поэтому продажа устройств шла очень медленно, провоцируя создание мелкого бизнеса по перепродаже мест в очереди. Самые сообразительные быстро заметили, что, как правило, несколько гаджетов в одни руки кассир продает быстрее, чем когда эти же смартфоны продаются по одному. Поэтому они предложили нескольким подряд стоящим людям создавать краткосрочный консорциум: отдавать деньги первому из них, чтобы он купил на всех. Однако для борьбы со реселлерами кассир продавала не более 3-х устройств в одни руки, поэтому договориться таким образом между собой могли лишь 2 или 3 подряд стоящих человека.
Известно, что на продажу i-му человеку из очереди одного гаджета кассир тратит Ai секунд, на продажу двух устройств — Bi секунд, трех смартфонов — Ci секунд. Напишите программу, которая подсчитает минимальное время, за которое могли быть обслужены все покупатели.
Обратите внимание, что телефоны на группу объединившихся людей всегда покупает первый из них. Также никто в целях ускорения не покупает лишних смартфонов (то есть устройства, которые никому не нужны).
Записано сначала число N — количество покупателей в очереди (1 ≤ N ≤ 50000). Далее идет N троек натуральных чисел Ai, Bi, Ci. Каждое из этих чисел не превышает 36000. Люди в очереди нумеруются начиная от кассы.
Выведите одно число — минимальное время в секундах, за которое могли быть обслужены все покупатели.
| Вход | Выход |
|---|---|
| 5 5 10 15 2 10 15 5 5 5 20 20 1 20 1 1 |
12 |
| 2 3 4 5 1 1 1 |
4 |
Из верхнего левого угла в правый нижний угол сетки 2x2 можно пройти 6 разными путями (без возвратов, т.е. если идти только вниз или вправо). Сколько таких разных путей можно найти в сетке N×M?
Целые числа 1 ≤ N, M ≤ 20 через пробел.
Количество разных путей.
| Вход | Выход |
|---|---|
| 2 2 | 6 |
При перемещении из вершины треугольника вниз по примыкающим снизу числам, максимальная сумма просмотренных чисел равна 23.
3
7 4
2 4 6
8 5 9 3
3+7+4+9=23
Найдите максимальную сумму на пути сверху вниз для заданного треугольника из N строк.
На первой строке количество строк в треугольнике 1 ≤ N ≤ 100. Далее каждая строка треугольника с новой строки, числа в треугольнике (от 0 до 100) задаются через пробел.
Максимальная сумма.
| Вход | Выход |
|---|---|
| 4 3 7 4 2 4 6 8 5 9 3 |
23 |
Напишите программу, которая считает количество разложений P(N) данного натурального числа N на неупорядоченные натуральные слагаемые. Например, для N = 5 есть 7 различных разложений: 5 = 4+1 = 3+2 = 3+1+1 = 2+2+1 = 2+1+1+1 = 1+1+1+1+1. Разложения считаются различными если множества слагаемых различаются.
Натуральное число N, 0 < N ≤ 100.
Число P(N).
| Вход | Выход |
|---|---|
| 5 | 7 |
| 15 | 176 |
Посчитайте количество последовательностей длины N из нулей и единиц, в которых нет двух соседних единиц.
В единственной строке входного файла одно число N ( 1 ≤ N ≤ 40 ).
Вывести одно число — искомое количество последовательностей.
| Вход | Выход |
|---|---|
| 3 | 5 |
В некотором государстве в обращении находятся банкноты определенных номиналов. Центральный банк хочет, чтобы банкомат выдавал любую запрошенную сумму при помощи минимального числа банкнот, считая, что запас банкнот каждого номинала неограничен. Помогите Центральному банку решить эту задачу.
Первая строка входных данных содержит натуральное число N не превосходящее 100 — количество номиналов банкнот в обращении. Вторая строка входных данных содержит N различных натуральных чисел x1, x2, ..., xN, не превосходящих 10^6 — номиналы банкнот. Третья строчка содержит натуральное число S, не превосходящее 10^6 — сумму, которую необходимо выдать.
В первую строку выходного файла выведите минимальное число слагаемых (или -1, если такого представления не существует). Во вторую строку выведите это представление в любом порядке.
| Вход | Выход |
|---|---|
| 5 1 3 7 12 32 40 |
3 32 7 1 |