Алгоритмы

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

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

1. 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{;}\]

2. 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{;}\]

3. and — присваивает в массив \(b\) его поэлементный and (побитовое <<и>>) с массивом \(a\);

4. 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\) после выполнения описанной программы.

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

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

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

1. Сначала первому разработчику выдается \(c_1\) элементов, затем второму — \(c_2\), и так далее. Переход к \((i+1)\)-му разработчику происходит в тот момент, когда \(i\)-му назначается ровно \(c_i\) элементов.

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

3. Элементы, назначаемые очередному разработчику, выбираются начиная с той задачи, на которой остановился предыдущий разработчик. То есть, если последний элемент, назначенный предыдущему разработчику, был из \(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\)-му разработчику.

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

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

Для тестирования отказоустойчивости двух лучших спам-ботов компании <<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\)-ю секунду, их тоже следует учесть в ответе.

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

1. в момент времени \(0\) первый бот отправляет второму сообщение A, а второй первому — B;

2. в момент времени \(1\) боты отправляют друг другу ответы на полученные на нулевой секунде сообщения: первый второму B(1) (ответ на B), а второй первому — A(1);

3. в момент времени \(2\) новых сообщений не появляется, и они отправляют друг другу ответы на полученные на первой секунде сообщения: A(2) (ответ на A(1)) и B(2);

4. в момент времени \(3\) будут отправлены B(3) и A(3), и одновременно с этим второй бот отправит первому новое сообщение C;

5. в момент времени \(4\) первый отправит второму новое сообщение D, C(1) (ответ на C) и A(4), а второй первому — B(4);

6. в момент времени \(5\) новых сообщений нет, боты отправляют друг другу ответы на полученные секунду назад сообщения;

7. в момент времени \(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).

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

Компания пишет на эзотерическом языке программирования, похожем на 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>> в противном случае.

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

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

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

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

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

Вам дано \(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\), если для данной пары это невозможно.