Условие:
Вывод
стандартный вывод или output.txt
D. Тайны
Археологи обнаружили древние камни с таинственными символами, которые, как полагают, представляют собой магические заклинания. Каждое заклинание состоит из последовательности камней, каждый из которых имеет свою силу, обозначенной целым числом. Чтобы активировать заклинание, необходимо выбрать такую подпоследовательность камней, чтобы сумма их сил была равна определённому магическому числу М. Однако, согласно древним правилам, нельзя выбирать камни подряд - между любыми двумя выбранными камнями должно быть хотя бы одно непропускаемое звено.
Формат ввода
Первая строка входного файла содержит два целых числа: количество камней Nи М (1 <= N <= 10°; 1 <= K<= 10°),
Вторая строка содержит N целых чисел, разделенных пробелами: силы камней а1, а2, …, аn ( 10 < , <= 10°).
Формат вывода
рилелите олно целов число - максимальное количество камней, удовлетворяющих условию
Решение:
Для решения задачи о выборе камней с заданной суммой сил, при этом соблюдая условие, что между выбранными камнями должно быть хотя бы одно непропускаемое звено, можно использовать динамическое программирование.
Вот пример кода на Python, который решает данную задачу: