Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Постройка забора#24762

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

Забор представляет собой многоугольник ненулевой площади, сторонами которого являются доски. Пилить или ломать доски нельзя. Например, из трех досок с длинами 10, 11 и 12 можно построить забор, а из четырех досок с длинами 100, 1, 2 и 3 — нельзя.

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

Пожилым людям надо помогать, так что вам не составит труда решить для них эту задачу! Количество способов может быть довольно большим, поэтому выведите остаток от деления этого количества на число 10⁹ + 7.

Формат входного файла
В первой строке входного файла находится одно натуральное число n (1 ≤ n ≤ 4000) — количе- ство досок. Во второй строке дано n чисел li (1 ≤ l_i ≤ 4000) — длины досок.

Формат выходного файла
В выходной файл выведите одно число — количество способов выбрать доски для постройки забора, взятое по модулю 10⁹ + 7.

Ввод	Вывод
3 10 11 12	1
4 100 1 2 3	0
4 5 5 5 5	5

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

✓ 5✗ 441 100средняяВойти и решать

Уравнение с пропущенными цифрами#23416

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

Входные данные
Вводится строка, представляющая собой заданное уравнение без пробелов. Длина уравнения не превышает 80 символов.

Выходные данные
Требуется вывести верное равенство, полученное из исходного уравнения заменой знаков вопроса цифрами, либо сообщение "No solution".

Примеры

№	Входные данные	Выходные данные
1	`??2?4+9?=355`	`00264+91=355`

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

✓ 2✗ 371 300средняяВойти и решать

Восстановление скобок#23412

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

Входные данные
Вводится строка, которая содержит заданный шаблон длиной не более 80 символов.

Выходные данные
Выведите искомое количество способов. Исходные данные будут таковы, что это количество не превзойдет 2·10⁹.

Примеры

№	Входные данные	Выходные данные
1	`????(?`	`2`

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

✓ 116✗ 190800средняяВойти и решать

Билеты в театр#23364

Не так давно в городе будущего Иннополис достроили первый театр. После тяжелой рабочей недели студенты университета решили сходить в театр. Утром они приехали к открытию кассы театра, чтобы успеть купить билеты. Билет в театр стоит 100 рублей.

Оказалось, что у каждой девочки есть ровно одна банкнота номиналом 100 рублей, а у каждого мальчика — номиналом 1000 рублей. До ребят еще никто не успел купить билет, поэтому касса пуста. Это значит, что кассир выдает сдачу только теми банкнотами, которые получил от других ребят, стоявших раньше в очереди. Кассир обслуживает всех по очереди и не начинает обслуживать следующего человека, если еще не продал билет или не выдал требуемую сдачу предыдущему.

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

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

Формат входных данных
В первой строке задано два целых неотрицательных числа n и m, где n — количество девочек, m — количество мальчиков (1<= n + m < 10⁴).

Формат выходных данных
Выведите остаток от деления числа способов расставить студентов в очередь, чтобы все смогли купить билет, на 10⁹ + 7.

Ввод	Вывод
18 2	10
8 1	0
12 1	4

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

✓ 3✗ 651 100средняяВойти и решать

Число способов#22015

В прямоугольной таблице NxM в начале игрок находится в левой верхней клетке.

За один ход ему разрешается перемещаться в соседнюю клетку

либо вправо, либо вниз (влево и вверх перемещаться запрещено).

Посчитайте, сколько есть способов у игрока попасть в правую

нижнюю клетку.

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

Во входном файле задано два числа N и M - размеры таблицы (1<=N<=10,

1<=M<=10).

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

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

Примечание

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

Пример входного файла

2 3

Пример выходного файла

Пояснение

Если у нас есть таблица из 2 строк и 3 столбцов, то существуют следующие

способы попасть из левого верхнего угла в правый нижний:

1) вниз, вправо, вправо

2) вправо, вниз, вправо

3) вправо, вправо, вниз

Еще один пример входного файла

3 3

Пример выходного файла

Динамическое программирование на таблицах Динамическое программирование: один параметр Комбинаторика

✓ 21✗ 29800средняяВойти и решать

Кладовка из Простоквашино#21996

Сразу же после заселения в новый дом в Простоквашино кот Матроскин, Шарик и дядя Фёдор затеяли ремонт. Непосредственно перед его началом они обнаружили, что в доме отсутствует кла- довка для стройматериалов, и наспех пристроили её к дому. Как только вспомогательное строение было готово, встал вопрос о необходимости провести туда электричество и повесить лампочку.

Обсудив вопросы электрификации новых помещений с почтальоном Печкиным, наши герои узна- ли много полезной информации. Чтобы посетители не мучились с выбором, в деревенском магазине продаётся только один вид лампочек, зато в неограниченных количествах. Стоит одна лампочка ни дорого, ни дёшево, а ровно C рублей. Правда, лампочки в магазине не самые качественные, и вклю- чить каждую из них можно только K раз, а на K + 1 включение она перегорает. Недостаток этот компенсируется тем, что во включенном состоянии лампочка перегореть не может. К сожалению, электроэнергия в Простоквашино недешевая, и каждая минута работы лампочки обойдется дяде Фёдору и его друзьям в D рублей.

Узнав всё это, экономный Матроскин составил поминутный график из N предполагаемых посе- щений кладовки. Каждый визит в новое помещение задаётся моментом входа ai и моментом выхода bi . Таким образом, i-й визит продолжается ровно b_i − a_iминут.

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

Формат входных данных
В первой строке входных данных записаны четыре целых числа N, K, C, D — количество пла- нируемых посещений кладовки, количество успешных включений для одной лампочки, стоимость покупки лампочки и стоимость минуты работы лампочки соответственно (1 <= N, K <= 200 000, 1 <= C, D <= 10⁹ ). В следующих N строках даны по два целых положительных числа ai и bi , описывающих пред- полагаемые визиты в кладовку (1 <= a_i < b_i <= 10⁹ ). Посещения не пересекаются по времени и упорядочены, то есть b_i < a_i+1.

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

Ввод	Вывод
1 2 5 6 3 5	12
3 1 15 10 1 3 4 5 30 35	105

Замечание
Замечание В первом примере достаточно заплатить только за электроэнергию: лампочка должна быть включена на третьей минуте и выключена на пятой, стало быть, суммарные затраты составляют (5 − 3) × 6 = 12.
Во втором примере выгодно не выключать лампочку между первым и вторым посетителем, а для третьего использовать уже новую лампочку

Динамическое программирование Динамическое программирование: один параметр Префиксные суммы(минимумы, ...)

✓ 13✗ 1651 000средняяВойти и решать

Выборы#21952

Скоро в Соединенных Штатах Берляндии пройдут выборы президента. На эту ответственную должность претендуют два кандидата: Дядя Сэм и Дядя Фродо. Вы работаете аналитиком в пред- выборном штабе Дяди Сэма, и вам поручено помочь ему победить конкурента. Раздуть газетный скандал из одержимости оппонента бросанием колец в жерла вулканов не получилось, так что при- дётся воспользоваться математикой.

Казалось бы, чтобы выиграть, необходимо убедить проголосовать за нашего кандидата более половины пришедших на выборы. Оказывается, что иногда нужно гораздо меньше! Для того чтобы понять, как это возможно, рассмотрим подробнее процедуру голосования.

Как вы знаете, Соединенные Штаты Берляндии разделены на несколько административных ре- гионов первого уровня — штатов. Сначала в каждом из штатов проходят местные выборы, по итогам которых каждый штат отдаёт свой голос за одного из кандидатов. Если не менее половины штатов выбрало Дядю Сэма, то выигрывает он (в случае равенства голосов Дядя Сэм имеет преимущество как действующий президент), иначе побеждает Дядя Фродо. Все штаты, в свою очередь, состоят из административных регионов второго уровня, каждый из которых представлен выборщиком из административных регионов третьего уровня и так далее. Последний уровень состоит из отдельных жителей Берляндии. Всего в Берляндии N жителей и K уровней административных единиц. Одним из ключевых принципов этой страны является равенство, так что любой регион i-го уровня делится на одинаковое число регионов следущего уровня (в том числе содержит одинаковое число граждан).

Так получилось, что делением на регионы поручили заняться именно вам, то есть в ваших руках назначить, на сколько именно административных единиц i-го уровня делится (i−1)-ая администра- тивная единица.

Также у вас есть сильный инструмент влияния на выбор людей — нефтяные бурли. Чтобы заста- вить одного избирателя отдать свой голос за Дядю Сэма, достаточно дать ему скромный подарок в размере одного нефтяного бурля.

К несчастью, изначально все N жителей Соединённых Штатов Берляндии собираются отдать свой голос за Дядю Фродо. Требуется определить минимальное количество нефтяных бурлей, ко- торое достаточно потратить для победы на выборах.

Формат входных данных

В единственной строке ввода находятся два целых числа N и K (1 <= N <= 10¹⁵ , 1 <= K <= 10).

Формат выходных данных
Требуется вывести единственное число — минимальное количество нефтяных бурлей, которое придётся потратить на предвыборные подарки при наилучшем разбиении на регионы.

Примеры

Ввод	Вывод
9 2	4
12 3	2

Замечание
Берляндские законы не запрещают, чтобы страна состояла из одного штата, а город — одного жителя. Аналогично с остальными типами регионов.

На рисунке 1 черным цветом отмечены те регионы, в которых победил Дядя Сэм. На нижнем уровне черными изображены вершины, соответствущие подкупленным конкретным жителям.

Алгоритмы на графах Динамическое программирование Динамическое программирование: один параметр Простые числа и разложение на множители

✓ 2✗ 771 200средняяВойти и решать

Укладка плитки#21902

В процессе ремонта в Лаборатории Информационных Технологий строителям необходимо заменить поврежденные напольные плитки в коридоре лаборатории, который имеет размер 2 × n метров. В распоряжении строителей есть неограниченный запас плиток двух размеров: 1 × 2 метра и 1 × 1 метр. При этом плитки размером 1 × 2 метра перед укладкой разрешается поворачивать на 90 градусов и размещать как вдоль, так и поперек коридора.

Строители уже начали ремонт и уложили в некоторых местах пола коридора k плиток размером 1 × 1. Для завершения ремонта прорабу необходимо подготовить план дальнейших работ. Для этого ему надо решить, каким образом уложить плитки на места, где они еще не уложены. Это можно сделать различными способами и прораб хочет перебрать все варианты и выбрать самый удачный. Перед тем как это сделать, прораб хочет знать, какое количество вариантов ему придется рассмотреть. Это число требуется найти по модулю 10⁹ + 7.

Требуется написать программу, которая по заданной длине коридора n и расположению плиток, которые уже уложены, определяет количество способов укладки плиток на оставшиеся места. Ответ необходимо вывести по модулю 10⁹ + 7.

Формат входного файла
Первая строка входного файла содержит два целых числа: n — длину коридора и k — количество уже уложенных единичных плиток (1 ≤ n ≤ 100 000, 0 ≤ k < 2n). Последующие k строк содержат по два целых числа xi и yi , которые задают позиции уже уложенных единичных плиток, i-я плитка уложена на xi-м метре коридора в yi-м ряду (1 ≤ xi ≤ n, 1 ≤ yi ≤ 2).

Формат выходного файла
Выходной файл должен содержать одно целое число — количество способов укладки плиток в коридоре, взятое по модулю 10⁹ + 7.

Ввод	Вывод
2 0	7
3 0	22
3 1 2 1	8

Динамическое программирование по профилю Динамическое программирование: один параметр

✓ 3✗ 11 200средняяВойти и решать

MLG pro#21779

Bonkisilver очень хочет стать MLG pro и попасть в FaZe clan. Для этого он каждый день практикуется в стрельбе из снайперской винтовки. В качестве поощрения, за каждый noscope он получает 2 пачки doritos, а за каждый quickscope - одну. Сколько вариантов сделать выстрелы было у Bonkisilver, если в итоге у него была n-1 пачка.

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

На вход подается число n (1 <= n <= 50).

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

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

Примеры

№	Входные данные	Выходные данные
1	3	2

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

✓ 113✗ 304700средняяВойти и решать

Бинарная сила#90900

Вы играете в игру «Бинарная Сила» и управляете персонажем, у которого есть 𝑑 = 2^𝑛 навыков, пронумерованных 1 до 𝑑. Эти навыки расположены на листьях полного двоичного дерева высоты 𝑛, изначально все навыки имеют уровень 1. Пример такого дерева для 𝑛 = 3 приведен на иллюстрации ниже.

После этого вы начинаете прокачивать навыки следующим образом.
• Навыки прокачиваются посредством заполнения двоичного дерева снизу вверх.
• Для очередной вершины дерева вы должны выбрать и записать в нее один из двух навыков, записанных в
непосредственных детях этой вершины (на рисунке из детей в родителя ведут стрелки).
• Уровнем навыка считается число вершин, в которых выбран этот навык.
Пример корректного распределения навыков по дереву для 𝑛 = 3 приведен ниже.

В этом примере первый навык имеет уровень 4, седьмой – уровень 3, четвертый и пятый – уровень 2, а второй, третий, шестой и восьмой не были прокачаны ни разу, поэтому остались на уровне 1.
Кроме прокачки персонажа, в игре есть 𝑚 различных квестов, с помощью которых можно получать монетки. Квесты активируются после того, как все дерево навыков было заполнено.
Квесты бывают трех типов:
1. «𝑙𝑒𝑠𝑠 𝑥𝑖 𝑘𝑖 𝑠𝑖» – вы получите 𝑠𝑖 монет, если уровень навыка с номером 𝑥𝑖 окажется строго меньше 𝑘𝑖 .
2. «𝑒𝑥𝑎𝑐𝑡 𝑥𝑖 𝑘𝑖 𝑠𝑖» – вы получите 𝑠𝑖 монет, если уровень навыка с номером 𝑥𝑖 окажется равен 𝑘𝑖 .
3. «𝑙𝑒𝑠𝑠 𝑥𝑖 𝑘𝑖 𝑠𝑖» – вы получите 𝑠𝑖 монет, если уровень навыка с номером 𝑥𝑖 окажется строго больше 𝑘𝑖 .
Так как монеты – очень ценный ресурс в игре «Бинарная Сила», вы хотите узнать максимальное количество монет, которое возможно получить с помощью имеющихся квестов после улучшения всех навыков.

Формат входных данных
Каждый тест состоит из нескольких независимых наборов входных данных. Первая строка содержит одно целое число 𝑡 – количество наборов входных данных (1 ≤ 𝑡 ≤ 10⁴). Далее следует описание наборов входных данных.
Каждый набор начинается со строки, содержащей два целых числа 𝑛 и 𝑚 – высоту дерева навыков и количество квестов соответственно (1 ≤ 𝑛 ≤ 15; 0 ≤ 𝑚 ≤ 50 000). Число навыков при этом равно 𝑑 = 2^𝑛.
Далее следуют 𝑚 строк, 𝑖-я из которых содержит четыре целых числа 𝑡𝑖, 𝑥𝑖, 𝑘𝑖, 𝑠𝑖 – тип квеста и его описание (1 ≤ 𝑡𝑖 ≤ 3; 1 ≤ 𝑥𝑖 ≤ 𝑑; 1 ≤ 𝑘𝑖 ≤ 𝑛; 1 ≤ 𝑠𝑖 ≤ 10⁹). Типы квестов следуют в том же порядке, в котором они перечислены в условии: 𝑡𝑖=1 соответствует квесту типа «𝑙𝑒𝑠𝑠», 𝑡𝑖 = 2 – квесту типа «𝑒𝑥𝑎𝑐𝑡» и 𝑡𝑖 = 3 – квесту типа «𝑚𝑜𝑟𝑒».
Гарантируется, что сумма 𝑑 по всем наборам входных данных не превосходит 2¹⁶ и сумма 𝑚 по всем наборам входных данных не превосходит 50 000

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

графы Динамическое программирование на поддеревьях дп

—Войти и решать

Why Did the Cow Cross the Road II#90427

Фермер Джон растит $N$ пород коров ($1 \leq N \leq 1000$), последовательно пронумерованных $1 \ldots N$. Некоторые пары пород не так дружественны, как другие и это определяется номерами пород: породы $a$ и $b$ дружественны если $|a - b| \leq 4$, и не дружественны в противном случае.

Длинная дорога проходит через ферму Джона. Имеется последовательность из $N$ полей на одной стороне дороги (по одному полю для каждой породы), и последовательность из $N$ полей на другой стороне дороги, также по одному полю для каждой породы. Чтобы помочь своим коровам безопасно переходить дорогу, ФД хочет нарисовать "зебры" через дорогу. Каждая "зебра" должна соединить поле на одной стороне дороги с полем на другой стороне дороги где два поля имеют дружественные породы коров.

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

ФОРМАТ ВВОДА (файл nocross.in):

Первая строка ввода содержит число $N$. Следующие $N$ строк описывают порядок, по номерам пород полей вдоль одной стороны дороги. Каждый номер породы - это целое число в интервале $1 \ldots N$. Последние $N$ строк описывают порядок, по номерам пород полей вдоль другой стороны дороги. Каждая порода появится ровно один раз в каждом порядке.

ФОРМАТ ВЫВОДА (файл nocross.out):

Выведите максимальное количество непересекающихся "дружественных зебр", которые ФД может нарисовать вдоль дороги.

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

—Войти и решать

Cow Hopscotch (Silver)#90409

Фермер Джон придумал игру для своих коров

Она играется на решётке R*C (2 <= R <= 100, 2 <= C <= 100), где каждый квадрат помечен целым числом от 1 до K (1 <= K <= R*C). Коровы выполняют последовательность прыжков, начиная в левом верхнем квадрате и заканчивая в правом нижнем квадрате и прыжок является корректным если и только если:

1) Вы прыгаете на квадрат c другим числом

2) Квадрат, куда Вы прыгаете, как минимум на одну строку ниже квадрата, в котором Вы сейчас стоите

3) Квадрат, в который Вы прыгаете как минимум на одну колонку правее квадрата, в котором Вы сейчас стоите

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

Формат входных данных

Первая строка ввода содержит целые числа R, C, K. Каждая из следующих R строк содержит C целых чисел, каждое в интервале 1..K.

Формат выходных данных

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

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

—Войти и решать

Cow Hopscotch (Bronze)#90404

Фермер Джон придумал игру для своих коров.

Она играется на решётке R*C (2 <= R <= 15, 2 <= C <= 15), где каждый квадрат раскрашем красным либо синим цветом. Коровы начинают в левом верхнем углу и двигаются в правый нижний последовательными прыжками. Прыжок является корректным если и только если:

1) Вы прыгаете на квадрат другого цвета

2) Квадрат, куда Вы прыгаете, как минимум на одну строку ниже квадрата, в котором Вы сейчас стоите

3) Квадрат, в который Вы прыгаете как минимум на одну колонку правее квадрата, в котором Вы сейчас стоите

Формат входных данных

Первая строка содержит два целых числа R и C. Каждая из следующих R строк содержит ровно C символов. Каждый символ или R или B (обозначающих соответтсвенно красный или синий квадрат)

Формат выходных данных

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

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

—Войти и решать

COW#90402

Беси стоит перед огромным камнем в середине своего любимого поля. На камне - шифровка на древнем языке, алфавит которого состоит только из трёх букв C, O, W. Беси интересно, сколько раз встретилось слово COW в тексте.

Бесси не возражает если другие букв встречаются между C O W. Также Беси считает разными слова, в которых отличается хоть одна буква. Например COW встречается только один раз в слове CWOW, два раза в слове CCOW, и 8 раз в слове CCOOWW.

По заданному тексту шифровки помогите Беси посчитать сколько раз появится слово COW.

Формат входных данных

Первая строка ввода содержит одно целое число N <= 10^5. Вторая строка содержит строку из N символов, каждый их которых либо C, либо O, либо W.

Формат выходных данных

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

Заметим, что ответ может быть очень большим, поэтому нужно из пользовать 64-битную целую величину (long long в С++ или long в Java).

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

—Войти и решать

Secret Cow Code#90401

Коровы экспериментируют с секретными кодами, и они изобрели метод для создания строки с бесконечной длиной которая может быть использована для кодирования.

Пусть дана строка $s$, назовём $F(s)$ строку $s$ за которой идёт строка $s$ "циклически сдвинутая" на один символ вправо (последний символ становится новым первым символом). По заданной строке $s$, коровы строят свою строку бесконечной длины повторя применение $F$; каждый шаг удваивает длину текущей строки.

Вам дана начальная строка и индекс $N$, помогите коровам вычислить символ на позиции $N$, в этой бесконечной строке.

ФОРМАТ ВВОДА (файл cowcode.in):

Ввод состоит из одной строки, содержащий строку, за которой следует число $N$. Строка содержит не более 30 больших латинских букв, $N \leq 10^{18}$.

Заметим, что $N$ может не поместиться в 32-битное целое, поэтому нужно использовать 64-битное целое (например long long для С/С++).

ФОРМАТ ВЫВОДА (файл cowcode.out):

Выведите $N$-ый символ в бесконечной строке построенной по данной. Первый символ имеет $N=1$.

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

—Войти и решать

Subsequence Reversal#90398

Фермер Джон выстроил $N$ своих коров в ряд, чтобы сделать фото ($1 \leq N \leq 50$). Высота $i$-ой коровы в этом ряду есть $a(i)$, и ФД думает, фото будет эстетически приятным, если будет иметь большую возрастающую по росту коров подпоследовательность.

Напомним, подпоследовательность это подмножество $a(i_1), a(i_2), \ldots, a(i_k)$ элементов из последовательности, где индексы $i_1 < i_2 < \ldots < i_k$. Мы говорим, что подпоследовательность возрастающая, если $a(i_1) \leq a(i_2) \leq \ldots \leq a(i_k)$.

ФД может переупорядочивать коров следующим образом выбрать любую подпоследжовательность и реверсировать её элементы

Например, если мы имееем список

1 6 2 3 4 3 5 3 4

мы можем реверсировать следующие элементы

1 6 2 3 4 3 5 3 4
  ^         ^ ^ ^

получим

1 4 2 3 4 3 3 5 6
  ^         ^ ^ ^

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

Определите максимально возможную длину возрастающей подпоследовательности основываясь на факте, что Вы можете реверсировать любую подпоследовательность, но только один раз.

Формат входных данных:

Первая строка ввода содержит числа $N$. Остальные $N$ строк содержат $a(1) \ldots a(N)$, целые числа в интервале $1 \ldots 50$.

ФОРМАТ ВЫВОДА (файл subrev.out):

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

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

—Войти и решать

Hoof, Paper, Scissors#90395

Возможно Вы слышали об игре "Камень, Бумага, Ножницы". Коровы любят играть в похожую игру "Копыто, Бумага, Ножницы" Правила игры "Копыто, Бумага, Ножницы" просты. Две коровы играют друг против друга. Они обе считают до трёх, а затем одновременно делают жест, представляющий копыто, бумагу или ножницы. Копыто выигрывает у ножниц, ножницы выигрывают у бумаги, бумага выигрывает у копыта. Конечно может быть и ничья, если обе коровы сделали один и тот же жест.

Фермер Джон хочет сыграть с Бесси $N$ раз ($1 \leq N \leq 100,000$). Бесси будучи экспертом в этой игре может предсказать каждый из жестов ФД. Но как корова, она очень ленива. Поэтому она хочет играть одним и тем же жестом много раз подряд. В действительности, она хочет переключаться между жестами не более чем $K$ ($0 \leq K \leq 20$) раз за все игры. Например, если $K=2$, она может играть "копыто" первые игры, затем переключиться на бумагу и в конце играть снова "копыто".

По последовательности жестов, которую сыграет ФД, определите максимальное количество игр, которые может выиграть Бесси.

ФОРМАТ ВВОДА (файл hps.in):

Первая строка ввода содержит числа $N$ м $K$.

Оставшиеся $N$ строк содержат жесты ФД, каждый H, P или S.

ФОРМАТ ВЫВОДА (файл hps.out):

Выведите максимальное количество игр, которые может выиграть Бесси, если она может переключаться не более чем $K$ раз.

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

—Войти и решать

Radio Contact#90383

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

Фермер Джон начинает в позиции ($f_x, f_y$) и планирует сделать $N$ шагов, каждый из которых в одном из 4 направлений: 'N' (север), 'E' (восток), 'S'(юг), 'W' запад. Беси начинает в позиции ($b_x, b_y$) и делает аналогичные $M$ шагов. Эти пути могут иметь общие точки. В каждый момент времени ФД может остаться в своей текущей позиции либо сделать один шаг вперёд по своему маршруту (если ещё не достиг финальной позиции). В каждый момент времени (исключая тот момент, когда они находятся в стартовой позиции), энергия, потреблённая их радиоустройствами равна квадрату расстояния между ними.

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

ФОРМАТ ВВОДА (файл radio.in):

Первая строка ввода содержит $N$ и $M$ ($1 \leq N, M \leq 1000$). Вторая строка содержит целые числа $f_x$ и $f_y$, третья строка содержит $b_x$ и $b_y$ ($0 \leq f_x, f_y, b_x, b_y \leq 1000$). Следующая строка содержит строку длины $N$, описывающая путь ФД, и последняя строка содержит строку длины $M$, описывающая путь Беси.

Гарантируется, что координаты ФД и Беси всегда в интервале ($0 \leq x,y \leq 1000$) на протяжении всего маршрута. Заметим, что Восток - это положительное направление по оси Х, а Север - положительное направление по оси Y.

ФОРМАТ ВЫВОДА (файл radio.out):

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

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

—Войти и решать

Team Building#90364

Каждый год, Фермер Джон привозит $N$ своих коров соревноваться на ярмарку. Его главный соперник Фермер Пауль привозит своих $M$ коров ($1 \leq N \leq 1000, 1 \leq M \leq 1000$).

Каждая из этих $N + M$ коров получает индивидуальную оценку. Однако в текущем году финальное соревнование будет ограничено командой из $K$ коров ($1 \leq K \leq 10$). Поэтому ФД и ФП отбирают по $K$ коров. Затем они разбиваются на пары: лучшая корова ФД становится в пару с лучшей коровой ФП, вторая корова ФД, становится в пару со второй коровой ФП и т.д. ФД выиграет, если в каждой из этих пар его корова будет иметь более высокую оценку.

Помогите ФД посчитать количество различных способов которыми ФД и ФП могут отобрать своих коров так, чтобы ФД выиграл в соревновании. Точнее, каждая считается каждая различная пара ($K$ коров от ФД, и $K$ коров от ФП). Выведите ответ по модулю 1,000,000,009.

ФОРМАТ ВВОДА (файл team.in):

Первая строка ввода содержит $N$, $M$, $K$. Значение $K$ будет не более чем $N$ и $M$.

Следующая строка содержит оценки $N$ коров ФД.

Следующая строка содержит оценки $M$ коров ФП.

ФОРМАТ ВЫВОДА (файл team.out):

Выведите количеаство способов, которыми ФД и ФП могут отобрать свои команды, чтобы победил ФД. Выводите это число по модулю 1,000,000,009.

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

—Войти и решать

Cow Checklist#90359

Каждый день Фермер Джон прогуливается по своему пастбищу проверить состояние всех своих коров. У него на ферме есть коровы двух пород: Holsteins и Guernseys. $H$ коров породы Holsteins последовательно пронумерованы $1 \ldots H$, и $G$ Guernseys последовательно пронумерованы $1 \ldots G$ ($1 \leq H \leq 1000, 1 \leq G \leq 1000$). Каждая из его коров расположена в точке на плоскости (точки не обязательно различны).

ФД начинает свою прогулку в позиции Holstein 1 а заканчивает в позиции Holstein $H$. Он хочет посетить каждую корову и для удобства ведёт чек-лист посещения коров. Он хочет посещать Holsteins и Guernseys в порядке их нумерации. В последовательности всех $H+G$ коров, в порядке их посещения, коровы породы Holsteins $1 \ldots H$ появятся как подпоследовательности (не обязательно непрерывные), аналогично и с коровами породы Guernseys. Другими словами, последовательность всех $H+G$ коров будет сформирована перемешиванием списка Holsteins пронумерованных $1 \ldots H$ и списка Guernseys, пронумерованных $1 \ldots G$.

Когда ФД двигается от одной коровы к другой, преодолевая расстояние $D$, он тратит $D^2$ энергии. Помогите ему определить, минимальное количество энергии, требуемое чтобы посетить всех его коров в соответствии с правилами, описанными выше.

ФОРМАТ ВВОДА (файл checklist.in):

Первая строка ввода содержит $H$ и $G$, разделённые одиночным пробелом.

Последующие $H$ строк содержат $x$ и $y$ координаты $H$ Holsteins, и следующие $G$ строк содержат координаты Guernseys. Каждая координата это целое число в интервале $0 \ldots 1000$.

ФОРМАТ ВЫВОДА (файл checklist.out):

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

Динамическое программирование на таблицах

—Войти и решать