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

Профессор Хаос#50571

В секретной лаборатории профессора Хаоса проходит эксперимент по выращиванию особо опасных бактерий. В начале первого дня эксперимента у Хаоса имеется \(a\) особо опасных бактерий.

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

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

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

Теперь профессор Хаос хочет выяснить, сколько особо опасных бактерий будет у него в контейнере после \(k\)-го дня эксперимента. Помогите ему найти ответ на этот вопрос.

Формат входных данных
В единственной строке входного файла содержится пять целых чисел \(a\), \(b\), \(c\), \(d\) и \(k\) (\(1 \le a, b \le 1000\), \(0 \le c \le 1000\), \(1 \le d \le 1000\), \(a \le d\), \(1 \le k \le 10^{18}\)).

Формат выходных данных
Выведите одно число — количество бактерий у Хаоса к концу \(k\)-го дня. Если эксперимент завершится в \(k\)-й день или ранее, выведите число 0.

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

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

Турнир ФХЛ#50446

Финальный турнир Флатландской Хоккейной Лиги (ФХЛ) играется между двумя командами-лидерами сезона. Команды играют матчи между собой до тех пор, пока одна из команд не выиграет ровно \(n\) матчей. Эта команда становится чемпионом ФХЛ. Каждый матч в финальном турнире заканчивается победой одной из команд, ничьих не бывает. Видеозаписи матчей публикуются на официальном сайте ФХЛ, так что все фанаты, которые пропустили матчи, могут посмотреть их в записи.

В этом году в финал вышли команды <<Капибары>> и <<Бурундучки>>. Петя и Вася очень любят хоккей, но во время турнира они были на сборах по информатике. Теперь они решили просмотреть все матчи финального турнира в записи, скачав их с официального сайта. Зайдя на сайт, они обнаружили, что в этом году финальный турнир ФХЛ состоял из \(k\) матчей. Скачав все видеозаписи, ребята начали их смотреть, но неожиданно поняли, что могут предсказать итог турнира, не досмотрев все матчи. Более того, они заметили, что про некоторые матчи они понимают, кто их выиграет, даже не начав смотреть запись.

Например, пусть \(n = 3\) и \(k = 4\). Петя и Вася сразу могут сделать вывод, что турнир закончится со счетом по матчам \(3:1\) или \(1:3\), ведь всего будет сыграно 4 игры. Пусть первый матч закончился победой команды <<Капибары>>, счет стал \(1:0\), второй матч также закончился победой команды <<Капибары>>, счет стал \(2:0\). Теперь ребята точно знают, что победителем турнира станет команда <<Капибары>>, ведь если бы турнир выиграла команда <<Бурундучки>>, то финальный счет был бы \(2:3\) и всего было бы сыграно 5 игр. Более того, команда <<Бурундучки>> гарантированно выиграет третий матч, иначе окончательный счет был бы \(3:0\), а команда <<Капибары>> "— четвертый матч.

По заданным \(n\), \(k\) и результатам игр определите, после какой игры Петя и Вася поймут, какая команда станет победителем турнира, а также про каждый матч определите, знают ли ребята победителя этого матча до того, как посмотрят его.

Формат входных данных
Первая строка ввода содержит два целых числа: \(n\) и \(k\) (\(1 \le n \le 100\), \(n \le k \le 2n-1\)). Вторая строка ввода содержит \(k\) целых чисел: \(i\)-е из них равно 1, если \(i\)-й матч выиграла команда <<Капибары>>, либо 2, если \(i\)-й матч выиграла команда <<Бурундучки>>.

Гарантируется, что по итогам турнира одна из команд выиграла ровно \(n\) матчей, причем ни одна из команд не выигрывает \(n\) матчей до того, как будут сыграны все \(k\) матчей, описанных во входных данных.

Формат выходных данных
Выведите две строки. Первая строка должна содержать одно число \(z\) (\(1 \le z \le k\)) "— номер матча, после которого ребята могут однозначно определить победителя турнира.

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

Задачи на моделирование Разбор случаев

✓ 5✗ 8—Войти и решать

Необычный массив#50409

У Васи есть массив, состоящий из \(n\) чисел \(a_1, a_2, \ldots, a_n\). Для каждой позиции \(i\) и для каждого подотрезка массива \([l, r]\), который содержит позицию \(i\) (то есть, \(1 \le l \le i \le r \le n\)), Вася вычисляет значение \(c_{i, l, r}\) следующим образом. Вася выписывает на листочек числа из массива с позиции \(l\) до позицию \(r\), всего \(len=r-l+1\) чисел (среди которых обязательно есть \(a_i\)), и сортирует выписанные числа по возрастанию. После чего Вася находит, на какой позиции \(j\) в полученном отсортированном массиве стоит число \(a_i\). Если таких позиций несколько, то среди них он выбирает ту, которая максимизирует расстояние от середины массива — позиции \(mid = \lceil (len+1) / 2 \rceil\) (\(len / 2 + 1\) в случае четного \(len\) и \((len+1)/2\) в случае нечетного \(len\)). Полученное расстояние \(|j - mid|\) и есть искомая величина \(c_{i,l,r}\).

Например, если у Васи был массив \(a=\{5,1,3,2,1,7\}\), а \(i=2\), \(l=2\), \(r=5\), то Вася выпишет на листочек числа \(\{1,3,2,1\}\), отсортирует их и получит массив \(\{1,1,2,3\}\), длина которого равна 4. Середина этого массива находится на позиции \(4/2+1=3\), а искомое число \(a_i=1\) стоит в этом массиве на позициях 1 и 2. Среди этих двух позиций Вася выбирает ту, которая дальше от середины, то есть, позицию 1. Искомая разность между позициями равна 2, и это и есть значение \(c_{2,2,5}\).

Для каждой позиции \(i\) Вася вычисляет величину \(b_i\), которая равна максимуму среди значений \(c_{i,l,r}\) среди всех подотрезков, содержащих позицию \(i\).

Как вы видите, определение числа \(b_i\) достаточно сложное. Помогите Васе вычислить значения \(b_i\) для всех позиций массива.

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

Во второй строке находится \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le n\)) — элементы массива.

Формат выходных данных
В единственной строке выведите \(n\) чисел, \(i\)-е из них должно быть равно \(b_i\).

Примечание

Разберем подробнее первый пример.

Для первой позиции Вася рассмотрит все подотрезки, содержащие эту позицию, в частности, подотрезок \([1,5]\), где \(l=1\) и \(r=5\). Для вычисления \(c_{i,l,r}=c_{1,1,5}\) Вася выпишет числа \(\{5, 4, 3, 2, 1\}\) и после сортировки получит \(\{1, 2, 3, 4, 5\}\). Середина этого массива находится на позиции 3, а искомое число \(a_1=5\) — на позиции 5. Таким образом, \(c_{1,1,5}=2\). Нетрудно заметить, что это число — максимальное среди всех подотрезков, содержащих позицию 1, а значит, \(b_1=2\).
\(b_2=c_{2,2,4}\).
\(b_3=c_{3,3,5}\).
\(b_4=c_{4,1,4}\). Действительно, если выписать числа на подотрезке \([1,4]\), то получится массив \(\{5,4,3,2\}\), который после сортировки превратится в \(\{2,3,4,5\}\). Середина этого массива находится на позиции \(3\), а искомый элемент \(a_4=2\) — на позиции 1. Таким образом, \(c_{4,1,4}=2\).
\(b_5=c_{5,1,5}\).

Дерево отрезков, RSQ, RMQ Использование сортировки реализация

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

Красивые перестановки#50397

Перестановкой размера \(n\) называется массив \(\langle a_1, a_2, \ldots, a_n \rangle\) различных чисел от \(1\) до \(n\). Каждое число в перестановке встречается ровно один раз.

Сеня называет красотой перестановки \(\langle a_1, a_2, \ldots, a_n \rangle\) число \((a_1a_2 + a_2a_3 + \ldots + a_{n-1}a_n)\). Он хочет посчитать количество перестановок, красота которых делится на \(k\).

Даны числа \(n\) и \(k\), найдите количество перестановок размера \(n\), красота которых делится на \(k\).

Например, для \(n = 3\) существует \(6\) перестановок. Рассмотрим все эти перестановки и их красоту.

Перестановка	Красота
\(\langle 1, 2, 3\rangle\)	\(1\cdot2 + 2\cdot3 = 8\)
\(\langle 1, 3, 2\rangle\)	\(1\cdot3 + 3\cdot2 = 9\)
\(\langle 2, 1, 3\rangle\)	\(2\cdot1 + 1\cdot3 = 5\)
\(\langle 2, 3, 1\rangle\)	\(2\cdot3 + 3\cdot1 = 9\)
\(\langle 3, 1, 2\rangle\)	\(3\cdot1 + 1\cdot2 = 5\)
\(\langle 3, 2, 1\rangle\)	\(3\cdot2 + 2\cdot1 = 8\)

Формат входных данных
Входные данные содержат два целых числа: \(n\) и \(k\) (\(1 \le n \le 10\), \(2 \le k \le 1000\)).

Формат выходных данных
Выведите одно целое число: количество перестановок размера \(n\), красота которых делится на \(k\).

Простые задачи на перебор

✓ 6✗ 21—Войти и решать

Фибоначчиевы суммы#50359

Числа Фибоначчи определяются следующим образом: \(F_1 = 1\), \(F_2 = 2\), а для \(n > 2\) выполнено \(F_n = F_{n - 2} + F_{n - 1}\). Таким образом, начало последовательности чисел Фибоначчи выглядит так \(1, 2, 3, 5, 8, 13, 21, \ldots\).

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

Формат входных данных
Первая строка ввода содержит число \(n\) (\(1 \le n \le 100\)).

Вторая строка ввода содержит число \(k\) (\(1 \le k \le 20\)).

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

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

Перебор с возвратом

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

Новое слово#50350

В информатике иногда образуют новые слова, взяв начало одного слова и конец другого. Например, из слов <<tree>> и <<heap>> образовано слово <<treap>>.

Дано слово \(s\) и слово \(t\). Сколько различных слов можно образовать, добавив к непустому началу слова \(s\) непустой конец слова \(t\)?

Формат входных данных
Первая строка входных данных содержит слово \(s\).

Вторая строка входных данных содержит слово \(t\).

Каждое из слов непусто и состоит из строчных латинских букв. Длина каждого из слов не превышает \(100\,000\).

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

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

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

Быстрый исполнитель#49859

Студент первого курса ИТМО Миша изучает новый примитивный язык программирования. В этом языке все операции производятся над массивами целых неотрицательных чисел длины \(n\).

Миша успел создать массив \(a\) и равный ему массив \(b\). Также он успел реализовать четыре функции:

shift — делает циклический сдвиг массива \(a\) влево на \(d\), то есть при \(a = [a_0, a_1, \ldots, a_{n-1}]\) выполняет присваивание \[a \gets [a_d, \ldots, a_{n-1}, a_0, \ldots, a_{d-1}] \text{;}\]
xor — присваивает в массив \(b\) его поэлементный xor (побитовое исключающее <<или>>) с массивом \(a\), то есть \[b \gets [a_0 \oplus b_0, a_1 \oplus b_1, \ldots, a_{n-1} \oplus b_{n-1}] \text{;}\]
and — присваивает в массив \(b\) его поэлементный and (побитовое <<и>>) с массивом \(a\);
or — присваивает в массив \(b\) его поэлементный or (побитовое <<или>>) с массивом \(a\).

Используя эти функции, Миша написал программу, задаваемую последовательностью операций xor, and и or длины \(m\). Программа в цикле \(p\) раз выполняет следующие действия: для каждой операции из последовательности сначала вызывается shift, а затем соответствующая этой операции функция. Так, для последовательности операций \([\mathtt{or}, \mathtt{xor}, \mathtt{and}]\) и \(p = 5\) программа будет выглядеть как

b = a = [...]
repeat 5 times {
    shift
    or
    shift
    xor
    shift
    and
}

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

Формат входных данных
В первой строке ввода перечислены четыре целых числа \(n\), \(m\), \(d\) и \(p\) — длина массива, количество операций в последовательности, величина сдвига и количество повторений (\(0 \le d < n \le 2 \cdot 10^5\); \(1 \le m \le 10\); \(1 \le p \le 10^9\)).

Во второй строке перечислены \(n\) целых чисел \(a_i\) — элементы массива \(a\), они же — изначальные значения элементов массива \(b\) (\(0 \le a_i \le 10^9\)).

В третьей строке через пробел перечисены \(m\) слов, каждое из которых равно <<xor>>, <<and>> или <<or>> — последовательность применяемых на каждой итерации цикла операций.

Формат выходных данных
Выведите \(n\) целых чисел — элементы массива \(b\) после выполнения описанной программы.

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

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

Перекладывание ответственности#49858

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

Всего в команде разработчиков \(n\) человек. Также есть \(n\) задач, которые необходимо подготовить. Подготовка \(i\)-й задачи требует подготовки ровно \(c_i\) ее элементов, и разработка каждого элемента \(i\)-й задачи имеет сложность \(w_i\).

Было решено, что каждый разработчик будет отвечать за столько же элементов, за сколько он бы отвечал, если бы разрабатывал целиком соответствующую задачу. Иными словами, \(i\)-му разработчику будет назначено ровно \(c_i\) элементов из различных задач. Распределение элементов по разработчикам происходит следующим образом:

Сначала первому разработчику выдается \(c_1\) элементов, затем второму — \(c_2\), и так далее. Переход к \((i+1)\)-му разработчику происходит в тот момент, когда \(i\)-му назначается ровно \(c_i\) элементов.
Элементы, за которые будет отвечать каждый разработчик, выбираются по одному из всех еще не до конца распределенных задач по очереди. Сначала будет выбран один этап из первой задачи, затем — из второй, из третьей, и так далее по кругу. Если в какой-то задаче не осталось нераспределенных этапов, она пропускается.
Элементы, назначаемые очередному разработчику, выбираются начиная с той задачи, на которой остановился предыдущий разработчик. То есть, если последний элемент, назначенный предыдущему разработчику, был из \(x\)-й задачи, то первый элемент, назначенный следующему, будет из задачи \((x+1) \bmod n\) (если в ней еще остались нераспределенные элементы).

Иными словами, поддерживается набор еще не до конца распределенных задач и указатель \(x\) на <<текущую>> задачу. Когда надо выдать текущему разработчику очередной элемент, ему выдается один элемент из задачи \(x\), после чего \(x\) сдвигается по кругу вперед на следующую задачу.

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

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

В \(i\)-й из следующих \(n\) строк через пробел даны два целых числа \(c_i\) и \(w_i\) — количество элементов в \(i\)-й задаче и сложность их разработки (\(1 \le c_i, w_i \le 10^9\)).

Формат выходных данных
В единственной строке выведите через пробел \(n\) чисел, \(i\)-е из которых равно суммарной сложности разработки элементов, доставшихся \(i\)-му разработчику.

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

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

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

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

SpamGPT-4#49856

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

После старта оба бота отправляют друг другу по одному сообщению, после чего первый бот отправляет новое сообщение каждые \(a\) секунд, а второй — каждые \(b\) секунд. Иными словами, первый бот отправляет новое сообщение на секундах \(0\), \(a\), \(2a\), и так далее, а второй — на секундах \(0\), \(b\), \(2b\), и так далее.

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

Вам даны параметры ботов \(a\) и \(b\). Определите, сколько сообщений каждый из ботов должен будет отправить к моменту времени \(T\), если они оба будут работать без ошибок.

Формат входных данных
В единственной строке ввода через пробел даны три целых числа \(a\), \(b\) и \(T\) — периодичности отправки новых сообщений и время работы ботов (\(1 \le a, b, T \le 10^9\)).

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

Замечание
Пояснение ко второму примеру:

в момент времени \(0\) первый бот отправляет второму сообщение A, а второй первому — B;
в момент времени \(1\) боты отправляют друг другу ответы на полученные на нулевой секунде сообщения: первый второму B(1) (ответ на B), а второй первому — A(1);
в момент времени \(2\) новых сообщений не появляется, и они отправляют друг другу ответы на полученные на первой секунде сообщения: A(2) (ответ на A(1)) и B(2);
в момент времени \(3\) будут отправлены B(3) и A(3), и одновременно с этим второй бот отправит первому новое сообщение C;
в момент времени \(4\) первый отправит второму новое сообщение D, C(1) (ответ на C) и A(4), а второй первому — B(4);
в момент времени \(5\) новых сообщений нет, боты отправляют друг другу ответы на полученные секунду назад сообщения;
в момент времени \(6\) будут отправлены ответы на сообщения с предыдущей секунды, а также второй бот отправит первому новое сообщение E.

Итого, первый бот отправил: A, B(1), A(2), B(3), D, C(1), A(4), B(5), D(2), C(3) и A(6), всего 11 сообщений.

Второй бот тоже отправил ровно 11 сообщений: B, A(1), B(2), C, A(3), B(4), D(1), C(2), A(4), E и B(6).

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

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

Плагиат кода#49855

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

Компания пишет на эзотерическом языке программирования, похожем на Malbolge, поэтому код каждого из сотрудников представляет из себя строчку из маленьких латинских букв. Код Алисы — строка \(t\), а код Боба — строка \(s\).

Поскольку клавиатура Боба сломана, он может печатать ровно два символа за раз, то есть может вставлять в любое место строки два любых (не обязательно одинаковых) символа. После заявления Алисы о подозрении Боба в плагиате их начальник начал анализировать строки \(s\) и \(t\), пытаясь понять, мог ли Боб получить строку \(s\) из строки \(t\) со своей сломанной клавиатурой. Для этого он пытается постепенно удалять из строки \(s\) по два соседних символа, пока не получит в итоге строrку \(t\).

Помогите выяснить, виноват ли Боб в плагиате: определите, можно ли получить строку \(t\) из строки \(s\), вырезая из нее произвольное количество раз по два стоящих рядом символа.

Входные данные
В первой строке дана строка \(s\), состоящая из маленьких латинских букв от ‘a’ до ‘z’ (\(1 \le |s| \le 2 \cdot 10^5\)).

Во второй строке дана строка \(t\), также состоящая из маленьких латинских букв (\(1 \le |t| \le |s|\)).

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

В качестве ответа выведите <<YES>>, если из \(s\) можно получить \(t\) удалениями двух символов подряд, и <<NO>> в противном случае.

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

"Два указателя"

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

Биржа - 2#49776

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

Торги проходят в течении \(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\), деньги потраченные на непроданные акции не учитываются.

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

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

Трансформация массива - 2#49774

Вам дано \(t\) пар массивов \(a_i\) и \(b_i\) равной длины.

За одну операцию модификации можно:

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

Для каждой пары массивов найдите минимальное число операций, которые необходимо применить к массиву \(a_i\), чтобы получить массив \(b_i\), или определите, что это невозможно.

Входные данные
В первой строке дано число \(t\) — число пар массивов (\(1 \le t \le 40\)).

В следующих \(3t\) строках содержатся описания пар массивов. Каждая пара описывается тремя строками.

В первой из них дано число \(n_i\) — количество элементов в каждом массиве \(i\)-й пары(\(1 \le n_i \le 10\)). Во второй строке заданы \(n_i\) чисел \(a_{i,j}\) — элементы массива \(a_i\) (\(1 \le a_{i,j} \le 1000\)). В третьей строке заданы \(n_i\) чисел \(b_{i,j}\) — элементы массива \(b_i\) (\(1 \le b_{i,j} \le 1000\)).

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

Выходные данные
Для каждого пары массивов выведите одно число — минимальное число операций, которые необходимо применить к массиву \(a_i\), чтобы получить массив \(b_i\), или \(-1\), если для данной пары это невозможно.

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

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

Сортировка по сумме строк#49709

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

Формат входных данных
В первой строке записаны два числа N и M - количество строк и столбцов матрицы соответственно (1 <= N, M <= 50 ). В следующих N строках записаны строки матрицы, в каждой – по M натуральных чисел, разделённых пробелами.

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

Алгоритмы сортировки

✓ 9✗ 5—Войти и решать

Перевод из 10 сс в двоичную сс#49564

Переведите {1} из десятичной системы счисления в двоичную систему счисления.

Двоичная система счисления

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

Подпоследовательность с кратным количеством#49445

Дана последовательность из N чисел. Известно, что сумма всех чисел последовательности не превышает 10⁹. Рассматриваются все её непрерывные подпоследовательности, в которых количество положительных чисел кратных двум кратно K. Найдите такую подпоследовательность с максимальной суммой.

Формат входных данных
В первой строке записаны два натуральных числа N и K (1 <= N <= 1 000 000, 1 <= K <= 100). Каждая из следующих N строк содержит одно число, не превышающее по модулю 1 000.

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

Линейный поиск

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

Алёна и таблички#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—Войти и решать

Тестирование мессенджера - 2#49030

Перед выпуском VK Messenger’а разработчики из компании IT-компании <<VK>>, как и положено, убеждаются в корректности работы приложения. Проверкой корректности работы систем занимаются тестировщики и QA-инженеры.

Часть функциональных тестов для тестирования смены ников выглядит следующим образом:

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

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

Каждый сценарий состоит из трех наборов событий.

Первый набор состоит из событий вида <<в момент времени \(t_i\) поступил запрос регистрации нового пользователя с ID \(\mathtt{id}_i\) и ником \(\mathtt{handle}_i\)>>.

Гарантируется, что ID уникальны для всех пользователей приложения. Если выбранный ник никем не занят, регистрация проходит успешно, иначе запрос на регистрацию отклоняется. Во втором случае пользователь с тем же ID может попробовать зарегистрироваться еще раз.
Второй набор описывает события вида <<в момент времени \(t_i\) пользователь с ником \(\mathtt{handle}_{i,1}\) отправляет запрос на смену ника на \(\mathtt{handle}_{i,2}\)>>.

Гарантируется, что для каждого такого запроса ник \(\mathtt{handle}_{i,1}\) кому-то принадлежит. Если \(\mathtt{handle}_{i,2}\) уже занят каким-либо пользователем, запрос отклоняется, иначе пользователь успешно меняет ник. При успешной смене ника старый ник перестает ассоциироваться с каким-либо пользователем, пока кто-то снова его не займет.
Третий набор описывает события вида <<в момент времени \(t_i\) пользователь с ником \(\mathtt{handle}_{i,1}\) отправляет сообщение пользователю с ником \(\mathtt{handle}_{i,2}\).

Гарантируется, что и \(\mathtt{handle}_{i,1}\) и \(\mathtt{handle}_{i,2}\) на момент времени \(t_i\) соответствуют каким-то зарегистрированным пользователям.

Также гарантируется, что никакие два события не происоходят в одно и то же время, то есть все \(t_i\) уникальны.

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

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

Далее следуют \(T\) описаний сценариев. Описание каждого сценария начинается с пустой строки, после чего следуют три набора событий. В первой строке описания \(q\)-го набора (\(q\) от \(1\) до \(3\)) дано единственное целое число \(n_q\) — количество событий в наборе, после чего следуют \(n_q\) строк в указанном ниже формате (\(1 \le n_1 + n_2 + n_3 \le 1000\); \(0 \le n_q\)).

События первого набора задаются в формате <<REG \(\mathtt{id}_i\) BY \(\mathtt{handle}_i\) AT \(t_i\)>>.
События второго набора задаются в формате <<CHANGE \(\mathtt{handle}_{i,1}\) TO \(\mathtt{handle}_{i,2}\) AT \(t_i\)>>.
События третьего набора задаются в формате <<SEND FROM \(\mathtt{handle}_{i,1}\) TO \(\mathtt{handle}_{i,2}\) AT \(t_i\)>>.

Моменты событий \(t_i\) — целые числа от \(1\) до \(10^9\). Также все \(\mathtt{id}_i\) — целые числа от \(1\) до \(10^9\), а \(\mathtt{handle}_i\) — строки из маленьких латинских букв длины не более \(10\).

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

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

В первой строке статистики выведите целое число \(q\) — количество зарегистрированных пользователей. В следующих \(q\) строках выведите статистику для каждого пользователя в порядке возрастания их ID в формате <<<\(\mathtt{id}\)> RECEIVED <\(\mathtt{total}\)> TOP <\(\mathtt{count}_\mathrm{top}\)> FROM <\(\mathtt{id}_\mathrm{top}\)>>>, где \(\mathrm{total}\) — суммарное количество полученных пользователем сообщений, \(\mathtt{id}_\mathrm{top}\) — ID пользователя, от которого он получил больше всего сообщений, а \(\mathtt{count}_\mathrm{top}\) — само количество сообщений, полученных от пользователя \(\mathtt{id}_\mathrm{top}\).

Если у некоторого пользователя есть несколько собеседников, отправивших ему максимальное число сообщений, выведите в качестве \(\mathtt{id}_\mathrm{top}\) минимальный из их ID. Если пользователь не получал сообщения, считайте \(\mathtt{count}_\mathrm{top}\) равным \(0\).

Задача на реализацию Сортировка событий Хеш

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

Тестирование мессенджера#49029

Часть функциональных тестов для тестирования смены ников выглядит следующим образом:

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

Каждый сценарий состоит из трех наборов событий.

Первый набор состоит из событий вида <<в момент времени \(t_i\) поступил запрос регистрации нового пользователя с ID \(\mathtt{id}_i\) и ником \(\mathtt{handle}_i\)>>.

Гарантируется, что ID уникальны для всех пользователей приложения. Если выбранный ник никем не занят, регистрация проходит успешно, иначе запрос на регистрацию отклоняется. Во втором случае пользователь с тем же ID может попробовать зарегистрироваться еще раз.
Второй набор описывает события вида <<в момент времени \(t_i\) пользователь с ником \(\mathtt{handle}_{i,1}\) отправляет запрос на смену ника на \(\mathtt{handle}_{i,2}\)>>.

Гарантируется, что для каждого такого запроса ник \(\mathtt{handle}_{i,1}\) кому-то принадлежит. Если \(\mathtt{handle}_{i,2}\) уже занят каким-либо пользователем, запрос отклоняется, иначе пользователь успешно меняет ник. При успешной смене ника старый ник перестает ассоциироваться с каким-либо пользователем, пока кто-то снова его не займет.
Третий набор описывает события вида <<в момент времени \(t_i\) пользователь с ником \(\mathtt{handle}_{i,1}\) отправляет сообщение пользователю с ником \(\mathtt{handle}_{i,2}\).

Гарантируется, что и \(\mathtt{handle}_{i,1}\) и \(\mathtt{handle}_{i,2}\) на момент времени \(t_i\) соответствуют каким-то зарегистрированным пользователям.

Также гарантируется, что никакие два события не происоходят в одно и то же время, то есть все \(t_i\) уникальны.

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

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

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

События первого набора задаются в формате <<\(t_i\): REG \(\mathtt{id}_i\) \(\mathtt{handle}_i\)>>.
События второго набора задаются в формате <<\(t_i\): CHANGE \(\mathtt{handle}_{i,1}\) \(\mathtt{handle}_{i,2}\)>>.
События третьего набора задаются в формате <<\(t_i\): SEND \(\mathtt{handle}_{i,1}\) \(\mathtt{handle}_{i,2}\)>>.

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

В первой строке статистики выведите целое число \(q\) — количество зарегистрированных пользователей. В следующих \(q\) строках выведите статистику для каждого пользователя в порядке возрастания их ID в формате <<<\(\mathtt{id}\)> SENT <\(\mathtt{total}\)> TOP <\(\mathtt{count}_\mathrm{top}\)> TO <\(\mathtt{id}_\mathrm{top}\)>>>, где \(\mathrm{total}\) — суммарное количество отправленных пользователем сообщений, \(\mathtt{id}_\mathrm{top}\) — ID пользователя, получившего от него больше всего сообщений, а \(\mathtt{count}_\mathrm{top}\) — само количество сообщений, отправленных пользователю \(\mathtt{id}_\mathrm{top}\).

Если у некоторого пользователя есть несколько собеседников, получивших от него максимальное число сообщений, выведите в качестве \(\mathtt{id}_\mathrm{top}\) минимальный из их ID. Если пользователь не отправлял сообщения, считайте \(\mathtt{count}_\mathrm{top}\) равным \(0\).

реализация Сортировка событий Хеш

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

Устранение массива#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—Войти и решать