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

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

Торги проходят в течении \(n\) дней, всего на рынке представлены акции \(m\) компаний, цены акций компании фиксированы в течении одного дня. Сделки бывают двух типов:

Купить \(x\) акций компании \(comp\)
Продать все акции компании \(comp\)

За каждую сделку надо заплатить 1% комиссии. Например, если купить 10 акций по 300 рублей, то суммарно заплатить придется 3030 рублей. Если же продавать 10 акций стоимостью 300 рублей каждая, то за них можно получить 2970 рублей.

Прибылью с продажи будем считать разность полученных при продаже денег и суммарно потраченных денег при покупках. Например, если 10 акций были куплены по 300 рублей, а затем еще 5 акций были куплены по 400 рублей, то в случае продажи по стоимости 500 прибыль составит: \(15 \cdot 500 \cdot 0.99 - (10 \cdot 300 \cdot 1.01 + 5 \cdot 400 \cdot 1.01) = 7425 - (3030 + 2020) = 2375\) рублей. При этом, акции могут быть проданы в убыток (за меньшую стоимость, чем были куплены), тогда прибыль с продажи будем считать отрицательной.

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

Вам даны \(k\) событий покупки/продажи. Необходимо найти максимальную суммарную прибыль среди всех моментов времени.

Входные данные
В первой строке входных данных содержится одно целое число \(t\) — число тестовых наборов (\(1 \le t \le 30\)).

Затем следуют \(t\) тестовых наборов. Каждый тестовый набор описывается следующим образом:

В первой строке тестового набора содержатся три целых числа \(n\), \(m\) и \(k\) — число дней, в которые проходят торги, число компаний на рынке и число событий, соответственно (\(1 \le n, m \le 100\), \(1 \le k \le 1000\)).

В следующих \(m\) строках записаны названия компаний и \(n\) чисел — стоимости акций компании в рублях в каждый из дней торгов. Названия компаний состоят из не более чем \(10\) строчных букв латинского алфавита и попарно различны. Стоимости акций — целые числа в диапазоне от \(1\) до \(10^5\) включительно.

В следующих \(k\) строках заданы события покупки/продажи в хронологическом порядке. Событие покупки задается в формате <день> buy <число акций> <название компании>, а событие продажи задается в формате <день> sell <название компании>. При этом <день> — целое число от \(1\) до \(n\), а <число акций> — целое число от \(1\) до \(1000\). Гарантируется, что все события следуют в порядке неубывания дней и корректны, а именно нет продаж некупленных акций и покупок акций, которых нет на рынке.

Выходные данные
Для каждого тестового набора выведите в отдельной строке максимальную прибыль среди всех моментов времени, с относительной или абсолютной погрешностью не более \(10^{-4}\).

Примечание

В первом тестовом наборе изначально до продаж суммарная прибыль равна \(0\), после первой продаже суммарная прибыль становится \(2375\) (случай разобран в примере).

Во втором тестовом наборе промежуточные прибыли равны \(0\), \(-11.11\) (акция продана дороже, но комиссия больше разницы) и \(1948.89\).

В третьем тестовом наборе промежуточные прибыли равны \(0\) и \(-2080\).

В четвертом тестовом наборе промежуточные прибыли равны \(0\) и \(979.9\), деньги потраченные на непроданные акции не учитываются.

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

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

Алёна и таблички#49296

На уроке информатики маленькая девочка Алёна осваивает редактирование таблиц в одной очень известной программе.

Сейчас у неё есть таблица из целых чисел, состоящая из \(n\) строк и \(m\) столбцов. Через \(a_{i,j}\) будем обозначать число в \(i\)-й строке и \(j\)-м столбце. Будем говорить, что таблица отсортирована по неубыванию по \(j\)-му столбцу, если \(a_{i, j} \leq a_{i + 1, j}\) для всех \(i\) от \(1\) до \(n - 1\).

Учительница дала Алёне \(k\) заданий. Для каждого из заданий известны два числа \(l\) и \(r\) и требуется ответить на вопрос: если от таблицы оставить только строки с \(l\) по \(r\) включительно, то будет ли она отсортирована по неубыванию хотя бы по одному столбцу? Другими словами, существует ли такое \(j\), что \(a_{i, j} \leq a_{i + 1, j}\) для всех \(i\) от \(l\) до \(r - 1\) включительно.

Алёна ещё слишком маленькая, чтобы справиться с заданием самостоятельно — помогите ей!

Формат входных данных
В первой строке входных данных записаны два целых положительных числа \(n\) и \(m\) (\(1 \leq n \cdot m \leq 100\,000\)) — количество строк и столбцов в таблице соответственно. Обратите внимание, что дано ограничение только на произведение этих чисел, то есть на количество элементов таблицы.

В каждой из следующих \(n\) строк записаны \(m\) целых чисел, \(j\)-e число в \(i\)-й из этих строк соответствует значению \(a_{i, j}\) (\(1 \leq a_{i, j} \leq 10^9\)).

В следующей строке входных данных задано число \(k\) (\(1 \leq k \leq 100\,000\)) — количество заданий учительницы, которые нужно выполнить Алёне.

В \(i\)-й из последующих \(k\) строк числа \(l_i\) и \(r_i\) (\(1 \leq l_i \leq r_i \leq n\)).

Формат выходных данных
В \(i\)-й строке выведите “Yes”, если в таблице, полученной из исходной оставлением строк с \(l_i\) по \(r_i\) включительно будет столбец, по которому она отсортирована по неубыванию, и “No” в противном случае.

Замечание

В приведенном примере таблица не отсортирована ни по одному столбцу, но, например, строки 1–3 отсортированы по столбцу 1, а строки 4–5 по столбцу 3. В данной задаче 100 тестов, помимо тестов из условия, каждый из них оценивается в 1 балл. Результаты работы ваших решений на первых 60 тестах будут доступны во время соревнования. Результаты работы на остальных 40 будут доступны после окончания соревнования.

Решения, корректно работающие при \(1 \leq n, k \leq 100\) и \(m = 1\), наберут не менее 10 баллов.

Решения, корректно работающие при \(1 \leq n, m, k \leq 100\), наберут не менее 40 баллов.

Задачи на моделирование Префиксные суммы(минимумы, ...)

✓ 1✗ 13—Войти и решать

Облако хештегов#49295

Вася ведёт публичную страницу организации “Мышь и клавиатура”, где постоянно публикует различные новости из мира спортивного программирования. Для удобства поиска по новостям Вася прикрепляет к каждой из них список хештегов. В данной задаче хештегом называется строка, состоящая из маленьких букв английского алфавита и ровно одного символа ‘#’, расположенного в начале строки. Длиной хештега будем называть количество символов в нём, без учёта символа ‘#’.

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

Поскольку вам не хочется менять порядок хештегов в уже написанной новости, вы решили удалить у некоторых хештегов некоторый суффикс (какое-то количество последних символов), при этом можно даже удалить весь текст хештега, оставив только символ ‘#’, но сам символ ‘#’ удалять нельзя. Из всех возможных вариантов такого удаления вы хотите выбрать тот, в котором суммарно будет удалено минимальное количество символов. Если и таких вариантов несколько, то разрешается использовать любой из них.

Формат входных данных
В первой строке находится одно число \(n\) (\(1 \leq n \leq 500\,000\)) — количество хештегов в новости.

Каждая из следующих \(n\) строк содержит ровно один хештег положительной длины.

Обозначим через \(L\) суммарную длину всех хештегов. Гарантируется, \(L\) не превосходит \(500\,000\).

Формат выходных данных
Выведите полученные после удаления символов хештеги.

Замечание

Слово \(a_1, a_2, \ldots, a_m\) длины \(m\) лексикографически меньше слова \(b_1, b_2, \ldots, b_k\) длины \(k\), если выполняется одно из двух:

либо в первой позиции \(i\), такой что \(a_i \neq b_i\), символ \(a_i\) идёт раньше по алфавиту, чем символ \(b_i\), то есть в первой различающейся позиции символ слова \(a\) меньше символа слова \(b\);
либо (если такой позиции нет) \(m < k\), то есть второе слово начинается с первого, но при этом не совпадает с ним.

Про последовательность слов говорят, что они идут в лексикографическом порядке, если каждое слово в нём (кроме последнего) лексикографически не превосходит следующее за ним.

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

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

В данной задаче 50 тестов, помимо тестов из условия, каждый из них оценивается в 2 балла. Результаты работы ваших решений на первых 35 тестах будут доступны во время соревнования. Результаты работы на остальных 15 будут доступны после окончания соревнования.

Решения, корректно работающие при \(1 \leq n, L \leq 15\), наберут не менее \(20\) баллов.

Решения, корректно работающие при \(1 \leq n, L \leq 1\,000\), наберут не менее \(50\) баллов.

Решения, корректно работающие при \(1 \leq n, L \leq 100\,000\), наберут не менее \(70\) баллов.

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

✓ 2✗ 4—Войти и решать

Устранение массива#49028

Дан массив \(a\) длины \(n\). Каждый элемент массива — \(0\), \(1\) или \(2\). Известно, что нули находятся только строго в левой половине массива, то есть на индесах от \(1\) до \(\left\lfloor\frac{n}{2}\right\rfloor\). Все оставшиеся элементы могут быть равны только \(1\) или \(2\).

С массивом разрешается выполнять следующие два вида действий:

Заплатить две монеты и удалить из массива любое число \(a_i\). После такого действия массив \([a_1, a_2, \ldots, a_k]\) превращается в \([a_1, \ldots, a_{i-1}, a_{i+1}, \ldots, a_k]\).
Заплатить одну монету и заменить два стоящих рядом числа \(a_i\) и \(a_{i+1}\) на \(a_i\) копий числа \(a_{i+1}\). То есть, возможны следующие преобразования:

Иными словами, \(0\) можно удалить вместе со следующим числом, \(1\) можно удалить саму по себе, если она стоит не в конце массива, а \(2\) можно заменить на следующее за ней число.

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

Формат входных данных
В первой строке дано единственное целое число \(T\) — количество наборов входных данных (\(1 \le T \le 100\)). Далее следуют \(T\) наборов входных данных.

Каждый набор входных данных начинается со строки, содержащей единственное число \(n\) — изначальную длину массива. В следующей строке через пробел перечислены целые числа \(a_1\), …, \(a_n\) — элементы массива (\(0 \le a_i \le 2\)).

Гарантируется, что сумма длин массивов по всем наборам входных данных не превосходит \(10^6\).

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

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

✓ 3✗ 0—Войти и решать

Рамка для рисунка#48041

У Алексея есть набор, который состоит из n палочек длины 1 и m палочек длины 2. Палочки можно соединять между собой, либо выстраивая их в линию, либо под прямым углом.

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

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

Формат входных данных
Первая строка входных данных содержит целое число n - количество палочек длины 1 (1 ≤ n ≤ 10⁹).
Вторая строка входных данных содержит целое число m - количество палочек длины 2 (1 ≤ n ≤ 10⁹).

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

Замечание
В первом примере есть 5 палочек длины 1. Из них можно сложить квадрат со стороной 1, его площадь равна 1, при этом одна палочка останется.
Во втором примере есть 4 палочки длины 1 и 3 палочки длины 2. Из них можно сложить прямоугольник размера 2 x 3.
В третьем примере есть 3 палочки длины 1, из них невозможно сложить прямоугольник.

Вывод формулы Задача на реализацию Задачи на моделирование

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

Исследование зеркальных цветов#44936

Члены экипажа космического корабля «Пегас» приземлились на третьей планете Системы Медуза, для изучения зеркальных цветов. Их корабль приземлился в начале узкого поля фермы, на которой выращивают цветы. Зеркальные цветы начинают прорастать после полуночи. Любезные работники фермы предоставили экипажу план прорастания цветов в виде точки и времени прорастания. Экипажу корабля необходимо улетать с планеты в следующую полночь. Исследовательская группа корабля может передвигаться по планете с максимальной скоростью v_max. На исследование одного цветка группе необходимо время d. Исследовать цветок необходимо сразу весь, нельзя будет к нему вернуться позже. Цветы прорастают тем позже, чем дальше они расположены от начала поля. В одной точке прорастает только один цветок, и каждый цветок прорастает в свой момент времени. Нет двух цветков, которые бы проросли одновременно.
Команда экипажа хочет определить момент времени, когда исследовательская группа сможет вернуться на корабль, исследовав все цветы и затратив на исследование как можно меньше времени.

Входные данные
Программа получает на вход несколько строк. Первая строка содержит 2 целых числа через один пробел: v_max (в см/мин) и d (в минутах), 0 < vmax <= 200, 0 <= d <= 500.
Вторая строка содержит одно число N – количество цветов (в штуках). 0 <= N <= 1400 при d = 0, в противном случае 0 <= N <= 200.
Далее идут N строк, в каждой из которых записано по два числа через пробел: целое число x_i – расстояние от цветка до начала поля (в сантиметрах), 0 <= x_i <= 32767, и число t_i – момент прорастания цветка (в формате hh:mm). Пары приведены в порядке возрастания расстояний.

Выходные данные
Выведите момент времени возвращения исследовательской группы на корабль (в формате hh:mm), округленный до целых минут в большую сторону.

Примечания
1. В часе - 60 минут, в сутках - 24 часа.
2. Время в сутках изменяется от 00:00 до 23:59.
3. Можно считать, что исследовательская группа не меняет направления движения до тех пор, пока не дойдет до последнего цветка.

Примеры

№	Входные данные	Выходные данные
1	3 1 1 100 00:01	01:08

Бинарный поиск по ответу Задачи на моделирование

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

Массив сумм#44508

Юля выписала на доску n последовательных натуральных чисел a, a+1, …, a+n−1 и написала под каждым из них сумму его цифр в десятичной записи, под i-м числом было выписано sum_i.

После этого Юра стёр исходные числа и оставил только их суммы цифр. От вас требуется восстановить первое число в исходной последовательности a.

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

В первой строке содержится одно целое число n (2 <= n <= 100000) - длина исходной последовательности.

В следующей строке содержатся n целых чисел sum₁, sum₂, …, sum_n (1 <= sum_i<= 90) - суммы цифр чисел исходной последовательности.

Гарантируется, что для всех тестов существует подходящее a, такое что 1 <= a <= 10¹⁸.

Выходные данные
Выведите одно число a (1 <= a <= 10¹⁸) - первое число исходной последовательности. В случае, если существует несколько подходящих a, можно вывести любое.

Примечание

В первом тестовом примере сумма цифр 1 равняется 1, сумма цифр 2 равняется 2, сумма цифр 3 равняется 3, что соотносится с массивом sum, поэтому a = 1 подходит под условие задачи.

Во втором тестовом примере сумма цифр 77 равняется 14, сумма цифр 78 равняется 15, сумма цифр 79 равняется 16, сумма цифр 80 равняется 8, сумма цифр 81 равняется 9, что соотносится с массивом sum, поэтому a = 77 подходит под условие задачи.

Примеры

№	Входные данные	Выходные данные
1	3 1 2 3	1
2	5 14 15 16 8 9	77

Вывод формулы Задачи на моделирование

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

Морской бой#44312

В старом игровом автомате «Морской бой» игрок сбивает торпедами корабли, двигающиеся по игровому полю слева направо или справа налево.
В нашем варианте игры на поле может находиться одновременно несколько кораблей. Все корабли движутся с одинаковыми скоростями налево или направо. За одну секунду каждый корабль передвигается на единицу длины системы координат. Это означает, что через одну секунду после начала игры корабль, который находился в точке 20 и двигался направо, будет находиться в точке 21, а корабль, который находился в точке 30 и двигался налево, окажется в точке 29.
Вы можете выпускать торпеды, которые будут подбивать корабли. Торпеда, выпущенная в точке с какой-то координатой, уничтожает корабль, находящийся в этот момент в этой точке. При этом если в этой точке в этот момент времени окажется несколько кораблей, то торпеда подобьёт все эти корабли. Вы даже можете одновременно выпускать несколько торпед!
Подбейте все корабли, используя минимальное число торпед.

Входные данные
В первой строке содержится целое число N — количество кораблей, движущихся влево (с уменьшением координаты). Во второй строке содержится целое число M — количество кораблей, движущихся вправо (с увеличением координаты). Гарантируется, что 1 ≤ N + M ≤ 10⁵, N > 0 и M > 0.
Следующие N строк содержат по одному целому числу l_i — начальные координаты кораблей,двигающихся влево. Следующие M строк содержат по одному целому числу ri — начальные координаты кораблей, двигающихся вправо. Координаты l_i идут в порядке возрастания, координаты ri также заданы в порядке возрастания. Гарантируется, что все начальные координаты l_i и r_i чётные, различные и не превосходят по модулю 10⁹.
Выходные данные
Программа должна вывести столько строк, сколько торпед необходимо для уничтожения всех кораблей, при этом i-я строка должна содержать два целых числа t_i — время нанесения удара i-й торпедой и x_i — координату удара i-й торпедой. Все t_i и xi должны быть целыми, 0 ≤ t_i ≤ 10¹⁸ , −10¹⁸ ≤ x_i ≤ 10¹⁸. В один момент времени можно выпускать несколько торпед, в одну точку можно выпускать несколько торпед в разные моменты времени.

Примеры

№	Входные данные	Выходные данные
1	2 1 10 30 20	0 10 5 25

Замечание
В примере из условия два корабля движутся влево и один корабль движется вправо. Начальные координаты кораблей, двигающихся влево, равны l₁ = 10 и l₂ = 30, а начальная координата корабля, двигающегося вправо, равна r₁ = 20. В момент времени t₁ = 5 в одной точке x₁ = 25 окажутся два корабля — двигающийся влево из точки 20 и двигающийся вправо из точки 30. Их можно подбить одной торпедой. Оставшийся корабль, двигающийся влево, можно подбить, например, в момент времени t₂ = 2 в точке x₂ = 8.

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

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

Самолёт#44309

В салоне самолёта в одном ряду находится n кресел. Для удобства прохода и обсуживания пассажиров вдоль салона делается один или два прохода. Например, в салоне самолёта Sukhoi Superjet 100 в ряду 5 кресел и один проход (с одной стороны прохода два кресла, с другой стороны — три), а в самых больших современных самолётах — 10 кресел и два прохода (по три кресла по бокам салона у иллюминаторов и четыре кресла между проходами).

Предположим, что в будущем появятся самолёты большего размера, поэтому количество проходов придётся увеличить. Определите, какое минимальное число проходов должно быть в самолёте, в одном ряду салона которого находится n кресел. По бокам салона (у иллюминаторов) может находиться не более 3 кресел, а между двумя проходами — не более 4 кресел. При этом в салоне должен
быть хотя бы один проход.
Входные данные
Программа получает на вход одно натуральное число n, не превосходящее 2 · 10⁹ , — количество кресел в одном ряду салона.
Выходные данные
Программа должна вывести единственное целое число — минимальное количество проходов, которое должно быть в салоне самолёта с n креслами в одном ряду.

Примеры

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

Вывод формулы Задачи на моделирование

✓ 62✗ 67500лёгкаяВойти и решать

Порадомой#43137

В один осенний день чебаркульская сборная по американскому футболу возвращалась на поезде домой после дружеского матча с командой Чебоксар. Подъезжая к очередной реке, главные тренеры футболистов — Алексей Юрьевич и Михаил Леонидович — заметили, что мост через реку на их пути не выглядит слишком надёжно, и, если несколько вагонов с суммарной массой больше W тонн будут целиком находиться на нём, переправа обязательно рухнет. Вагоны, которые находятся на мосту не полностью, не учитываются в суммарной массе.
Алексей Юрьевич, как самый ответственный тренер, точно знает, сколько весит каждый из вагонов поезда: i-й вагон от начала состава имеет массу ai тонн. Михаил Леонидович же имеет идеальное зрение, а потому может сказать, что длина моста равняется длине ровно p вагонов.
Крушения допустить никак нельзя, а потому тренеры приняли волевое решение: отцепить минимальное число вагонов (возможно, все) с конца состава, чтобы поезд смог проехать опасное место. Помогите им и скажите, сколько вагонов придётся оставить до переправы.
Входные данные
В первой строке входных данных через пробел записаны три целых числа n,p и W — количество вагонов в поезде, длина моста в вагонах и максимальная нагрузка в тоннах, которую он выдерживает (1 <= n <= 10⁵, 1 <= p <=10⁵, 0 <= W <=10¹⁴).
Во второй строке через пробел записаны n целых чисел a_i — веса вагонов в порядке их следования от начала состава (1 <= a_i <= 10⁹).
Выходные данные
Выведите единственное число — минимальное количество вагонов, которое надо отцепить от хвоста поезда, чтобы тот смог безопасно проехать по мосту.

Примеры

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

Замечание
В данном тесте мост обрушится, только если на него заедут 3 и 4 вагон одновременно, а это значит, что достаточно отцепить лишь последний вагон.

Задачи на моделирование Префиксные суммы(минимумы, ...)

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

Лес#42971

Миша заблудился в лесу и пытается выйти из него. Он проходит A шагов на север, затем B шагов на восток, затем C шагов на юг, D шагов на запад, после чего повторяет свои действия (снова A шагов на север, B шагов на восток, C шагов на юг, D шагов на запад и т.д.).
Оказалось, что для того, чтобы выйти из леса из его первоначальной точки, ему нужно было пройти ровно K шагов в любом из четырёх направлений, то есть первоначально Миша находится в центре квадрата со стороной 2K шагов. Определите, сколько шагов Миша сделает, прежде чем выйдет из леса (впервые окажется на границе леса).

Входные данные
Первые четыре строки входных данных содержат по одному целому положительному числу A, B, C, D — количество шагов, которое Миша делает на север, восток, юг, запад. Пятая строка входных данных содержит целое число K — расстояние от начального расположения Миши до четырёх сторон квадрата (границ леса). Все входные числа не превосходят 10⁹.

Выходные данные
Программа должна вывести одно целое число — количество шагов, которое Миша сделает до выхода из леса. Гарантируется, что входные данные таковы, что Миша когда-нибудь выйдет из леса.
Обратите внимание, что значение ответа может быть больше, чем возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C и C++, тип long в Java и C#).

Примеры

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

Замечание
На рисунке изображён пример из условия. Миша делает 1 шаг на север (вверх), 1 шаг на восток (вправо), 2 шага на юг (вниз), 3 шага на запад (влево). От начального расположения Миши до стороны квадрата — 3 шага. Первоначальное расположение Миши и точка выхода из леса обозначены синими кругами. Путь Миши обозначен жёлтой линией. Миша пройдёт 13 шагов, прежде чем впервые окажется на границе леса.

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

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

Программа для Громозеки#42243

Когда Громозека держит в руках сразу две печеньки с числами, он сразу пробует преобразовать большее число в меньшее. При преобразовании он использует только две команды: “Вычесть 1” и “Разделить на 2”, первая команда уменьшает число на 1, вторая команда уменьшает число в два раза, если оно чётное, иначе происходит ошибка. Громозека любит, чтобы преобразование происходило как можно быстрее. Помогите Громозеке составить последовательность команд, при которой из большего числа получится меньшее, причем за наименьшее количество команд.

Входные данные
Программа получает на вход два натуральных числа A и B (по одному числу в строке). A >= B.

Выходные данные
Выведите последовательность команд преобразования. Каждая команда должна выводиться в отдельной строке. Первая команда обозначается, как -1, вторая команда как :2.

Примеры

№	Входные данные	Выходные данные
1	`21 2`	`-1 :2 :2 -1 :2`

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

✓ 155✗ 344600лёгкаяВойти и решать

Три четыре пять корову поменять#39515

N коров (1 ≤ N ≤ 100) Фермера Джона выстроены в ряд. i-ая корова слева имеет метку i, для всех 1≤i≤N.
ФД приказал коровам повторить ровно K (1 ≤ K ≤10⁹) раз следующий двухшаговый процесс:

Последовательность коров в позициях A1…A2 слева реверсивно меняют свой порядок (1≤A₁<A₂≤N).
Затем последовательность коров в позициях B1…B2 слева реверсивно меняют свой порядок (1≤B₁<B₂≤N).
Выведите получившийся порядок коров для всех i 1 ≤ i ≤ N после выполнения этого процесса ровно K раз.

Входные данные
Первая строка содержит N и K. Вторая строка содержит A₁ и A₂, третья строка содержит B₁ и B₂.
Выходные данные
На i-ой строке выведите метку i-ой коровы слева после завершения процесса всех обменов.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	7 2 2 5 3 7	1 2 4 3 5 7 6	Изначально порядок коров слева направо такой [1,2,3,4,5,6,7] После первого шага процесса порядок станет таким [1,5,4,3,2,6,7] После второго шага процесса порядок станет таким [1,5,7,6,2,3,4]. Повторив оба шага ещё раз получим результат, приведенный в выводе.

Вывод формулы Задачи на моделирование

✓ 1✗ 13—Войти и решать

Отслеживание контактов#39388

Фермер Джон продолжает заботиться о здоровье своих коров, последовательно пронумерованных 1…N.
Недавно ФД проверил их всех и выяснил, что некоторые из них больны. Используя видео из амбара, ФД может узнать какие пары коров взаимодействовали распространяя при этом болезнь. ФД собрал список с указанием времени, в которое происходило взаимодействие пар коров в видео (t,x,y), означающем, что в момент времени t корова x взаимодействовала с коровой y. Также ФД знает следующее:

Ровно одна корова была инфицирована изначально (нулевой пациент).
После того, кaк корова инфицирована, она передаёт инфекцию её следующим K взаимодействиям (возможно включая одного и того же партнера несколько раз). После K раз передачи инфекций, она перестаёт передавать инфекцию (осознав что заражает, она начинает тщательно мыть копыта).
Однажды заболев, она остаётся больной.

К несчастью, ФД не знает, какая из его N коров, является "нулевым пациентом", кроме того он не знает значение K!. Помогите ему сузить диапазоны этих неизвестных, основываясь на его данных. Гарантируется, что ответ существует.

Входные данные
Первая строка ввода содержит N (2<= N <=100) и T (1 <= T <= 250). Следующая строка содержит строку длиной N, состоящую из 0 и 1, описывающую текущее состояние N коров ФД, 0 - здорова, 1 - больна. Каждая из последующих T строк описывает запись из списка взаимодействий ФД, и состоит из трёх чисел, t,x,y, где t - положительное целое время взаимодействия (t <= 250), x и y - различные целые в интервале 1…N, указывающее какие коровы взаимодействовали в момент времени T. В один момент времени T происходит не более одного взаимодействия.

Выходные данные
Выведите одну строку, содержащую три целых числа x,y,z, где x - количество различных коров, которые могли быть "нулевым пациентом", y - минимально возможное значение K, подходящее к исходным данным, z - наибольшее возможное значение K, подходящее к исходным данным. Если для K нет верхней границы, выведите "Infinity" для z. Заметим, что возможно K=0.

Примеры

№	Входные данные	Выходные данные
1	`4 3 1100 7 1 2 5 2 3 6 2 4`	`1 1 Infinity`

Задача на реализацию Задачи на моделирование Перебор

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

Гость из прошлого#39059

Коля Герасимов очень любит кефир, и в своём 1984 году он освоил все тонкости покупки этого чудесного напитка. Но однажды, как вам, наверное, известно, он попал в далёкий 2084 год, где покупка кефира представляет собой более сложный процесс.

Будущее будущим, а кушать хочется всегда, поэтому Коля отправился в местную молочную лавку. В 2084 году кефир продают в литровых пластиковых бутылках по a копеек за штуку и в литровых бутылках из стекла по b копеек за штуку. При этом пустую стеклянную бутылку можно сдать и получить назад c (c < b) копеек, а пластиковую бутылку сдать нельзя.

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

Входные данные
В первой строке входных данных задаётся число n (1 <= n <= 10¹⁸)— количество копеек у Коли в кармане.
В строках со второй по четвертую по одному записаны числа a, b и c (1 <= a <= 10¹⁸, 1 <= c < b <= 10¹⁸) - стоимость пластиковой бутылки с кефиром, стоимость стеклянной бутылки с кефиром и сколько копеек можно получить, сдав пустую стеклянную бутылку, соответственно.

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

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

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

Примеры

№	Входные данные	Выходные данные
1	10 11 9 8	2
2	10 5 6 1	2

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

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

Наша Таня громко плачет#39057

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

Сегодня рабочий день системного администратора Миши начался со звонка секретаря Тани, которая в очередной раз не справилась с редактированием документа. Миша моментально пришёл к Тане и узнал, что в результате ошибки в папке на ее компьютере оказалось n копий документа, над которым она сейчас работает. Других документов в папке нет. Таня просит Мишу удалить лишние копии, чтобы у неё осталась ровно одна копия нужного файла.

Таня работает в операционной системе Bububuntu, в которой есть две команды, позволяющие удалять файлы. Первая команда удаляет один произвольный файл с компьютера. На выполнение этой команды Миша тратит A секунд. Вторая команда рассчитана как раз на случай, подобный Таниному, и позволяет уменьшить количество копий файла в k раз. В силу технический особенностей Bububuntu эта команда работает, только если количество файлов в папке делится на k без остатка. На выполнение этой команды Миша тратит B секунд.

Для решения Таниной проблемы Миша решил по очереди использовать эти команды таким образом, чтобы в конце в папке остался ровно один документ.

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

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

В первой строке содержится целое число n ( 1 <= n <= 2*10⁹) - количество копий документа в папке у Тани.
Во второй строке содержится целое число k ( 1 <= k <= 2*10⁹) - количество раз, в которое уменьшает количество файлов вторая команда.
В третьей строке содержится целое число A ( 1 <= A <= 2*10⁹) - количество секунд, которое Миша тратит на выполнение первой команды.
В четвёртой строке содержится целое число B ( 1 <= B <= 2*10⁹) - количество секунд, которое Миша тратит на выполнение второй команды.

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

Выведите единственное число - минимальное количество секунд, которое придётся потратить Мише на решение проблемы.

Примечание

В первом тестовом примере оптимальная стратегия Миши такова:

За 3 секудны удалить один файл, в результате чего в папке останется 8 файлов. Обратите внимание, что Миша не мог использовать вторую команду, потому что 9 не делится на 2 .
За 1 секунду уменьшить число файлов в 2 раза. После этой операции в папке останется 4 файла.
За 1 секунду уменьшить число файлов в 2 раза. После этой операции в папке останется 2 файла.
За 1 секунду уменьшить число файлов в 2 раза. После этого в папке останется 1 файл и цель Миши будет выполнена.

На выполнение этих четырёх операций Миша потратит 6 секунд. Можно показать, что Миша не сможет удалить лишние файлы меньше, чем за 6 секунд.

Во втором тестовом примере Мише выгодно 4 раза удалить один файл. Так как на одно удаление Миша тратит 2 секунды, на выполнение всего задания Миша потратит 4·2 = 8 секунд. Кроме того, Миша мог бы удалить лишние файлы, один раз воспользовавшись второй командой, но, так как её выполнение занимает 20 секунд, Мише это не выгодно.

Примеры

№	Входные данные	Выходные данные
1	9 2 3 1	6
2	5 5 2 20	8
3	19 3 4 2	12

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

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

Экономическая грамотность#39056

Многие банки при оплате покупок их банковскими картами предлагают систему возврата части потраченных средств, называемую cashback .

Мама Алёны имеет три подобные карты с разными условиями возврата части потраченной суммы. На карту банка RR возвращается 5 рублей из каждых полных 100 рублей стоимости одной покупки. Например, 5 рублей возвращается и за покупку стоимостью 100 рублей, и 199 рублей. Банк BB возвращает 2 рубля с каждых 50 рублей покупки, и за покупку стоимостью 199 рублей он вернет уже 6 рублей. А банк ММ возвращает 3% с полной стоимости любой покупки (заметим, что при цене в целом числе рублей, 3% всегда будут составлять целое число копеек), поэтому за покупку в 199 рублей вернется 5 руб. 97 коп.

Алёна любит ходить вместе с мамой за покупками. Мама предложила Алёне определять, какую покупку какой картой оплачивать, чтобы сумма возврата была максимально возможной. Считайте, что оплата любой покупки возможна любой картой. Если какие-то две или все три карты дают лучшую сумму возврата с точностью до копеек, то Алёна выбирает ту из карт, которая ей больше нравится по оформлению. Больше всего Алёна любит карту банка MM, затем идёт карта банка BB, а меньше всего Алёне нравится карта банка RR.

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

Вводится одно целое число S ( 1 <= S <= 10 000 ) — стоимость покупки в рублях.

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

Выведите название банка RR , BB или MM в зависимости от того, картой какого банка выгоднее оплатить эту покупку. А при равенстве суммы возврата - название банка, определённого в условии задачи.

Примечание

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

Примеры

№	Входные данные	Выходные данные
1	10	MM
2	199	BB
3	101	RR

Задачи на моделирование Условный оператор

✓ 36✗ 153500лёгкаяВойти и решать

Спираль#38875

Робот перемещается по клетчатой плоскости и рисует спираль. Исходно он находится в клетке (0, 0) и направлен в сторону увеличения первой координаты.
Далее он действует по следующему алгоритму: совершает d перемещений вперед, затем поворачивает налево и снова делает d перемещений вперед. После этого он поворачивает налево и умножает значение d на k. Затем робот повторяет описанный процесс. Робот останавливается, сделав суммарно ровно n перемещений.
Требуется вывести картинку, на которой отмечены клетки, на которых побывал робот.

Входные данные
На вход подаются целые числа n, d и k (1 ≤ n ≤ 1000, 1 ≤ d ≤ 100, 2 ≤ k ≤ 5).

Выходные данные
Пусть минимальный прямоугольник из клеток, содержащий все посещенные роботом клетки, имеет высоту h и ширину w. На первой строке выведите числа h и w, разделенные пробелом. Следующие h строк должны содержать по w символов, выведите «*» для клетки, посещенной роботом и «.» для не посещенной.

Примеры

№	Входные данные	Выходные данные
1	13 2 2	5 5 ***** ... .** .... *...

Двумерные массивы Задачи на моделирование

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

Мегазорды#38866

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

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

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

Входные данные
В первой строке входного файла заданы числа g, r и b — количество зордов у зеленого, красного и синего рейнджера соответственно (1 ≤ g, r, b ≤ 10⁵).
В следующей строке находится g чисел x_i — номера моделей, которые есть у зеленого рейнджера (0 ≤ x_i ≤ 10⁹).
В следующей строке находится r чисел y_i — номера моделей, которые есть у красного рейнджера (0 ≤ y_i ≤ 10⁹).
В следующей строке находится b чисел z_i — номера моделей, которые есть у синего рейнджера (0 ≤ z_i ≤ 10⁹).

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

Примеры

№	Входные данные	Выходные данные
1	3 3 2 101 11 52 11 23 23 31 13	3

Замечание
Различные мегазорды из первого примера: 101 + 11 + 13, 52 + 23 + 31, 52 + 23 + 31. Последний мегазорд встречается дважды, так как красный ренжер мог взять либо второй, либо третий зорд. Обратите внимание, что собрать мегазорд 11+11+13 нельзя, так как при этом одна и та же модель будет использована дважны.

Вывод формулы Задачи на моделирование

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

Рейнджеры в автобусе#38865

Не каждый день могучие рейнджеры надевают свои костюмы. Сами посудите: как нелепо они бы смотрелись, скажем, в общественном транспорте, если бы не снимали их!
Это создаёт определённые трудности злодеям, которые хотят выследить их. Вот и сегодня Рита Репульса не может их поймать, потому что не знает, как они выглядят без костюмов.
Рита следит за автобусом, в котором, по её мнению, едет кто-то из рейнджеров. В салоне автобуса n рядов сидений, в каждом из которых по два места — слева и справа от прохода. Ряды пронумерованы от 1 до n, начиная с передней части автобуса. На конечной остановке в автобус по очереди зашли k человек, и Рита знает, кто на какое место сел и в каком порядке. Кроме того, ей известно, как каждый из рейнджеров выбирает себе место, когда заходит в автобус:

Красный рейнджер любит сидеть впереди. Поэтому среди свободных мест он всегда выбирает место в ряду с наименьшим номером. Если же в этом ряду свободно два места, он садится слева от прохода.
Синий рейнджер тоже любит сидеть впереди. Но, в отличие от красного, когда в ряду с наименьшим номером свободно два места, Синий садится справа.
Чёрный рейнджер любит сидеть сзади. Среди свободных мест он всегда выбирает место в ряду с наибольшим номером, а если там свободно два места, то садится слева от прохода.
Жёлтый рейнджер тоже, любит сидеть сзади. Но, в отличие от чёрного, когда в ряду с наибольшим номером свободно два места, жёлтый садится справа.
Розовый рейнджер не имеет никаких предпочтений и может сесть на любое свободное место.

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

Входные данные
В первой строке заданы числа n и k — количество рядов в автобусе и количество пассажиров (1 ≤ n ≤ 10⁹, 1 ≤ k ≤ min(2 · 10⁵, 2n)).
В следующих k строках описаны пассажиры в том порядке, в котором они заходили в автобус.
В i-й из этих строк заданы числа x_i и y_i — место, на которое сел i-й пассажир (1 ≤ x_i ≤ n, 1 ≤ y_i ≤ 2), x_i — это номер ряда, y_i = 1, если это место слева от прохода, и y_i = 2, если справа.
Все места, на которые сели пассажиры, различны.

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

Примеры

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

Замечание

На этой картинке показаны места, на которые садились пассажиры в примере.

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

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