| Условие задачи | | Прогресс |
|
Темы:
Динамическое программирование: два параметра
Треугольник Паскаля строится следующим образом. Первая строка состоит из одного числа, равного единице. Каждая следующая
содержит на одно число больше, чем предыдущая. Первое и последнее из этих чисел равны 1, а все остальные вычисляются как сумма числа, стоящего в предыдущей строке над ним и числа, стоящего в предыдущей же строке слева от него.
Входные данные
Вводится одно целое число N (\(0<=N<=30\)).
Выходные данные
Выведите N строк треугольника Паскаля. Разделяйте числа в строке одним пробелом.
Примечание
Все числа в треугольнике Паскаля при указанных ограничениях входят в Longint.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
8
|
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
|
| |
![]()
|
|
Темы:
Динамическое программирование: два параметра
В прямоугольной таблице NxM (в каждой клетке которой записано некоторое число) в начале игрок находится в левой верхней клетке.
За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено).
При проходе через клетку с игрока берут столько у.е., какое число записано в этой клетке (деньги берут также за первую и последнюю клетки его пути).
Требуется найти минимальную сумму у.е., заплатив которую игрок может попасть в правый нижний угол.
Входные данные
В первой строке записаны два числа N и M - размеры таблицы (\(1<=N<=20\), \(1<=M<=20\)). Далее записаны N строк по M чисел в каждой - размеры штрафов в у.е. за прохождение через соответствующие клетки (каждое число от 0 до 100).
Выходные данные
Выведите минимальную сумму, потратив которую можно попасть в правый нижний угол.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
3 4
1 1 1 1
5 2 2 100
9 4 2 1
|
8 |
| |
![]()
|
|
Темы:
Динамическое программирование: два параметра
Динамическое программирование по подстрокам
Задан шаблон, состоящий из круглых скобок и знаков вопроса. Требуется определить, сколькими способами можно заменить знаки вопроса круглыми скобками так, чтобы получилось правильное скобочное выражение.
Входные данные: вводится строка, которая содержит заданный шаблон длиной не более 80 символов.
Выходные данные: выведите искомое количество способов. Исходные данные будут таковы, что это количество не превзойдет \( 2 \cdot 10^9\).
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
????(? |
2 |
| |
![]()
|
|
Темы:
Динамическое программирование
Динамическое программирование: два параметра
Дана прямоугольная доска N × M (N строк и M столбцов). В левом верхнем углу находится шахматный конь, которого необходимо переместить в правый нижний угол доски. При этом конь может ходить ТОЛЬКО на две клетки вниз и на одну клетку вправо, либо на две клетки вправо и на одну клетку вниз (смотри рисунок).
Необходимо определить, сколько существует различных маршрутов, ведущих из левого верхнего в правый нижний угол.
Входные данные
Во входной строке находятся два натуральных числа N и M (\(1 <= N,\ M <= 50\)).
Выходные данные
Выведите единственное число количество способов добраться конём до правого нижнего угла доски.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
4 4 |
2 |
| |
![]()
|
|
Темы:
Динамическое программирование
Динамическое программирование: два параметра
Дана прямоугольная доска N × M (N строк и M столбцов). В левом верхнем углу находится шахматный конь, которого необходимо переместить в правый нижний угол доски. При этом конь может ходить только так, как показано на рисунке:
Необходимо определить, сколько существует различных маршрутов, ведущих из левого верхнего в правый нижний угол.
Входные данные
Во входной строке находятся два натуральных числа N и M (\(1 <= N,\ M <= 15\)).
Выходные данные
Выведите единственное число количество способов добраться конём до правого нижнего угла доски.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
4 4 |
2 |
| 2 |
7 15 |
13309 |
| |
![]()
|
|
Темы:
Динамическое программирование: два параметра
Петя очень любит компьютерные игры. Недавно он обнаружил в интернете интересную ролевую игру. Управляя героем, надо искать магические артефакты и получать золото.
К сожалению, первый же квест в игре поставил Петю в тупик. Выполнив задание, он получил n магических артефактов, которые можно использовать для получения золота. Для каждого артефакта известна его ценность , для i -го артефакта она равна wi . Для получения золота артефакты можно активировать . Каждый артефакт можно активировать только один раз. Петя может активировать артефакты в произвольном порядке.
У героя, которым управляет Петя, есть магическая сила , исходно она равна нулю. Есть два способа активировать артефакт: с помощью магии и с помощью силы. Если активировать артефакт с ценностью w с помощью магии, то магическая сила героя увеличивается на w . Если же активировать артефакт с ценностью w с помощью силы, то герой получает xw золотых монет, где x — магическая сила героя в момент активации артефакта.
Например, если герой Пети получил 4 артефакта с ценностями 1, 1, 2 и 2, то можно получить 9 золотых монет, действуя следующим образом. Сначала надо активировать с помощью магии по одному артефакту с ценностью 1 и 2. После этого магическая сила героя равна 3, теперь можно активировать с помощью силы оставшиеся артефакты и получить 3 и 6 золотых монет, соответственно.
Помогите Пете определить, какое максимальное количество золотых монет он может получить, активировав артефакты в правильном порядке оптимальным образом.
Входные данные
Первая строка входных данных содержит единственное число n — количество магических артефактов ( 1 ≤ n ≤ 100 ).
Вторая строка входных данных содержит n чисел w1 , w2 , ..., wn — ценности артефактов ( 1 ≤ wi ≤ 100 ).
Выходные данные
Выведите максимальное возможное число золотых монет, которые можно получить с помощью магических артефактов.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
4
1 1 2 2 |
9 |
| |
![]()
|
|
Темы:
Динамическое программирование: два параметра
Миша установил на свой телефон новую игру «Мемтест 2к17». В ней предусмотрены ежедневные награды за посещение. Награды бывают n уровней. Тип награды зависит от награды за предыдущий день, а именно:
если игрок в предыдущий день не посещал игру, то за сегодняшнее посещение он получит награду уровня 1;
если игрок в предыдущий день зашёл в игру и получил награду уровня k ( k ≠ n ), то за сегодняшнее посещение он получит награду уровня k + 1 ;
если игрок в предыдущий день зашёл в игру и получил награду уровня n , то за сегодняшнее посещение он получит награду уровня 1.
На Форуме для Крутых Программистов Миша выяснил, что награды каждого из уровней составляют соответственно a 1 , a 2 , ..., a n золотых монет.
Через m дней состоится турнир по «Мемтест 2к17», к которому Миша хочет собрать как можно больше золотых монет. Помогите ему спланировать посещения игры на протяжении m дней, оставшихся до турнира. Найдите наибольшее количество золотых монет, которое он сможет получить за счёт ежедневных наград в этот период. Можно считать, что игра установлена в первый из этих m дней, то есть до этого Миша в неё ни разу не заходил.
Входные данные
Первая строка входных данных содержит натуральные числа n и m ( 1 ≤ n , m ≤ 1000 ) — количества уровней наград и дней до турнира.
Вторая строка входных данных содержит n целых чисел a 1 , a 2 , ..., a n ( 1 ≤ a i ≤ 1000 ), где a i — величина награды i -го уровня в золотых монетах.
Выходные данные
Выведите одно натуральное число — наибольшее количество золотых монет, которое Миша сможет получить до турнира.
Примечание
В первом тесте из примера Мише выгодно заходить в игру каждый день. Тогда он получит 1 + 2 + 4 = 7 золотых монет.
Во втором тесте из примера Мише выгодно заходить в игру в первый и третий день, получив в каждый из них по 4 монеты, тогда в сумме он получит 8 монет.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
3 3
1 2 4 |
7 |
| 2 |
3 3
4 2 1 |
8 |
| |
![]()
|
|
Темы:
Динамическое программирование
Динамическое программирование: два параметра
Популярная сеть быстрого питания «McDuck's» открыла новый филиал в Берляндии. В ресторане установлено k плит. Для того чтобы приготовить бургер, надо жарить котлету в течение минуты на одной из плит, поэтому ресторан может готовить не более k бургеров в минуту.
Известно, что в «McDuck's» придут n клиентов. i-й из них придёт в момент времени ti, закажет xi бургеров и будет готов заплатить за них ci бурлей. Каждый клиент готов ждать заказ в течение w минут и, если через w минут после прихода он не получил xi бургеров, он не заплатит ничего. При этом каждый клиент готов получать только свежие бургеры, то есть только те, котлеты для которых были поджарены не раньше времени ti. Из-за таких сложных требований ресторан не всегда сможет выполнить все заказы всех клиентов.
Менеджеров ресторана заинтересовало, какую максимальную прибыль может получить «McDuck's». Помогите им ответить на этот непростой вопрос. Можно считать, что на готовку бургеров не расходуется никаких денег.
Входные данные
В первой строке содержатся три целых числа n, k и w (1 ≤ n ≤ 100000, 1 ≤ k ≤ 10, 1 ≤ w ≤ 60) — число клиентов, число плит и время ожидания клиента, соответственно.
Следующие n строк содержат описания клиентов, состоящие из трёх целых чисел — ti, xi, ci (1 ≤ ti, xi, ci ≤ 109) — время (в минутах) прихода i-го клиента, число бургеров, которые он закажет и число бурлей, которые он готов заплатить, соответственно. Клиенты перечислены в порядке возрастания времени прихода, то есть для любого i > 1 верно, что ti−1 ≤ ti.
Выходные данные
В единственной строке выведите одно число — максимальную прибыль ресторана.
Примечание
В первом тестовом примере первую котлету можно поставить жариться в момент времени 0 и тогда в момент времени 1 она будет готова и её можно будет дать в бургере первому клиенту. В момент времени 1 можно поставить жариться ещё одну котлету, она будет готова в момент времени 2 и её можно будет дать в бургере второму клиенту.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
2 1 1
1 1 5
1 1 7 |
12 |
| 2 |
3 2 2
1 6 8
2 5 10
3 4 4 |
12 |
| |
![]()
|
|
Темы:
Динамическое программирование: два параметра
Сколько целых последовательностей длины N, A = (A1,…,AN), удовлетворяют всем приведенным ниже условиям?
1) 1 <= Ai <= M (1 <= i <= N)
2)\(\sum\limits_{i=1}^NA_i \le K\)
Входные данные
На вход подается строка, содержащая три целых числа N, M (1 <= N, M <= 50), K (N <= K <= NM).
Выходные данные
Выведите на ответ на задачу.
Примеры
| № |
Входные данные |
Выходные данные |
Пояснения |
| 1 |
2 3 4
|
6
|
(1,1) (1,2) (1,3) (2,1) (2,2) (3,1) |
| |
![]()
|