Темы --> Информатика --> Алгоритмы --> Динамическое программирование --> Динамическое программирование: два параметра --> Динамическое программирование: последовательности
---> 46 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 4 5 6 7 8 9 10 >> Отображать по:
#3674
Игра на бирже
  
#111134
Шахтеры
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
512 megabytes

На двух угольных шахтах работают шахтеры. Добыча угля — тяжелая работа, так что шахтерам необходимо доставлять еду прямо в шахты. Каждый раз, когда очередная порция продовольствия доставляется в шахту, шахтеры производят некоторое количество угля. Существует три типа еды для шахтеров: мясо, фрукты и бублики. Шахтеры любят разнообразие в еде и будут работать продуктивнее, если их диета будет разнообразной. Точнее, каждый раз, когда в шахту доставляется новая порция продовольствия, необходимо посмотреть на две предыдущие поставки (или меньше чем две, если их еще не было) и действовать по следующему правилу:

  • если вся еда была одинаковой — будет произведена одна тонна угля
  • если еды была двух типов — будет произведено две тонны угля
  • если трех типов — три тонны угля

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

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

Первая строка содержит число N (1 ≤ N ≤ 100 000) — количество поставок еды. Вторая строка содержит N символов — типы поставок в том порядке, в котором они будут осуществляться. Каждый из символов будет большой латинской буквой M (мясо), F (фрукты) или B (бублики).

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

Выведите единственное число — количество тонн угля, которое можно добыть.

Примеры тестов

Входные данные
6
MBMFFB
Выходные данные
12
Входные данные
16
MMBMBBBBMMMMMBMB
Выходные данные
29

Подзадача 1.
\(1 \le N \le 27\). Решение оценивается в \(30\) баллов.
Подзадача 2.
Дополнительные ограничения отсутствуют. Решение оценивается в \(70\) баллов.

#111227
Ордынское войско
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Готовясь к бою, хан Гирей пронумеровал всех воинов своего войска натуральными числами от 1 до N. Поскольку воины умеют сражаться, но не умеют считать, при любом построении в шеренгу они выстраиваются в произвольном порядке. Одного или несколько воинов, стоящих в шеренге, будем называть отрядом. Отряд назовем правильным, если номера этих воинов в том порядке, в котором они стоят в шеренге, образуют упорядоченную по возрастанию последовательность чисел. Среди всех правильных отрядов хан Гирей выбирает ударный отряд – самый большой по количеству воинов. Так, в шеренге 1 3 2 4 из четырех воинов ударными являются отряды 1 3 4 и 1 2 4, а отряд 1 4 – один из правильных, но не ударный. Некоторые воины являются личными телохранителями хана Гирея. Требуется составить программу, определяющую количество таких шеренг, в которых телохранители хана образуют ударный отряд.

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

В первой строке входного файла задано натуральное число N – общее количество воинов (1 ≤ N ≤ 15). Во второй строке задано натуральное число K – количество телохранителей хана (1 ≤ K ≤ N). В третьей строке через пробел указаны K различных натуральных чисел, не превосходящих N, – номера телохранителей хана в порядке возрастания.

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

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

Примечание

В первом примере войско состоит из пяти воинов. Ударный отряд должен состоять из трех воинов с номерами 1, 3 и 4. Этому условию удовлетворяют следующие 11 шеренг: (1, 3, 2, 5, 4), (1, 3, 5, 2, 4), (1, 3, 5, 4, 2), (1, 5, 3, 2, 4), (1, 5, 3, 4, 2), (2, 1, 3, 5, 4), (2, 1, 5, 3, 4), (2, 5, 1, 3, 4), (5, 1, 3, 2, 4), (5, 1, 3, 4, 2), (5, 2, 1, 3, 4).

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

  1. (оценивается в 40 баллов) 1 ≤ N ≤ 8.

  2. (оценивается в 10 баллов) 9 ≤ N ≤ 10.

  3. (оценивается в 10 баллов) N = 11.

  4. (оценивается в 10 баллов) N = 12.

  5. (оценивается в 10 баллов) N = 13.

  6. (оценивается в 10 баллов) N = 14.

  7. (оценивается в 10 баллов) N = 15.

Примеры
Входные данные
5
3
1 3 4
Выходные данные
11
Входные данные
3
3
1 2 3
Выходные данные
1
Входные данные
1
1
1
Выходные данные
1
#111490
A + B = C
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Часто для пробного тура на различных олимпиадах по информатике предлагается задача «A + B», в которой по заданным целым числам \(A\) и \(B\) требуется найти их сумму.

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

Пусть председатель жюри выбрал число \(C\), запись которого состоит из \(n\) десятичных цифр и не начинается с нуля. Теперь он хочет подобрать такие целые положительные числа \(A\) и \(B\), чтобы их сумма была равна \(C\), и запись каждого из них также состояла из \(n\) десятичных цифр и не начиналась с нуля. В дополнение к этому председатель жюри старается подобрать такие числа \(A\) и \(B\), чтобы каждое из них было красивым. Красивым в его понимании является число, запись которого не содержит двух одинаковых подряд идущих цифр. Например, число 1272 считается красивым, а число 1227 — нет.

Требуется написать программу, которая для заданного натурального числа \(C\) вычисляет количество пар красивых положительных чисел \(A\) и \(B\), сумма которых равна \(C\). Поскольку количество пар красивых чисел может быть большим, необходимо вывести остаток от деления этого количества на число \(10^9+7\).

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

Входной файл содержит одно целое положительное число \(C\). Число \(C\) не начинается с нуля. Количество цифр в записи числа \(С\) не превышает \(10000\).

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

Выходной файл должен содержать одно целое число — остаток от деления количества искомых пар красивых чисел \(A\) и \(B\) на число \(10^9+7\).

Система оценивания

Правильные решения для тестов, в которых 1 ≤ C ≤ 999 (1 ≤ n ≤ 3), будут оцениваться из 25 баллов.

Правильные решения для тестов, в которых 1 ≤ C ≤ 999 999 (1 ≤ n ≤ 6), будут оцениваться из 50 баллов.

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

Пояснения к тестам

Число 22 можно представить в виде суммы двузначных чисел тремя способами: 10 + 12, 11 + 11, 12 + 10. Способ 11 + 11 не подходит, поскольку число 11 не является красивым. Следовательно, ответ для числа 22 равен 2.

Число 200 можно представить в виде суммы трехзначных чисел единственным способом: 100 + 100. Этот способ не подходит, поэтому ответ для числа 200 равен 0.

Число 1000 нельзя представить в виде суммы четырехзначных чисел, поэтому ответ для числа 1000 аналогично равен 0.

Примеры
Входные данные
22
Выходные данные
2
Входные данные
200
Выходные данные
0
Входные данные
1000
Выходные данные
0
Входные данные
239
Выходные данные
16
#113104
Расстояние Дамерау-Левенштейна
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Одной из наиболее распространенных опечаток при наборе текста является перестановка двух соседних символов, например, вместо слова «программа» набрано слово «прогармма». Расстояние Левенштейна не учитывает такие опечатки: при вычислении расстояния Левенштейна одна перестановка будет считаться за два редактирования (например, удаление и вставка символа).

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

Определите расстояние Дамерау-Левенштейна для двух данных строк.

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

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

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

Требуется вывести одно число – расстояние Дамерау-Левенштейна для данных строк.

Примеры
Входные данные
XABCDE
ACBYDF
Выходные данные
4
Страница: << 4 5 6 7 8 9 10 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест