Тема:
Информатика
>>
Алгоритмы
>>
Динамическое программирование
>>
Динамическое программирование: классические задачи
Фильтр
Выбрана 1 задача
Версия для печати
Убрать все задачи
Решение
Убрать все задачи
Существуют ли такие натуральные числа a1 < a2 < a3 < ... < a100, что НОД(a1, a2) > НОД(a2, a3) > ... > НОД(a99, a100)?
Решение
Задачи
Страница: 1 2 3 >> [Всего задач: 15]
На вершине лесенки, содержащей N ступенек, находится мячик,
который начинает прыгать по ним вниз, к основанию. Мячик может прыгнуть на
следующую ступеньку, на ступеньку через одну или через 2. (То есть,
если мячик лежит на 8-ой ступеньке, то он может переместиться на 5-ую,
6-ую или 7-ую.) Определить число всевозможных "маршрутов" мячика с вершины
на землю.
Формат входных данных
Одно число 0 < N < 31.
Формат выходных данных
Одно число — количество маршрутов.
Даны две последовательности
x[1]...x[n]
и
y[1]...y[k] целых чисел. Найти максимальную
длину последовательности, являющейся подпоследовательностью
обеих последовательностей. Количество операций порядка
n . k.
На квадратной доске расставлены целые неотрицательные числа. Черепашка,
находящаяся в левом верхнем углу, мечтает попасть в правый нижний. При этом
она может переползать только в клетку справа или снизу и хочет, чтобы сумма
всех чисел, оказавшихся у нее на пути, была бы максимальной. Определить эту
сумму.
Формат входных данных
Первая строка — N — размер доски.
Далее следует N строк, каждая из которых содержит N целых чисел, представляющие доску.
Формат выходных данных
Одно число — максимальная сумма.
При переработке радиоактивных материалов образуются отходы двух видов — особо опасные (тип A) и неопасные (тип B). Для их хранения используются одинаковые контейнеры. После помещения отходов в контейнеры, последние укладываются вертикальной стопкой. Стопка считается взрывоопасной, если в ней подряд идет более двух контейнеров типа A. Для заданного количества контейнеров N определить число безопасных стопок.
Формат входных данных
Одно число 0 < N < 31.
Формат выходных данных
Одно число — количество безопасных вариантов формирования стопки.
Требуется вычислить количество N-значных чисел в системе счисления с основанием K, таких что их запись не содержит двух подряд идущих нулей.
Ограничения: 2 <= K <= 10, N + K <= 18.
Формат входных данных
Числа N и K в десятичной записи, разделенные пробелом или переводом строки.
Формат выходных данных
Искомое число в десятичной записи.
Страница: 1 2 3 >> [Всего задач: 15]
Задача 98714[Мячик на лесенке] |
|
|
Формат входных данных
Одно число 0 < N < 31.
Формат выходных данных
Одно число — количество маршрутов.
|
|
Решение |
Задача 76270 |
|
|
|
|
|
Решение |
Задача 98715[Черепашка] |
|
|
Формат входных данных
Первая строка — N — размер доски.
Далее следует N строк, каждая из которых содержит N целых чисел, представляющие доску.
Формат выходных данных
Одно число — максимальная сумма.
|
|
|
Решение |
Задача 98717[Взрывоопасность] |
|
|
Формат входных данных
Одно число 0 < N < 31.
Формат выходных данных
Одно число — количество безопасных вариантов формирования стопки.
|
|
|
Решение |
Задача 98718[K-ичные числа] |
|
|
Ограничения: 2 <= K <= 10, N + K <= 18.
Формат входных данных
Числа N и K в десятичной записи, разделенные пробелом или переводом строки.
Формат выходных данных
Искомое число в десятичной записи.
|
|
|
Решение |
Страница: 1 2 3 >> [Всего задач: 15]
