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

Путь в никуда#24761

Колобку снится странный сон.
В нём Колобок находится на клетчатом поле размера n × m в клетке с координатами (x, y).
Изначально Колобок смотрит вдоль положительного направления оси X. Затем он начинает идти по полю со следующей закономерностью:
• Пройти на одну клетку вперед. Повернуть на 90^oвправо.
• Пройти на одну клетку вперед. Повернуть на 90^o вправо.
• Пройти на две клетки вперед. Повернуть на 90^o вправо.
• Пройти на две клетки вперед. Повернуть на 90^o вправо.
• Пройти на три клетки вперед. Повернуть на 90^o вправо.
• Пройти на три клетки вперед. Повернуть на 90^o вправо.
• Пройти на четыре клетки вперед. Повернуть на 90^o вправо.
• И так далее...

Движение продолжается до тех пор, пока Колобок не выйдет за границы поля. После этого Колобок просыпается.

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

Формат входного файла
В первой строке входного файла находятся два натуральных числа n, m (1 ≤ n, m ≤ 10⁹ ) — размеры доски вдоль оси X и оси Y соответственно. Во второй строке находятся два натуральных числа x, y (1 ≤ x ≤ n; 1 ≤ y ≤ m) — координаты стартовой позиции колобка.

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

Вывод	Ввод
7 6 3 4	36
2 2 1 1	2
2 2 1 2	4

Комментарий
На рисунке наглядно показан первый пример.

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

Тяжелая, вариант-1#24736

В школьную столовую пришли n учеников разных классов и выпили суммарно k стаканов компота. Кассирша тетя Таня хорошо знает всех учеников, поэтому про i-го пришедшего школьника она знает число a_i — минимальное количество стаканов компота, которое мог выпить этот школьник. Также она знает, i-й школьник выпьет явно не больше a_i+x стаканов компота. Теперь ей стало интересно: а какое максимальное количество стаканов компота гарантированно выпил один из школьников? То есть она хочет найти такое максимальное число m, что при любом корректном распределении количества выпитых стаканов компота между школьниками, школьник, выпивший максимальное количество стаканов компота, выпил их не менее чем m штук. Помогите ей с этой задачей.

Формат входного файла

В первой строке входного файла input.txt находятся три натуральных числа n, k, x (1 ≤ n ≤ 100; 1 ≤ k ≤ 2 · 10⁴; 1 ≤ x ≤ 100) — количество школьников, пришедших в столовую, количество стаканов компота, выпитого ими, и максимальное количество стаканов, которое каждый школьник мог выпить сверх своего минимального количества, соответственно.
В следующей строке находятся n целых чисел a_i (1 ≤ a_i ≤ 100), разделенных пробелами, — минимальное количество стаканов компота, которое выпил i-й школьник.
Гарантируется, что входные данные корректны.

Формат выходного файла

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

Пример входных и выходных данных

Ввод	Вывод	Комментарий
3 4 1 1 1 2	2	Так как всего было выпито 4 стакана компота, а школьники выпили хотя бы 1, 1 и 2 стакана соответственно, первый школьник выпил ровно 1 стакан, второй — ровно 1 стакан, третий — ровно 2 стакана. Следовательно, ответ равен 2.
3 6 1 1 1 2	2	Каждый из школьников мог выпить по 2 стакана компота. Значит, ответ 3 гарантировать нельзя. Следовательно, ответ равен 2.
3 7 1 1 1 2	3	Так как всего выпито 7 стаканов компота, хотя бы один школьник выпил 3 стакана. Ответ 4, очевидно, недостижим. Следовательно, ответ равен 3.
3 12 2 1 2 4	5	Первый школьник выпил хотя бы 1 стакан и не более 3, второй — хотя бы 2 и не более 4, третий — хотя бы 4 и не более 6. Невозможно выпить 12 стаканов компота, если третий школьник выпьет ≤ 4 стакана, следовательно, ответ равен 5.

Жадный алгоритм Задачи на моделирование

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

Orders#24733

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

Входные данные
В первой строке на вход подается числа n и m - количество приказов, которые отдал Блейз, и количество команд, которые понимают его войска соответственно. (1 <= n, m <= 5000)
В следующей строке на вход подаются m слов - команды, которые понимают войска Блейза.
В следующих n строках на вход подаются слова - приказы, которые отдает Блейз.
Все строки длиной не превышают 100.

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

Выведите n строк: в строке номер i содержится ответ на задачу для приказа Блейза номер i. Строки, являющиеся ответом на этот запрос, выводятся через пробел в одну строку.

Пример
Ввод

5 5
is in if on of
it
in
of
ij
op

Вывод
if in is
if in is on
if of on
if in is
of on

(с) Евгений Григорьев

Бор Обход в глубину Перебор

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

Cipher#24728

Корвину удалось перехватить n сообщений о перемещении войск Эрика. Правда, они оказались зашифрованными, но это не беда! Вы ведь поможете ему расшифровать эти сообщения? Это должно быть не сложно, ибо Корвин знает хотя бы одну подстроку в каждом исходном сообщении.

Известно, что для шифровки Эрик использует шифр Цезаря, то есть шифр, в котором буква с номером i заменяется на букву с номером i + k, где k - некоторое число.

Так как современные компиляторы не поддерживают амберский алфавит, мы будем заменять символы на их порядковый номер - число от 1 до q, где q - количество символов в алфавите.

Каждое сообщение имеет длину x, а каждая известная подстрока его расшифровки - y.

Ваша цель - восстановить все изначальные сообщения.

СДАВШИЙ С ПОМОЩЬЮ STD::STRING ОТПРАВИТСЯ ВО ДВОРЫ ХАОСА!!!

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

В первой строке считываются числа n (\(1 <= n <= 100\)) и q (\(1 <= k <= 100\))

В следующих 3 * n строках содержатся числа x_i, y_i (\(1 <= b_i <= a_i <= 100\)) и 2 массива с числами, являющиеся сообщением и его подстрокой его расшифровки.

Выходные данные
В строке номер i выведите расшифрованный вариант сообщения с номером i.
В конце этой строки пробела быть НЕ ДОЛЖНО

Примеры

№	Входные данные	Выходные данные
1	1 11 10 4 11 7 1 1 2 6 7 1 1 8 2 7 7 8	6 2 7 7 8 1 2 7 7 3

Z-функция. Префикс-функция Поиск подстроки в строке реализация

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

Восстановление скобок#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средняяВойти и решать

Сенсор#23362

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

Сенсор выдает число s равное суммарному числу точек на нижних гранях игральных костей.

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

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

В первой строке входного файла задано число s сумма на нижних гранях костей (s <= 10⁵).

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

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

Ввод	Вывод
2	2
4	4

Пояснение к примеру

В первом примере на нижних гранях могло выпасть 1 + 1 или 2, суммы на верхних гранях 12 и

5, соответственно.

Комбинаторика Перебор

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

Кладовка из Простоквашино#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средняяВойти и решать

Раскраска отрезков#21847

У Джона Доу есть n отрезков на прямой. Отрезок (a, b) (a < b) — это множество точек x, таких, что a < x < b. Говорят, что отрезки (a1, b1) и (a2, b2) пересекаются, если существует такая точка c, что a1 < c < b1 и a2 < c < b2.

Джон хочет покрасить каждый отрезок в чёрный или белый цвет так, чтобы никакие два отрезка одного цвета не пересекались. Он хочет узнать, сколько существует различных способов покрасить отрезки таким образом.

Две покраски считаются различными, если существует отрезок, который в одной покраске покрашен в белый цвет, а в другой — в чёрный.

Пусть количество способов покрасить отрезки равно x. Выведите остаток от деления x на 10⁶ + 3.

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

В первой строке записано целое число n (1 ≤ n ≤ 10⁵) — количество отрезков у Джона. В следующих n строках находится описание отрезков. В i-й из них записано два числа li и ri (0 ≤ li < ri ≤ 10⁹) — координаты концов i-го отрезка.

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

Выведите остаток от деления x (количество способов покрасить отрезки) на 10⁶ + 3.

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

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

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

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

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

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

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

Примечание

Тесты поделены на группы, но оцениваются отдельно.

n ≤ 3 — 10 баллов
n ≤ 15 — 30 баллов
n ≤ 100 — 20 баллов
ai ≤ 10⁶ — 20 баллов
Без дополнительных ограничений — 20 баллов

Использование сортировки Сканирующая прямая

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

Мерлин#21817

Однажды, вернувшись в свою башню, Мерлин обнаружил, что Моргана наложила проклятие на

все его сосуды с эликсиром мудрости.

Мерлин знает, как снять проклятие, но соответствующее заклинание требует, чтобы во всех

сосудах, к которым оно применяется, было равное количество эликсира.

Чтобы добиться этого, Мерлин решил действовать следующим образом. Он выбирает несколько

сосудов и переливает весь эликсир из выбранных сосудов в оставшиеся. Он может распределить

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

эликсир из выбранных сосудов перелит, Мерлин разбивает опустошенные сосуды (с них проклятие

уже не снять), выбрасывает осколки и применяет заклинание снятия проклятия к оставшимся

сосудам.

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

чтобы снять проклятие Морганы.

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

В первой строке входного файла находится число n (2 ≤ n ≤ 10⁵) — количество сосудов. Во

второй строке содержатся n чисел a₁, a₂, . . . , a_n (1 ≤ a_i ≤ 10⁹) — количество литров эликсира

мудрости в каждом сосуде.

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

Выведите в выходной файл минимальное количество сосудов, которые Мерлину придется

разбить.

Пример
Ввод

2 3 2
Вывод
1

Ввод:

4 4 4 4
Вывод
0

Ввод

1 2 3 4 5
Вывод
2

В первом примере можно, например, перелить 0.5 литра эликсира из первого сосуда во второй

и 1.5 литра в третий, после чего разбить первый сосуд.

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

В третьем примере можно, например, перелить 1 литр эликсира из первого сосуда во второй, по

2 литра из пятого во второй и третий, 1 литр из пятого в четвертый, после чего разбить первый и

пятый сосуды.

Использование сортировки Отрезки реализация

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

Миссия Пиксель. 9. Отчёт командира#91327

🎯

Шаг 9: Отчёт командира

Средне

Финальная задача перед решающей атакой! Нужно составить рейтинг серверных зон по суммарному урону. Данные разбросаны — одна зона может встречаться несколько раз. Сгруппируй и отсортируй!

Условие задачи

Дано N строк. В каждой — название зоны и число (урон), через пробел. Одна зона может встречаться несколько раз.

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

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

В первой строке — число N. В каждой из следующих N строк — название зоны и целое число через пробел.

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

На каждой строке: название и суммарный урон через пробел (по убыванию урона).

Использование сортировки

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

Приключение на 20 минут#91234

Недавно руководители Отеля поняли, что гостей становится все больше и нужно расширять штат. С чего бы начать? Первым на работу взяли нового Портье.

Но вот незадача, Портье ещё не успел освоиться на новом месте, как уже начались проблемы. Недовольные постояльцы вызвали его к себе в номер на шестом этаже, однако, по неопытности он заблудился и зашел в комнату \(404\)!!! А там…Лабиринт.

Лабиринт представляет собой последовательность из \(n\) дверей, расположенных друг за другом на одном этаже. Каждая \(i\)-я дверь покрашена в какой-то цвет \(a_i\), причём на этаже ровно по две двери каждого из цветов.

Допустим, что \(i\)-я и \(j\)-я двери покрашены в один и тот же цвет, причём \(i < j\). В таком случае, если Портье зайдёт в \(i\)-ю дверь, то он окажется между \(j\)-й и \((j+1)\) -й дверьми и сможет дальше зайти в одну из них. Если же он зайдёт в \(j\)-ю дверь, то он окажется между \((i-1)\) -й и \(i\)-й дверьми и далее сможет зайти в одну из них. Если \(i = 1\), то войдя в \(j\)-ю дверь, Портье окажется левее первой двери и далее сможет зайти только в неё же, а если \(j = n\), то войдя в \(i\)-ю дверь, он окажется правее последней двери и выберется из лабиринта.

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

Формат входных данных
В первой строке находится чётное число \(n\) \((2 \le n \le 200\,000)\) — количество дверей в лабиринте.

Вторая строка содержит \(n\) целых чисел \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le n\)), где \(a_i\) — цвет \(i\)-й двери в последовательности. Гарантируется, что в лабиринте ровно по две двери каждого из цветов.

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

Ниже на картинке изображено пояснение к первому примеру из условия.

Задачи на моделирование

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

Конвейерный отель#91233

Вы с друзьями уже давно заехали в отель, но только сейчас выяснилось, что в отеле существуют так называемые <<Тихие часы>>. Во время этих часов все должны находиться в своих комнатах, и обойти это ограничение нельзя, потому ключи от комнат на время <<Тихих часов>> забирает персонал отеля. К счастью, вам повезло и вы с друзьями живёте на одном этаже, в последовательных комнатах с номерами от \(1\) до \(n\). Расстояние между соседними комнатами равно 5 метрам.

Вы пришли к достаточно изящной идее, которая поможет справиться со столь сложной ситуацией. За одну ночь под всеми комнатами вы проложили конвейер из \(3n\) ячеек, позволяющий перевозить посылки. Соседние ячейки, так же, как и комнаты, находятся на расстоянии 5 метров друг от друга. Ячейки конвейера с номерами от \(n + 1\) до \(2n\) находятся под комнатами друзей, ячейки с номерами от \(1\) до \(n\) – левее комнаты номер \(1\), а ячейки с номерами от \(2n + 1\) до \(3n\) – правее комнаты с номером \(n\).

В один из таких <<Тихих часов>> каждый друг отправил посылку одному другому другу. Для того, чтобы перемещать посылки, есть две кнопки: <<ВПРАВО>> и <<ВЛЕВО>>, сдвигающие конвейер на 5 метров вправо и влево соответственно.

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

Первая строка входных данных содержит одно целое число \(n\) (\(2 \le n \le 100\,000\)) — число друзей, обменивающихся посылками.

Вторая строка содержит \(n\) целых чисел \(a_i\) (\(1 \le a_i \le n, a_i \ne i\)) — номер друга, которому адресована посылка \(i\)-го из друзей.

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

Разберём пример из условия. Сначала можно 1 раз нажать кнопку <<ВПРАВО>>, после этого второй друг получит посылку от первого, а третий — от второго. После этого необходимо 2 раза нажать на кнопку <<ВЛЕВО>>, тогда второй друг получит посылку от третьего. И наконец, нужно ещё 2 раза нажать кнопку <<ВЛЕВО>>, после чего первый друг получит посылку от четвёртого. Итого потребуется 5 нажатий.

Задачи на моделирование

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

Демонтаж#91229

Отель представляет собой последовательность из \(n\) зданий различной высоты, построенных вплотную друг к другу. Не так давно в Отель провели кабельное телевидение, которым все теперь с удовольствием пользуются. Но есть одна проблема: на крыше \(m\)-го здания осталась куча оборудования от спутникового телевидения, которое надо с неё спустить, и вам поручили это сделать.

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

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

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

Формат входных данных
На первой строке вводится два целых числа \(n, m\) \((1 \le m \le n \le 100\,000)\) — число зданий и номер здания, на котором находится оборудование, соответственно.

Вторая строка содержит \(n\) целых чисел \(h_1, h_2, \dots, h_n\) \((1 \le h_i \le 10^9)\) — высоты зданий.

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

В данном примере вам достаточно лестницы длины \(1\), так как вы можете подняться с её помощью на крышу пятого здания, далее добраться по лестницам между крышами на третью крышу, взять оборудование, после чего сначала спуститься по лестнице между третьей и четвертой, а затем — четвертой и пятой крышами. После этого можно спуститься с крыши пятого здания.

Задачи на моделирование

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

Зелье от морской болезни#91198

Шкипер Баг ужасно страдает от морской болезни. Единственное спасение — зелье «Штиль», которое продаётся в лавках на островах архипелага. На n островах цены разные: в i-м порту бутылка стоит xi дублонов.

Каждый раз, когда «Нулевой указатель» заходит в порт, у Шкипера Бага с собой разная сумма — зависит от того, не украл ли корабельный кот монеты из кармана. Всего таких заходов будет q. Для каждого захода Шкипер Баг хочет заранее знать: в скольких портах архипелага он смог бы купить зелье, имея столько дублонов?

Формат входных данных
Первая строка: n (1≤n≤100 000) — количество портов.
Вторая строка: n чисел xi (1≤xi≤100 000) — цены на зелье.
Третья строка: q (1≤q≤100 000) — количество заходов в порт.
Следующие q строк: число mi (1≤mi≤10⁹) — дублоны Шкипера Бага при i-м заходе.

Формат выходных данных
q чисел — для каждого захода количество портов, где хватит денег.

Примечание:
При 1 дублоне ни одна лавка недоступна. При 8 — можно купить в 4 лавках (цены 2, 3, 4, 7). При 3 — только одна лавка (цена 2). При 100 дублонах — все пять.

*1100 Бинарный поиск дп реализация

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

Путь в лабиринте#89120

Дан лабиринт в виде прямоугольной таблицы N×M. Символ '.' — проход, символ '#' — стена. Найдите количество различных путей из левого верхнего угла (0,0) в правый нижний угол (N-1, M-1).
Двигаться можно только вправо или вниз. Проходить через одну клетку дважды нельзя.

Формат входных данных
Первая строка: два числа N и M — размеры лабиринта (2 ≤ N, M ≤ 5)
Следующие N строк: лабиринт (символы '.' и '#')

Формат выходных данных
Одно число — количество различных путей.
Если путей нет, вывести 0.

Примечание

В тестовом примере существуют два пути
Путь 1: (0,0)→(1,0)→(2,0)→(2,1)→(2,2)
Путь 2: (0,0)→(0,1)→(0,2)→(1,2)→(2,2)

ПОДСКАЗКА:
1. Отмечай посещённые клетки, чтобы не ходить по кругу
2. При откате снимай отметку о посещении
3. Проверяй границы лабиринта и стены

Рекурсивный перебор

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

Ледяная горка#81116

В Простоквашино построили ледяную горку. Она состоит из N ступенек. На каждой ступеньке написано число — сколько секунд нужно отдохнуть, если встать на неё. Дядя Фёдор стартует перед первой ступенькой и может прыгать на 1 или 2 ступеньки вперёд. Ему нужно добраться до вершины (встать на последнюю ступеньку), потратив минимум времени на отдых.

Входные данные: В первой строке число N (1 ≤ N ≤ 10). Во второй строке N целых чисел от 0 до 100 — время отдыха на каждой ступеньке.

Выходные данные: Минимальное суммарное время отдыха.

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

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

Ленивый поиск#67762

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

Формат входных данных
На вход подается одна строка. Строка содержит печатаемые ASCII-символы. В строке обязательно есть хотя бы одна подпоследовательность начинающаяся с < и заканчивающаяся >.

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

Пример
Входные данные
<br><hr><img/>

Выходные данные
<br> <hr> <img/>

Конечные автоматы

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

Email адреса#67760

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

В заданном тексте, состоящем не более чем из 100 строк, найдите все email адреса. Выведите эти адреса в столбик в порядке их встречаемости в тексте.

Формат email адреса (немного упростим, для облегчения реализации):

Локальная часть (до @): буквы (английские большие и маленькие), цифры, точки, дефисы, подчеркивания
Доменная часть (после @): буквы, цифры, точки, дефисы. Доменная часть должна содержать как минимум одну точку. Недопускается две и более точек подряд. Существование доменной части не проверяется.
Обязательно содержит символ @
Обычно заканчивается доменом верхнего уровня (например, .com, .ru, .org и др), состоящим от 2-х до 4-х символов (существование домена верхнего уровня не проверяется).

Примечание:

Регистр не имеет значения
Адреса могут быть в любом месте текста
Нужно найти все вхождения, даже повторяющиеся
Валидность адреса проверяется только по формату (может не существовать реально).

Формат входных данных
В первой строке записано натуральное число N - количество строке текста. Далее, идут сами строки текста.

Формат выходных данных
Выведите все искомые email адреса, каждый адрес в отдельной строке.

Конечные автоматы

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

Все слова на p#67723

Словом называется последовательность символов ограниченная слева и справа пробелом или началом(концом) строки. Найдите все слова, начинающиеся на английскую букву p (без учета регистра).

Формат входных данных
Строка, состоящая из букв английского алфавита. Длина строки не более 1000 символов.

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

Задача на реализацию Конечные автоматы Строки

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