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


Плюсануть
Поделиться
Класснуть
Запинить


Условие задачи Прогресс
ID 31928. Сборка компьютера
Темы: Динамическое программирование   

Для сборки компьютера необходимо T компонентов различного типа (видеокарта, жесткий диск, монитор и т.д.). В магазине продаются N компонентов. Каждый компонент относится к определенному типу и имеет некоторую стоимость и рейтинг по обзорам в журналах.
Напишите программу, определяющую из каких компонентов нужно собрать компьютер, чтобы его стоимость не превышала B, в составе были по одному компоненту каждого типа, а суммарный рейтинг использованных компонентов был максимальным.

Первая строка ввода содержит одно целое число – количество типов компонентов T (1 ≤ T ≤ 5). Вторая строка ввода содержит одно целое число – количество компонентов в магазине N (1 ≤ N ≤ 1000). Далее следует N строк, содержащих по три целых числа, разделенных пробелами – стоимость i-го компонента Ci (1 ≤ Ci ≤ 3000), его рейтинг Ri (1 ≤ Ri ≤ 3000) и его тип ti (1 ≤ ti ≤ T). Далее следует строка, содержащая одно целое число – бюджет на покупку компьютера B (1 ≤ B ≤ 3000).

Вывести в первой строке одно целое число – максимальный суммарный рейтинг использованных компонент. Во второй строке вывести T целых чисел – i-е число означает номер компонента типа i, выбранного для сборки. Если существует несколько вариантов с максимальным суммарным рейтингом, то из них вывести вариант с минимальной стоимостью, а среди таких вариантов можно вывести любой. Если не существует варианта сборки компьютера в рамках указанного бюджета, то вывести в первой строке одно число –1

Ввод Вывод
2
5
10 6 1
5 7 1
6 10 2
1 5 1
11 11 2
16
 18
2 5

ID 28419. Шаблон с ? и *
Темы: Динамическое программирование   

Шаблоном называется строка, состоящая из английских букв (a, ..., z, A, ..., Z) и символов ? и *. Каждый из символов ? разрешается заменить на одну произвольную букву, а каждый из символов * – на произвольную (возможно пустую) последовательность букв. Про любую строку из букв, которую можно получить из шаблона такими заменами, будем говорить, что она удовлетворяет этому шаблону.
 
Имеются два шаблона. Требуется найти строку минимальной длины, которая удовлетворяет обоим шаблонам, либо выдать сообщение, что такой строки не существует.
 
Входные данные
Заданные шаблоны записаны в первых двух строках входных данных. Длина каждого шаблона не превосходит 80 символов.

Выходные данные
Выведите строку минимальной длины, удовлетворяющую обоим шаблонам, либо сообщение "No solution!"

Ввод Вывод
AB?
*BC
 ABC

ID 30783. Садовник-художник
Темы: Динамическое программирование   

Садовник посадил N деревьев в один ряд. После посадки деревьев садовнику нужно их покрасить. В его распоряжении есть краска трех цветов: белая, синяя и оранжевая. Сколько способов покраски деревьев есть у него, если никакие два соседних дерева нельзя красить в одинаковый цвет?
 
Входные данные
В единственной строке записано одно натуральное число - количество деревьев N (1 ≤ N ≤ 50).
 
Выходные данные
В единственную строку нужно вывести одно число - количество способов покраски.
 
Ввод Вывод
3 12

ID 33142. Ход конем_1
Темы: Динамическое программирование    Динамическое программирование: два параметра   

Дана прямоугольная доска N × M (N строк и M столбцов). В левом верхнем углу находится шахматный конь, которого необходимо переместить в правый нижний угол доски. При этом конь может ходить ТОЛЬКО на две клетки вниз и на одну клетку вправо, либо на две клетки вправо и на одну клетку вниз (смотри рисунок).
 
 
Необходимо определить, сколько существует различных маршрутов, ведущих из левого верхнего в правый нижний угол.
 
Входные данные: во входной строке находятся два натуральных числа N и M (\(1 <= N,\ M <= 50\)).  
 
Выходные данные: выведите единственное число количество способов добраться конём до правого нижнего угла доски.
 
Примеры
№ Входные данные Выходные данные
1 4 4 2

ID 33143. Ход конем - 2
Темы: Динамическое программирование    Динамическое программирование: два параметра   

Дана прямоугольная доска N × M (N строк и M столбцов). В левом верхнем углу находится шахматный конь, которого необходимо переместить в правый нижний угол доски. При этом конь может ходить только так, как показано на рисунке:

 
Необходимо определить, сколько существует различных маршрутов, ведущих из левого верхнего в правый нижний угол.
 
Входные данные:  во входной строке находятся два натуральных числа N и M (\(1 <= N,\ M <= 15\)).  
 
Выходные данные: выведите единственное число количество способов добраться конём до правого нижнего угла доски.
 
Примеры
№ Входные данные Выходные данные
1 4 4 2
2 7 15 13309

ID 23416. Уравнение с пропущенными цифрами
Темы: Динамическое программирование   

Задано уравнение вида \(A + B = C\), где A, B и C - неотрицательные целые числа, в десятичной записи которых некоторые цифры заменены знаками вопроса (?). Примером такого уравнения является \(?2+34=4?\). Требуется так подставить вместо знаков вопроса цифры, чтобы это равенство стало верным, либо определить, что это невозможно. Найти только одно из  возможных решений.
 
Входные данные: вводится строка, представляющая собой заданное уравнение без пробелов. 
Длина уравнения не превышает 80 символов. 
 
Выходные данные: требуется вывести верное равенство, полученное из исходного уравнения заменой знаков вопроса цифрами, либо сообщение "No solution".
 

Примеры
№ Входные данные Выходные данные
1 ??2?4+9?=355 00264+91=355
 
ID 37892. Муравьиная ферма
Темы: Динамическое программирование   

У мальчика Пети есть муравьиная ферма. На ферме есть участок прямоугольной формы, состоящий из NxM квадратов. В правом нижнем квадрате данной области имеется дырка, благодаря которой можно сбежать с фермы. Каждый день очередной муравьишка начинает свой путь с левой верхней клетки. Далее он перемещается в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться он не может), и двигается так до достижения правой нижней клетки. Затем он выбирается наружу. Каждый муравьишка двигается своим уникальным путем (т.е. никакой муравей не повторяет ни один путь другого). Если муравей не может пойти по своему уникальному пути, то он остается на ферме. Посчитайте, сколько муравьев сбежит с фермы и поселится в комнате Пети.
 
Входные данные
Вводятся два числа N и M - размеры таблицы (\(1<=N<=10\), \(1<=M<=10\)).

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

Примечание
При указанных ограничениях число способов входит в тип Longint.
 

 

Примеры
№ Входные данные Выходные данные
1 1 10 1

 
ID 37893. Дамка
Темы: Динамическое программирование   

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


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

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


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

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

 

 

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

 
ID 30767. Максимальная сумма смежных элементов
Темы: Динамическое программирование    ЕГЭ - вычислительные задачи   

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

 

Примеры
№ Входные данные Выходные данные
1
9
-2
1
-3
4
-1
2
1
-5
4
 6
 
Пояснения: для заданной последовательности чисел (-2 1 -3 4 -1 2 1 -5 4) наибольшую сумму можно получить для смежной последовательности элементов: 4 -1 2 1.
Решение на 2 балла начисляются при прохождении программой 50% тестов, 3 балла - при прохождении программой 75% тестов.

 
ID 33135. Лесопилка
Темы: Динамическое программирование   

Недавно на лесопилку, где работает Вася, поступил новый заказ. Для постройки нового дома мэру соседнего города требуется a досок длины x футов и b досок длины y футов.
 
Поскольку на лесопилке имеется только неограниченный запас досок длины z футов, Васе поручили исполнить заказ клиента, распилив имеющиеся доски на меньшие. Вася хочет закончить работу как можно быстрее, поэтому он хочет выполнить заказ, сделав как можно меньше распилов. При этом количество использованных досок длины z роли не играет, кроме того, часть досок, образовавшихся в результате распила, может не требоваться для заказа и остаться на лесопилке.
 
Например, если на лесопилке имеются доски длины 80, а клиенту требуется две доски длины 30 и семь досок длины 20, то достаточно сделать семь распилов: одну доску распилить двумя распилами на доски длины 20, 30 и 30, одну тремя распилами на четыре доски длины 20 и одну двумя распилами на доски длины 20, 20 и 40. Доска длины 40 клиенту не нужна, она останется на лесопилке, остальные доски будут отправлены клиенту.
 
Входные данные
На вход программы поступают числа a, x, b, y и z. Все числа положительны и не превышают 300, x<=z, y<=z, x!=y.
 
Выходные данные
Выведите  минимальное количество распилов, которые требуется сделать для того, чтобы выполнить заказ.
 
Ввод Вывод
2 30 7 20 80 7

 
ID 38143. Подсчёт коров
Темы: Динамическое программирование   

Коровы Фермера Джона разбрелись по огромному пастбищу, представленному в виде 2D-решётки (шахматной доски).  Размещение коров весьма занимательно. Для каждой ячейки (x,y) с \(x>=0\) и \(y>=0\), существует корова в ячейке (x,y), если для всех целых чисел \(k>=0\), остатки \(\lfloor {\frac {x}{3^k} }\rfloor\) и \(\lfloor {\frac {y}{3^k} }\rfloor\) по модулю 3 имеют одну и ту же четность. Другими словами оба эти остатка нечётные (равны 1) или оба чётные (равны 0 или 2). Например, ячейки для \(0<=x,y<9\), которые содержат коров обозначены цифрой 1 на рисунке ниже. 

 x
    012345678

  0 101000101
  1 010000010
  2 101000101
  3 000101000
y 4 000010000
  5 000101000
  6 101000101
  7 010000010
  8 101000101
Ферме Джон интересуется сколько коров присутствует в определённом квадратном регионе его пастбища. Он задаёт Q вопросов, кажый содержит три целых числа xi,yi,di. Для каждого вопроса Фермер Джон хочет знать, сколько коров в ячейках с (xi, yi) до (xi+di, yi+di) (включая конечные точки).


Входные данные
Первая строка содержит Q (\(1<=Q<=10^4\)) - количество вопросов.
Каждая из следующих Q строк содержит 3 целых числа di, xi, и yi (\(0<=x_i,y_i,d_i<=10^{18}\)).


Выходные данные
Q строк, по одной для каждого вопроса - одно целое число - ответ.
 
 
Примеры
№ Входные данные Выходные данные
1 8
10 0 0
10 0 1
9 0 2
8 0 2
0 1 7
1 1 7
2 1 7
1000000000000000000 1000000000000000000 1000000000000000000		 11
0
4
3
1
2
2
1000000000000000001

ID 38144. Современное искусство - 3
Темы: Динамическое программирование   

Наскучившись стандартными двумерными произведениями искусства (а также разочаровавшись тем, что другие копируют ее работы), великая художница Пикоусо решила перейти к более минималистичному, одномерному стилю. Ее последняя картина может быть описана одномерным массивом цветов длины N (\(1<=N<=300\)), где каждый цвет указывается целым числом в интервале \(1…N\).
К великому разочарованию Пикоусо, ее конкурент Муне, похоже, придумал, как копировать даже эти одномерные картины! Муне закрашивает один интервал одним цветом, ждет, пока он высохнет, затем красит другой интервал и так далее. Муне может использовать каждый из N цветов столько раз, сколько пожелает (возможно ни одного).

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


Входные данные
Первая строка содержит число N. Следующая строка содержит N целых чисел в интервале \(1…N\), указывающих цвет каждой ячейки в картине Пикоусо.

 

Выходные данные
Выведите минимальное количество движений кисти, чтобы скопировать картину.
 
 
Примеры
№ Входные данные Выходные данные
1 10
1 2 3 4 1 4 3 2 1 6		 6
 
Пояснение

В этом примере Муне может скопироват картину так: (незакрашенные ячейки обозначены цветом 0).

Изначально весь массив не закрашен:
0 0 0 0 0 0 0 0 0 0
Муне закрашивает первые 9 ячеек цветом 1:
1 1 1 1 1 1 1 1 1 0
Муне закрашивает интервал цветом 2:
1 2 2 2 2 2 2 2 1 0
Муне закрашивает интервал цветом 3:
1 2 3 3 3 3 3 2 1 0
Муне закрашивает интервал цветом 4:
1 2 3 4 4 4 3 2 1 0
Муне закрашивает одну ячейку цветом 1:
1 2 3 4 1 4 3 2 1 0
Муне закрашивает последнюю ячейку цветом 6:
1 2 3 4 1 4 3 2 1 6
Заметим, что на первом движении кисти можно было закрасить цветом 1 и десятую ячейку. Это не изменило бы финальное состояние.
ID 38444. Деревни
Темы: Динамическое программирование    Алгоритмы на графах    Обход в глубину    Динамическое программирование на графах   

В тридесятом государстве есть N деревень. Некоторые пары деревень соединены дорогами. В целях экономии, “лишних” дорог нет, т.е. из любой деревни в любую можно добраться по дорогам единственным образом.
Новейшие исследования показали, что тридесятое государство находится в сейсмически опасной зоне. Поэтому глава государства захотел узнать, какой именно ущерб может принести его державе землетрясение. А именно, он хочет узнать, какое минимальное число дорог должно быть разрушено, чтобы образовалась изолированная от остальных группа ровно из P деревень такая, что из любой деревни из этой группы до любой другой деревни из этой группы по-прежнему можно будет добраться по неразрушенным дорогам (группа изолирована от остальных, если никакая неразрушенная дорога не соединяет деревню из этой группы с деревней не из этой группы).
Вы должны написать программу, помогающую ему в этом.

Формат входных данных
Первая строка входного файла содержит два числа: N и P (1 ≤ P ≤ N ≤ 150). Все остальные строки содержат описания дорог, по одному на строке: описание дороги состоит из двух номеров деревень (от 1 до N), которые эта дорога соединяет. Все числа во входном файле разделены пробелами и/или переводами строки.

Формат выходных данных
В выходной файл выведите единственное число — искомое количество дорог.

Примеры
№ Входные данные Выходные данные Пояснение
1 3 2
1 2
3 2		 1  
2 11 6
1 2
1 3
1 4
1 5
2 6
2 7
2 8
4 9
4 10
4 11		 2 группа деревень (1, 2, 3, 6, 7, 8) окажется изолированной от остальных, если разрушить дороги 1–4 и 1–5.

ID 38475. Скайлайн
Темы: Динамическое программирование   

Вы хотите, чтобы небоскребы в вашем городе имели красивый вид. Решено построить N небоскребов в ряд. У небоскреба с номером i должно быть ровно h[i] этажей.

У Вас есть предложения от различных строительных компаний. Первая из них предлагает строить один этаж в любом из небоскребов за 3 миллиона евро. Вторая предлагает строить по одному этажу в каждом из двух соседних небоскребов за 5 миллионов евро. Заметим, что не имеет значения, находятся ли эти этажи на одинаковой высоте или нет. Третья компания предлагает строить по одному этажу в каждом из трех последовательных небоскребах за 7 миллионов евро.

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

Входные данные
Первая строка содержит одно целое число N (1 ≤ N ≤ 300). Вторая строка содержит N целых чисел h[1], h[2] ..., h[N], 1 ≤ h[i] ≤ 200.

Выходные данные
В единственной строке выведите одно целое число: минимальную сумму денег для строительства, в миллионах.
ID 38509. Подстроки подпоследовательностей
Темы: Динамическое программирование: один параметр    Динамическое программирование    Дерево отрезков, RSQ, RMQ    Дерево Фенвика   

Назовем подпоследовательностью массива a непустой массив b такой, что он может быть получен из массива a удалением нескольких (возможно, никаких) элементов массива a. Например, массив [1,3]  является попоследовательностью массива [1,2,3] , но [3,1]  не является.

Назовем подотрезком массива a непустой массив b такой, что он может быть получен путем удаления нескольких (возможно, никаких) первых и последних элементов массива a. Например, [1,2]  является подотрезком массива [1,2,3] , а [1,3]  не является. Несложно заметить, что у массива длины n ровно  \( {n(n+1) \over 2}\)  подотрезков.

Назовем массив a длины n возрастающим , если для любого 1 ≤ i ≤ n выполняется ai ≤ ai+1.

Монотонностью массива назовем количество его возрастающих подотрезков.

Дан массив a длины n. Посчитайте сумму монотонностей по всем его подпоследовательностям. Так как ответ может быть очень большим, выведите его по модулю 109+7.

Входные данные
В первой строке задано целое число n (1 ≤ n ≤ 200000) — длина массива a.
Во второй строке заданы n целых чисел (1 ≤ ai ≤ 200000) — элементы массива a.

Выходные данные
Выведите одно целое число — сумму монотонностей всех подпоследовательностей по модулю 109+7.

Примечание
В первом тестовом примере у массива есть 7 подпоследовательностей:

  • У массива [1]  есть ровно один подотрезок и он является возрастающим.
  • У массива [2]  есть ровно один подотрезок и он является возрастающим.
  • У массива [3]  есть ровно один подотрезок и он является возрастающим.
  • У массива [1,2]  есть три подотрезка ([1], [2], [1,2] ) и все они являются возрастающими.
  • У массива [1,3]  есть три подотрезка ([1], [3], [1,3] ) и все они являются возрастающими.
  • У массива [3,2]  есть три подотрезка ([3], [2], [3, 2] ), но только два из них ([3]  и [2] ) являются возрастающими.
  • У массива [1,3,2]  есть шесть подотрезков ([1], [3], [2], [1,3], [3,2], [1,3,2] ) и четыре из них ([1], [3], [2], [1,3] ) являются возрастающими.
Во втором тестовом примере все возрастающие подотрезки всех подпоследовательностей имеют длину 1.
Примеры
№ Входные данные Выходные данные
1 3
1 3 2		 15
2 3
6 6 6		 12

ID 38511. Путешествие по строке
Темы: Дерево отрезков, RSQ, RMQ    sqrt декомпозиция    Хеш    Суффиксный массив    Динамическое программирование    Хеш   

Скажем, что последовательность строк t1 , ..., tk является путешествием длины k , если для всех i > 1 ti является подстрокой ti - 1 строго меньшей длины. Например, { ab , b } является путешествием, а { ab , c } или { a , a } — нет.

Определим путешествие по строке s как путешествие t1 , ..., tk , все строки которого могут быть вложены в s так, чтобы существовали (возможно, пустые) строки u1 , ..., uk + 1 , такие, что s = u1t1u2 t2 ... uk tk uk + 1 . К примеру, { ab , b } является путешествием по строке для abb , но не для bab , так как соответствующие подстроки расположены справа налево.

Назовём длиной путешествия количество строк, из которых оно состоит. Определите максимально возможную длину путешествия по заданной строке s .

Входные данные
В первой строке задано целое число n ( 1 ≤ n ≤ 500 000 ) — длина строки s .

Во второй строке содержится строка s , состоящая из n строчных английских букв.

Выходные данные
Выведите одно число — наибольшую длину путешествия по строке s .

Примечание
В первом примере путешествием по строке наибольшей длины является { abcd , bc , c } .

Во втором примере подходящим вариантом будет { bb , b } .

Примеры
№ Входные данные Выходные данные
1 7
abcdbcc		 3
2 4
bbcb		 2

ID 38515. Бургеры в McDuck's
Темы: Динамическое программирование    Динамическое программирование: два параметра   

Популярная сеть быстрого питания «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

ID 38634. Числовые печеньки - 2
Темы: Комбинаторика    Динамическое программирование   

У Громозеки N печенек. На i-й (1<=i<=N) печеньке написано целое число xi. Он выбирает одну или несколько из этих печенек, так чтобы среднее значение целых чисел, записанных на выбранных печеньках, было равно А.
Какими способами он может сделать свой выбор?

Входные данные
В первой строке вводятся два целых числа N (1<=N<=50) и A (1<=A<=50). Во второй строке N целых чисел - xi (1<=xi<=50).

Выходные данные
Выведите одно число - количество способов выбрать такие печеньки, чтобы среднее значение всех записанных чисел на печеньках было ровно A.
 

 

Примеры
№ Входные данные Выходные данные Примечение
1 4 8
7 9 8 9		 5 Ниже приведены 5 способов выбрать печеньки так, чтобы в среднем было 8.
1) Выберите 3-ю печеньку.
2) Выберите 1-ю и 2-ю печеньки.
3) Выберите 1-ю и 4-ю печеньки.
4) Выберите 1-ю, 2-ю и 3-ю печеньки.
5) Выберите 1-ю, 3-ю и 4-ю печеньки.
2 3 8
6 6 9		 0  
3 8 5
3 6 2 8 7 6 5 9		 19  
4 33 3
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3		 8589934591 Ответ может не соответствовать 32-битному целому числу.

 
ID 39959. Количество сообщений
Темы: Динамическое программирование   

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

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

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

Пример:
 

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

ID 39960. Комфортная поездка Макс
Темы: Динамическое программирование   

Макс находится на начальной станции поезда, и сейчас в него хотят зайти n человек (включая саму Макс). Они уже выстроились в некотором порядке, и для каждого из них известен код города ai, в который они направляются.

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

Комфортность поездки в поезде с людьми на отрезке с l по r равна XOR-у различных кодов городов у людей на отрезке с l по r. Операция XOR также известна как исключающее побитовое ИЛИ.

Общая комфортность выбранных отрезков вычисляется как сумма комфортности каждого отдельного отрезка.

Помогите Макс узнать максимальную достижимую общую комфортность.

Входные данные:
Первая строка содержит натуральное число n - число людей.
Вторая строка содержит n целых чисел ai (0 <= ai <= 5000) - код города, в который направляется i-й человек.

Выходные данные:
Выведите одно целое число - максимальную общую комфортность.

Примеры:
 

Входные данные Выходные данные
6
4 4 2 5 2 3		 14
9
5 1 3 1 5 2 4 2 5		 9

ID 39961. Сумма минимумов
Темы: Динамическое программирование    Дерево отрезков, RSQ, RMQ   

Вам дан массив из n целых чисел. Вам необходимо разделить его на k непустых подотрезков (последовательность подряд идущих элементов) так, чтобы:
1) Каждый элемент массива входил ровно в один подотрезок.
2) Если для каждого подотрезка выбрать минимальное в нем число, то сумма всех минимумов должна быть максимально возможной.

Сообщите сумму минимумов значений в подотрезках этого разбиения.

Входные данные:
В первой строке дается два натуральных числа - n (1 <= n <= 500) и k (1 <= k <= n).
Во второй строке дается n целых чисел - элементы массива ai (1 <= ai <= 105).

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

Пример:
 

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

Пояснение:
Одно из подходящих разбиений: [4, 2], [5], [1, 3]. Сумма минимумов в каждом подотрезке равна 2 + 5 + 1 = 8.
ID 39962. Сжатие строки
Темы: Динамическое программирование    Z-функция. Префикс-функция   

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

Сжатая версия строки s — последовательность строк c1, s1, c2, s2, ..., ck, sk, где ci — десятичная запись числа ai (без лидирующих нулей), а si — некоторая строка из строчных латинских букв. Если Хлоя запишет строку s1 ровно a1 раз, потом s2 ровно a2 раз, и так далее, у нее получится строка s.
Длина сжатой версии равна |c1| + |s1| + |c2| + |s2|... |ck| + |sk|. Среди всех сжатых версий Хлоя хочет выбрать такую, что её длина минимальна. Помогите Хлое определить минимально возможную длину.

Входные данные:
В единственной строке входных данных записана строка s, состоящая из строчных латинских букв (1 ≤ |s| ≤ 5000).

Выходные данные:
Выведите одно целое число — минимальную длину сжатой версии строки s.

Примеры:
 

Входные данные Выходные данные
aaaaaaaaaa 3
abcab 6
cczabababab 7


Пояснения:
В первом примере Хлоя выберет следующую версию: c1 — 10, s1 — a.
Во втором примере Хлоя выберет следующую версию: c1 — 1, s1 — abcab.
В третьем примере Хлоя выберет следующую версию: c1 — 2, s1 — c, c2 — 1, s2 — z, c3 — 4, s3 — ab.
 
ID 39963. Ресторан
Темы: Динамическое программирование    Использование сортировки    Бинарный поиск в массиве   

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

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

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

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

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

Примеры:
 

Входные данные Выходные данные
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

ID 39964. Максимальные вопросы
Темы: Динамическое программирование    Префиксные суммы(минимумы, ...)   

У Макс в блокноте были записаны две строки s длины n и t длины m, состоящие из букв «a» и «b» латинского алфавита. Причем Макс знает, что строка t имеет вид «abab...», то есть на нечетных позициях строки стоит буква «a», а на четных — «b».

Вдруг утром Макс обнаружила, что кто-то испортил ее строку s. Некоторые буквы s были заменены на символ «?».

Назовем последовательность позиций i, i + 1, ..., i + m - 1 вхождением строки t в s, если 1 ≤ i ≤ n - m + 1 и t1 = si, t2 = si + 1, ..., tm = si + m - 1.

Красота строки s оценивается как максимальное количество непересекающихся вхождений строки t в нее. Макс может заменить некоторые из символов «?» на «a» или «b» (символы на разных позициях можно заменять на разные буквы). Макс хочет произвести замены так, чтобы красота строки s была максимально возможной. Из всех таких вариантов она хочет заменить как можно меньше символов «?». Найдите, сколько замен она должна сделать.

Входные данные:
Первая строка содержит одно целое число n (1 ≤ n ≤ 105) — длину строки s.
Вторая строка входных данных содержит строку s длины n, состоящую только из букв «a» и «b» латинского алфавита, а также символов «?».
Третья строка содержит целое число m (1 ≤ m ≤ 105) — длину строки t. Сама строка t содержит «a» на нечетных позициях, и «b» на четных.

Выходные данные:
Выведите единственное целое число — минимальное количество замен, которое должен сделать Вася, чтобы сделать красоту строки s максимально возможной.

Примеры:
 

Входные данные Выходные данные
5
bb?a?
1		 2
9
ab??ab???
3		 2

Пояснения:
В первом примере строка t имеет вид «a». Единственный оптимальный вариант — заменить все символы «?» на «a».
Во втором примере используя две замены можно получить строку «aba?aba??». Больше двух вхождений получить нельзя.
ID 40022. Межрегиональная олимпиада
Темы: Бинарный поиск в массиве    Динамическое программирование    Жадный алгоритм   

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

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

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

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

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

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

Вторая строка должна содержать одно целое число 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

ID 40058. Игра-заливка
Темы: Динамическое программирование   

Вам дана полоска из клетчатой бумаги из n раскрашенных квадратов, пронумерованных от 1 до n слева направо. Квадрат под номером i изначально покрашен в цвет ci.

Скажем, что квадраты i и j лежат в одной компоненте, если ci = cj и ci = ck для всех k, удовлетворяющих i < k < j. Иначе говоря, все квадраты на отрезке от i до j должны иметь одинаковый цвет.
Например, у полоски [3,3,3] есть 1 компонента связности, а у [5,2,4,4] их 3.

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

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

Входные данные:
Первая строка содержит одно целое число n (1 ≤ n ≤ 5000) — количество квадратов.

Вторая строка содержит целые числа c1,c2,…,cn (1 ≤ ci ≤ 5000) — изначальные цвета квадратов.

Выходные данные:
Выведите одно целое число — минимальное количество ходов, которое нужно сделать.

Примеры:
 

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

Пояснение:
Один из оптимальных способов в первом примере: [5, 2, 2, 1] -> [5, 2, 2, 2] -> [5, 5, 5, 5]
ID 40059. Zuma
Темы: Динамическое программирование   

Хлоя недавно установила на свой телефон игру «Zuma». Игроку даётся ряд из n драгоценных камней, i-й из которых имеет цвет ci. Цель игры — уничтожить все камни за как можно меньшее количество секунд.

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

Напомним, что строка (или подстрока) является палиндромом, если она одинаково читается как слева направо, так и справа налево. В данном случае это означает, что цвет первого камня равен цвету последнего камня, цвет второго равен цвету предпоследнего и так далее.

Входные данные:
В первой строке входных данных записано единственное число n (1 ≤ n ≤ 500) — количество камней в изначальном ряду.
Во второй строке записано n целых чисел, i-е из которых равно ci (1 ≤ ci ≤ n) — цвет i-го камня в изначальном ряду.

Выходные данные:
Выведите единственное целое число — минимальное количество секунд, необходимое чтобы удалить все камни.

Примеры:
 

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

Пояснения:
Последовательность в третьем примере: [1, 4, 4, 2, 3, 2, 1] -> [1, 4, 4, 1] -> []
ID 40060. Удаление пар
Темы: Динамическое программирование   

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

Входные данные:
Первая строка содержит одну строку четной длины от 2 до 200, состоящую из строчных букв латинского алфавита.

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

Пример:
 

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

Пояснение:
Можно заменить шестую букву на b, тогда процесс удаления будет выглядеть следующим образом: baddabcc -> baddab -> baab -> bb ->  .
 
ID 21778. Dank numbers
Темы: Динамическое программирование   

Число является dank number, если все его цифры идут в неубывающем порядке. Чтобы получить dank kush, Bonkisilver должен назвать все n-значные dank numbers. Вас не просят узнать все такие числа, Вам лишь нужно вывести их количество.

 
Входные данные
На вход подается число n (0 <= n <= 50).
 
Выходные данные
Выведите одно число - количество n-значных dank number. 
 
 
Примеры
№ Входные данные Выходные данные
1 9 24310
 
ID 21779. MLG pro
Темы: Динамическое программирование    Динамическое программирование: один параметр   

Bonkisilver очень хочет стать MLG pro и попасть в FaZe clan. Для этого он каждый день практикуется в стрельбе из снайперской винтовки. В качестве поощрения, за каждый noscope он получает 2 пачки doritos, а за каждый quickscope - одну. Сколько вариантов сделать выстрелы было у Bonkisilver, если в итоге у него была n-1 пачка.
 
Входные данные
На вход подается число n (1 <= n <= 50).
 
Выходные данные
Выведите одно число - количество вариантов сделать выстрелы. 
 
 
Примеры
№ Входные данные Выходные данные
1 3 2
 
ID 21780. MTN DEW
Темы: Динамическое программирование    Рекуррентные последовательности    Динамическое программирование: один параметр   

Чтобы подготовиться к предстоящей битве Bonkisilver должен прокачать свой скил, а, как известно, лучшим способом это сделать, является употребление mtn dew при прослушивании дабстепа в 4:20 по МСК. Полученный скилл вычисляется по формуле:

f(n) = f(n - 1) + f(n - 2) + f(n / 2),
где n - количество литров mtn dew, выражаемое целым числом. Операция n/2 означает целочисленное деление числа n на 2.

Также, известно, что

f(1) = 1 microCoinZ 
f(x) = 0 microCoinZ, при x < 1.

Помогите Bonkisilver сосчитать полученное количество microCoinZ.
 
Входные данные
На вход подается число n (0 <= n <= 70).
 
Выходные данные
Выведите одно число - полученный скилл. 
 
Примеры
№ Входные данные Выходные данные
1 1 1

PS: Mountain Dew, также MTN DEW — безалкогольный сильногазированный прохладительный напиток, торговая марка американской компании PepsiCo. 
ID 25962. Числа Фибоначчи
Темы: Динамическое программирование    Рекуррентные последовательности   

Числа Фибоначчи определяются рекуррентной формулой:

\(F_0 = F_1 = 1, \\ F_n = F_{n-1} + F_{n-2}, \ при\ n > 2\)

Входные данные
В единственной строке входных данных записано натуральное число n (\(1<=n<=45\)).
 
Выходные данные
Вывести одно n-е число Фибоначчи - Fn.
 
Примеры
№ Входные данные Выходные данные
1 1 1
2 7 21

ID 21812. Завоевание
Темы: Динамическое программирование   

Лорд Петир собирает армию для похода на соседнее королевство. Он хочет, чтобы в его армию вошли все воины каждого из n городов его королевства. Петир выяснил, что в i-м городе ищут работу ai воинов, которых он может завербовать в свою армию.
Исходно в армии Лорда нет ни одного воина. Чтобы воин вошел в армию, Петир может заплатить этому воину. Для вербовки одного воина из i-го города, необходимо заплатить ему ci золотых монет. При этом воины из больших городов ценят свою работу дороже, поэтому если для i-го и j-го города выполнено ai < aj , то ci ≤ cj . Однако есть еще один способ добиться того, чтобы воины присоединились к армии. Если в какой-то момент оказывается, что в армии Лорда Петира уже строго больше воинов, чем осталось в некотором городе, то все воины этого города бесплатно присоединяются к армии Лорда.
Помогите Лорду Петиру выяснить, какое минимальное количество золотых монет он должен заплатить воинам, чтобы все воины из всех городов оказались в его армии.

Входные данные
В первой строке входного файла находится целое число n (1 ≤ n ≤ 1000) — количество городов, в которых Лорд Петир намерен набирать себе воинов. В следующих n строках входного файла находится по два целых числа ai и ci (1 ≤ ai ≤ 100, 1 ≤ ci ≤ 10 000) — количество воинов в i-м городе и число монет, которое необходимо заплатить одному воину в этом городе, чтобы он присоединился к армии. Для всех пар i и j выполнено условие, что если ai < aj , то ci ≤ cj .

Выходные данные
В выходной файл выведите одно целое число — минимальное количество монет, которые Лорду Петиру придется заплатить, чтобы все воины вошли в его армию.
 
Примеры
№ Входные данные Выходные данные
1
3
1 1
2 2
4 3
 5
 
В приведенном примере Лорду необходимо действовать следующим образом. Сначала он платит 2 монеты воину из второго города, и 3 монеты воину из третьего города, чтобы они присоединились
к его армии. Теперь в армии Лорда 2 воина, а в городах осталось 1, 1 и 3 воина, соответственно. Воины из первого и второго городов бесплатно присоединяются к армии Лорда Петира, в его армии становится 4 воина, после чего и оставшиеся 3 воина из третьего города бесплатно присоединяются к его армии.
ID 27053. Упорядочите шарики
Темы: Динамическое программирование   

При игре в новую игру (некоторый гибрид боулинга и бильярда) используется N шариков, пронумерованных числами от 1 до N. В начале игры эти шарики должны быть выложены в линию в порядке своих номеров. В процессе игры их порядок может меняться.
 
Для того, чтобы упорядочить шарики перед началом следующей партии, используется следующее устройство. Это устройство состоит из головки, которая, перемещаясь над шариками, может «засасывать» и «выплевывать» шарики. Чтобы получить большее представление об этом устройстве, представьте себе пылесос, который может засасывать шарики, перемешаться в нужное место, и там, включаясь на продув в обратном направлении, шарики «выплевывать».
 
При засасывании шарика все шарики, которые находились правее засасываемого, сдвигаются влево. «Выплюнуть» шарик можно между любыми двумя шариками (а также перед первым шариком или после последнего), тогда выплевываемый шарик вставляется между этими шариками, и все шарики, которые находятся правее вставляемого, сдвигаются вправо.
 
В устройство может быть одновременно засосано больше одного шарика, при этом при выплевывании шарика первым выплевывается последний засосанный шарик, затем - предпоследний и т.д. (т.е. устройство работает по принципу стека). Шарики выплевываются по одному, т.е. можно выплюнуть только один шарик, остальные оставив внутри устройства (при этом дальше можно как продолжать «выплевывать» шарики в том же или в другом месте, так и засасывать новые шарики).
 
Наиболее энергоемкой из описанных операций является операция засасывания шарика, поэтому хочется минимизировать количество именно таких операций.
 
Напишите программу, которая по данному начальному расположению шариков определит минимальное количество операций засасывания, которое нужно, чтобы расположить шарики в порядке их номеров.
 
Входные данные
Во входном файле задано сначала число N — количество шариков (1<= N <= 1000). Далее идет N чисел, задающих номера шариков в порядке слева направо в их текущем расположении (каждое число — от 1 до N, и каждое из чисел встречается в последовательности ровно один раз).
 
Выходные данные
В выходной файл выведите одно число — минимальное количество операций засасывания шарика, которое потребуется, чтобы расположить шарики в порядке их номеров.
 

Комментарии к примерам тестов
 
1.Можно засосать, например, шарик номер 2 и выплюнуть его между 1-м и 3-м шариком.
 
2. Можно действовать, например, так. Сначала засосем шарик номер 1, затем – шарик номер 2. Затем переместимся в начало и перед 4-м шариком выплюнем шарик (это будет шарик номер 2). Дальше засосем шарик номер 3, и выплюнем его между шариками 2 и 4. Дальше переместимся в начало и там выплюнем шарик номер 1. Впрочем, это не единственный возможный вариант упорядочения шариков в этом примере.

 
Примеры
№ Входные данные Выходные данные
1 3
2 1 3		 1
2 4
4 3 2 1		 3


Командные олимпиады, Московская командная олимпиада, 9-11 классы, 2007, Лига А, Задача F
ID 27082. Кузнечик и лягушки
Темы: Динамическое программирование    Динамическое программирование: один параметр    Рекуррентные последовательности   

Кузнечик прыгает по столбикам, расположенным на одной линии на равных расстояниях друг от друга. Столбики имеют порядковые номера от 1 до N . В начале Кузнечик сидит на столбике с номером 1. Он может прыгнуть вперед на расстояние от 1 до K столбиков, считая от текущего.
 
На некоторых столбиках сидят лягушки, которые едят кузнечиков (Кузнечик не должен попадать на эти столбики!). Определите, сколькими способами Кузнечик может безопасно добраться до столбика с номером N. Учитывайте, что Кузнечик не может прыгать назад.
 
Входные данные
Входная строка содержит натуральные числа N и K , разделённые пробелом. Гарантируется, что 1 <= N, K <=  32 . Во второй строке записано число лягушек L ( 0 <= L <= N - 2 ). В третьей строка записано L натуральных чисел: номера столбиков, на которых сидят лягушки (среди них нет столбиков с номерами 1 и N ).
 
Выходные данные
Программа должна вывести одно число: количество способов, которыми Кузнечик может безопасно добраться до столбика с номером N .

 
Примеры
№ Входные данные Выходные данные
1 6 4
2
2 4		 3

ID 27086. Черепаха
Темы: Динамическое программирование    Динамическое программирование на таблицах   

Черепаха хочет переползти из левого верхнего угла поля размером N на M клеток ( 1 ≤ N , M ≤ 16 ) в правый нижний. За один шаг она может переместиться на соседнюю клетку вправо или на соседнюю клетку вниз. Определите, сколькими различными способами Черепаха может добраться до цели.
 
Входные данные
Входная строка содержит два натуральных числа: размеры поля N и M , разделённые пробелом ( 1 ≤ N , M ≤ 16 ).
 
Выходные данные
Программа должна вывести одно число: количество различных маршрутов из левого верхнего угла поля в правый нижний.
 
 
Примеры
№ Входные данные Выходные данные
1 3 3 6

ID 39370. Все ПСП
Темы: Рекурсия    Динамическое программирование    Перебор    Перебор с возвратом   

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

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

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

Пример:
 

Входные данные Выходные данные
3 ((()))
(()())
(())()
()(())
()()()

ID 33688. Числа Фибоначчи: Мемоизация рекурсии (C++)
Темы: Динамическое программирование    Динамическое программирование: один параметр   

Числа Фибоначчи, обозначаемые обычно F(n) образуют последовательность, называемую последовательностью Фибоначчи, такую, что каждое число является суммой двух предыдущих, начиная с 0 и 1. То есть,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), для n > 1.

По заданному n, вычислите F(n) (0 <= n <= 80).
 

Примеры
№ Входные данные Выходные данные
1 2 1
2 3 2
3 4 3

ID 46616. Числа Фибоначчи: Мемоизация рекурсии (Python)
Темы: Динамическое программирование    Динамическое программирование: один параметр   

Числа Фибоначчи, обозначаемые обычно F(n) образуют последовательность, называемую последовательностью Фибоначчи, такую, что каждое число является суммой двух предыдущих, начиная с 0 и 1. То есть,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), для n > 1.

По заданному n, вычислите F(n) (0 <= n <= 80).

(в коде программы длина одного отступа равна 4 пробелам!)

Примеры
№ Входные данные Выходные данные
1 2 1
2 3 2
3 4 3

ID 46617. N-е число Трибоначчи (рекурсивно)
Темы: Динамическое программирование    Динамическое программирование: один параметр   

Последовательность чисел Трибоначчи (Tn) определяется следующим образом: 

T0 = 0,
T1 = 1,
T2 = 1, и Tn+3 = Tn + Tn+1 + Tn+2 при n >= 0.

Для заданного числа n, определите значение Tn.



Входные данные
Программа получает на вход натуральное число n (0 <= n <= 37). Ответ гарантированно укладывается в рамки 32-разрядного целого числа, т.е. ответ <= 231 - 1.

Выходные данные
Выведите значение Tn.
 
 
Примеры
№ Входные данные Выходные данные
1 4 4
2 25 1389537

ID 46618. Подняться на вершину горы (снизу-вверху)
Темы: Динамическое программирование    Динамическое программирование: один параметр   

Робот Сильвер занимается терроформированием на планете Шелезяка. Сейчас робот находится перед лестницей, ведущей на вершину горы. Лестница состоит из n ступенек. Робот, поднимаясь вверх, может пойти на одну или сразу две ступеньки.
Пока робот поднимается на вершину, вы хотите определить, сколько существует различных способов, которыми он может добраться до последней ступеньки этой лестницы и тем самым оказаться на вершине горы.

Входные данные
Программа получает на вход одно целое число  n - количество ступенек в лестнице (1 <= n <= 45).

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

Примеры
№ Входные данные Выходные данные
1 2 2
2 3 3

ID 46619. Числа Фибоначчи. Динамика снизу вверх
Темы: Динамическое программирование    Динамическое программирование: один параметр   

Числа Фибоначчи, обозначаемые обычно F(n) образуют последовательность, называемую последовательностью Фибоначчи, такую, что каждое число является суммой двух предыдущих, начиная с 0 и 1. То есть,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), для n > 1.

По заданному n, вычислите F(n) (0 <= n <= 80).

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

Примеры
№ Входные данные Выходные данные
1 2 1
2 3 2
3 4 3

ID 46620. Подняться на вершину горы (рекурсивно)
Темы: Динамическое программирование    Динамическое программирование: один параметр   

Робот Сильвер занимается терроформированием на планете Шелезяка. Сейчас робот находится перед лестницу, ведущей на вершину горы. Лестница состоит из n ступенек. Робот, поднимаясь вверх, может пойти на одну или сразу две ступеньки.
Пока робот поднимается на вершину, вы хотите определить, сколько существует различных способов, которыми он может добраться до последней ступеньки этой лестницы и тем самым оказаться на вершине горы.

Входные данные
Программа получает на вход одно целое число  n - количество ступенек в лестнице (1 <= n <= 45).

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

Примеры
№ Входные данные Выходные данные
1 2 2
2 3 3

ID 46621. N-е число Трибоначчи (снизу-вверх)
Темы: Динамическое программирование    Динамическое программирование: один параметр   

Последовательность чисел Трибоначчи (Tn) определяется следующим образом: 

T0 = 0,
T1 = 1,
T2 = 1, и Tn+3 = Tn + Tn+1 + Tn+2 при n >= 0.

Для заданного числа n, определите значение Tn.



Входные данные
Программа получает на вход натуральное число n (0 <= n <= 37). Ответ гарантированно укладывается в рамки 32-разрядного целого числа, т.е. ответ <= 231 - 1.

Выходные данные
Выведите значение Tn.
 
Попробуйте решить эту задачу без использования массивов и других структур данных! Другими словами, ваша программа должна использовать фиксированный объем памяти, не зависящий от входных данных (О(1)).

 
Примеры
№ Входные данные Выходные данные
1 4 4
2 25 1389537

ID 46622. Стоимость проезда
Темы: Динамическое программирование    Динамическое программирование: один параметр   

Робот Сильвер движется по платному шоссе на планете Шелезяка. На каждом километре шоссе расположен пункт оплаты. Всего на шоссе n пунктов оплаты. Первый пункт оплаты находится в самом начале шоссе, n-й пункт оплаты находится в начале последнего километра шоссе. Заплатив нужную сумму в i-м пункте оплаты, робот может двигаться дальше либо до следующего пункта оплаты, либо же до того, который находится через 2 километра (то есть, если робот находится в пункте i, то он может двигаться либо до пункта i+1, либо до пункта i+2). Первую оплату можно сделать либо в первом пункте, либо во втором (на выбор). Если оплаты была произведена в предпоследнем (n-1) пункте, то можно просто доехать до конца  шоссе, не оплачивая проезд в последнем пункте.
Зная стоимость проезда через определенный пункт оплаты, помогите роботу Сильверу найти наименьшую стоимость проезда через все шоссе, которую должен будет заплатить Сильвер.

Входные данные
В первой строке записано количество пунктов оплаты n (2 <= n <= 1000). Во второй строке записыны n целых чисел (costi) - стоимость проезда через i-й пункт оплаты (1 <= i <= n, 0 <= costi <= 999).

Выходные данные
Выведите одно число - ответ на задачу.
 
 

Примеры
№ Входные данные Выходные данные
1 3
10 15 20		 15
2 10
1 100 1 1 1 100 1 1 100 1		 6

ID 46697. Маршрут наименьшей стоимости
Темы: Динамическое программирование    Динамическое программирование: один параметр   

Робот Сильвер движется по платному шоссе на планете Шелезяка. На каждом километре шоссе расположен пункт оплаты. Всего на шоссе n пунктов оплаты. Первый пункт оплаты находится в самом начале шоссе, n-й пункт оплаты находится в начале последнего километра шоссе. Заплатив нужную сумму в i-м пункте оплаты, робот может двигаться дальше либо до следующего пункта оплаты, либо же до того, который находится через 2 километра (то есть, если робот находится в пункте i, то он может двигаться либо до пункта i+1, либо до пункта i+2). Первую оплату можно сделать либо в первом пункте, либо во втором (на выбор). Если оплаты была произведена в предпоследнем (n-1) пункте, то можно просто доехать до конца  шоссе, не оплачивая проезд в последнем пункте.
Зная стоимость проезда через определенный пункт оплаты, помогите роботу Сильверу найти наименьшую стоимость проезда через все шоссе, которую должен будет заплатить Сильвер, а также пункты оплаты, на которых ему необходимо будет остановиться. 

Входные данные
В первой строке записано количество пунктов оплаты n (2 <= n <= 1000). Во второй строке записыны n целых чисел (costi) - стоимость проезда через i-й пункт оплаты (1 <= i <= n, 0 <= costi <= 999).

Выходные данные
Выведите в первой строке наименьшую стоимость проезда через шоссе. 
Во второй строке выведите через пробел номера пунктов оплаты (по возрастанию), на которых роботу придется остановиться, чтобы оплатить проезд. Если вариантов маршрута с остановками в пунктах оплаты несколько, то выведите любой из них.
 
 

Примеры
№ Входные данные Выходные данные
1 3
10 15 20		 15
2
2 10
1 100 1 1 1 100 1 1 100 1		 6
1 3 5 7 8 10

ID 46698. Калькулятор с восстановлением ответа
Темы: Динамическое программирование: один параметр    Динамическое программирование   

Имеется калькулятор, который выполняет три операции:
  1. Прибавить к числу X единицу.
  2. Умножить число X на 2.
  3. Умножить число X на 3.
Определите кратчайшую последовательность операций, необходимую для получения из числа 1 заданное число N.
 
Входные данные
Программа получает на вход одно число X, не превосходящее 106.

Выходные данные
Выведите строку, состоящую из цифр "1", "2" или "3", обозначающих одну из трех указанных операций, которая получает из числа 1 число N за минимальное число операций. Если возможных минимальных решений несколько, выведите любое из них. 
 
 
Примеры
№ Входные данные Выходные данные
1 1  
2 5 121
3 562340 3333312222122213312