Информатика

Два интернет-магазина продают товары. Маркетолог хочет найти:

1. Товары, которые продаются только в первом магазине

2. Товары, которые продаются только во втором магазине

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

В первой строке — число N (1 ≤ N ≤ 100000) — количество товаров первого магазина.

Во второй строке — N целых чисел — коды товаров первого магазина (1 ≤ код ≤ 1000000).

В третьей строке — число M (1 ≤ M ≤ 100000) — количество товаров второго магазина.

В четвёртой строке — M целых чисел — коды товаров второго магазина.

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

Первая строка: товары только первого магазина (в порядке возрастания через пробел) или "NONE".

Вторая строка: товары только второго магазина (в порядке возрастания через пробел) или "NONE".

Учитель математики дал двум ученикам, Пете и Васе, задания. Нужно мог ли Петя списать все заданяи у Васи, то есть является ли множество заданий Пети подмножеством заданий Васи .

Множество A является подмножеством B (A ⊆ B), если каждый элемент A также является элементом B.

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

В первой строке — число N (1 ≤ N ≤ 100000) — количество заданий Пети.

Во второй строке — N целых чисел — номера заданий Пети (1 ≤ номер ≤ 1000000).

В третьей строке — число M (1 ≤ M ≤ 100000) — количество заданий Васи.

В четвёртой строке — M целых чисел — номера заданий Васи.

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

"YES", если множество Пети является подмножеством множества Васи, иначе "NO".

Два программиста, Алекс и Макс, решали задачи на соревновании. Жюри хочет узнать, какие задачи решил ровно один из них (не оба сразу).

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

В первой строке — число N (1 ≤ N ≤ 100000) — количество задач, решённых Алексом.

Во второй строке — N целых чисел — номера задач Алекса (1 ≤ номер ≤ 1000000).

В третьей строке — число M (1 ≤ M ≤ 100000) — количество задач, решённых Максом.

В четвёртой строке — M целых чисел — номера задач Макса.

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

Номера задач, решённых ровно одним программистом (в порядке возрастания через пробел). Если таких нет — выведите "NONE".

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

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

В первой строке — число N (1 ≤ N ≤ 100000) — количество марок у Вики.

Во второй строке — N целых чисел — номера марок Вики (1 ≤ номер ≤ 1000000).

В третьей строке — число M (1 ≤ M ≤ 100000) — количество марок у Ники.

В четвёртой строке — M целых чисел — номера марок Ники.

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

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

Два брата, Коля и Толя, написали списки желаемых подарков на Новый Год. Мама хочет узнать, какие подарки хочет только Коля (но не Толя), чтобы подарить их именно ему.

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

В первой строке — число N (1 ≤ N ≤ 100000) — количество подарков в списке Коли.

Во второй строке — N целых чисел — номера подарков Коли (1 ≤ номер ≤ 1000000).

В третьей строке — число M (1 ≤ M ≤ 100000) — количество подарков в списке Толи.

В четвёртой строке — M целых чисел — номера подарков Толи.

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

Все номера подарков, которые хочет только Коля (в порядке возрастания через пробел). Если таких нет — выведите "NONE".

Два друга, Алиса и Боб, составили списки своих любимых чисел. Найди все числа, которые нравятся ОБОИМ друзьям. Числа в списках Алисы и Боба могут повторяться и не обязательно отсортированы.

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

В первой строке — число N (1 ≤ N ≤ 100000) — размер списка Алисы.

Во второй строке — N целых чисел — любимые числа Алисы (1 ≤ число ≤ 1000000).

В третьей строке — число M (1 ≤ M ≤ 100000) — размер списка Боба.

В четвёртой строке — M целых чисел — любимые числа Боба.

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

Все общие числа в порядке возрастания через пробел. Если общих чисел нет — выведите "NONE".

У Васи есть набор чисел. Для каждого запроса нужно найти минимальное число из набора, которое больше или равно заданному X. Если такого числа нет, вывести -1.

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

В первой строке — число N (1 ≤ N ≤ 100000) — размер набора.

Во второй строке — N целых чисел (1 ≤ число ≤ 1000000).

В третьей строке — число Q (1 ≤ Q ≤ 100000) — количество запросов.

В следующих Q строках — по одному числу X (1 ≤ X ≤ 1000001).

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

Для каждого запроса выведите ответ на отдельной строке.

На шахматном турнире участники получают баллы. Судья хочет в любой момент знать: какой максимальный и какой минимальный балл среди всех участников?

Участники могут присоединяться к турниру или выбывать:

+ X — игрок с баллом X пришёл на турнир

- X — игрок с баллом X ушёл с турнира

? — запрос минимального и максимального балла

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

В первой строке — число Q (1 ≤ Q ≤ 100000) — количество событий.

В следующих Q строках — события в указанном формате.

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

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

Для каждого запроса "?" выведите два числа через пробел: минимальный и максимальный балл.

Петя записывает ID своих друзей в социальной сети. Некоторые ID повторяются (когда друзья заходят несколько раз). Петя хочет получить список всех уникальных ID в отсортированном порядке от меньшего к большему.

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

В первой строке — число N (1 ≤ N ≤ 100000) — количество записей.

Во второй строке — N целых чисел — ID друзей (1 ≤ ID ≤ 1000000).

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

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

Волшебник Мерлин управляет своей библиотекой заклинаний. Он может выполнять три типа операций:

+ X — добавить книгу с номером X в библиотеку

- X — убрать книгу с номером X из библиотеки

? X — проверить, есть ли книга с номером X в библиотеке

Помоги Мерлину ответить на все его вопросы!

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

В первой строке — число Q (1 ≤ Q ≤ 100000) — количество операций.

В следующих Q строках — операции в формате: "+ X", "- X" или "? X" (1 ≤ X ≤ 1000000).

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

Для каждой операции "?" выведите "YES", если книга есть в библиотеке, или "NO", если её нет.

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

Робот перемещается по бесконечному полю и выполняет программу:

• L — шаг влево (x уменьшается на 1)
• R — шаг вправо (x увеличивается на 1)
• U — шаг вверх (y увеличивается на 1)
• D — шаг вниз (y уменьшается на 1)
• ( — установить хронометку (запомнить текущую позицию как безопасную)
• ) — экстренный возврат (переместиться к последней метке, метка исчезает)

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

Робот начинает разведку в точке (0, 0). По записи бортового журнала определи, в какой точке робот завершил миссию.

Пример

Журнал: RRR(RR)DD

Робот прошёл 3 клетки вправо, поставил метку на случай опасности, продолжил разведку ещё на 2 клетки вправо. Затем обнаружил угрозу и активировал возврат к метке. Оказавшись в безопасности, спустился на 2 клетки вниз.

Шаг  Команда  Позиция   Что произошло
─────────────────────────────────────────────
 0      —     (0, 0)    Старт миссии
 1      R     (1, 0)    Шаг вправо
 2      R     (2, 0)    Шаг вправо
 3      R     (3, 0)    Шаг вправо
 4      (     (3, 0)    Метка установлена
 5      R     (4, 0)    Шаг вправо
 6      R     (5, 0)    Шаг вправо
 7      )     (3, 0)    Возврат к метке!
 8      D     (3, -1)   Шаг вниз
 9      D     (3, -2)   Шаг вниз

Финальная позиция: 3 -2

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

Одна строка — запись бортового журнала.

• Символы: L, R, U, D, (, )
• Длина: от 1 до 10⁵ символов
• Гарантируется корректность: каждому ) предшествует непогашенная (

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

Два целых числа через пробел — координаты (x, y) финальной позиции робота.

В далёкой галактике проходит ежегодный Космический турнир по бластерболу. Правила подсчёта очков необычны:

• Каждое попадание x приносит базовые очки
• Капитан может активировать силовое поле, введя символ ( — пока оно активно, все очки удваиваются
• Деактивация поля происходит по вводу символа ) — возврат к обычному режиму
• Силовые поля могут быть вложенными — тогда множители перемножаются!

Запись матча — строка из символов x, ( и ). Подсчитай итоговый счёт команды.

Пример

Запись матча: xx(x(xx)x)x

Итого: 1 + 1 + 2 + 4 + 4 + 2 + 1 = 15

Формат ввода

Одна строка, содержащая запись матча.

• Символы: x (попадание), ( (активация поля), ) (деактивация)
• Длина строки: 1 ≤ |s| ≤ 10⁵
• Гарантируется корректность скобочной последовательности

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

Одно целое число — итоговый счёт команды.

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

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

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

Вводится строка, содержащая символы английского алфавита
 

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

Выведите результирующую строку

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

Свиток: abbaca

1. Руны bb аннигилируют → aaca
2. Руны aa аннигилируют → ca
3. Больше пар нет → ответ: ca

Фрагмент звёздного неба спроецирован на плоскость с декартовой системой координат. Учёный решил провести кластеризацию полученных точек, являющихся изображениями звёзд, то есть разбить их множество на N непересекающихся непустых подмножеств (кластеров), таких, что точки каждого подмножества лежат внутри прямоугольника со сторонами длиной H и W, причём эти прямоугольники между собой не пересекаются. Стороны прямоугольников не обязательно параллельны координатным осям. Гарантируется, что такое разбиение существует и единственно для заданных размеров прямоугольников.

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

Расстояние между двумя точками на плоскости \(A(x_1, y_1) \ и \ B(x_2, y_2)\) вычисляется по формуле:

\(d(A, B) = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}.\)

В файле A хранятся координаты точек двух кластеров, где H = 6,5 и W = 4,5 для каждого кластера. В каждой строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y. Известно, что количество точек не превышает 1000.

В файле Б хранятся координаты точек трёх кластеров, где H = 6,5, W = 5 для каждого кластера. Известно, что количество точек не превышает 10 000. Структура хранения информации в файле Б аналогична структуре в файле A.

Для файла A определите координаты центра каждого кластера, затем найдите два числа: \(P_1\) – минимальное расстояние от начала координат до центра кластера, и \(P_2\) – максимальное расстояние от начала координат до центра кластера.

Для файла Б определите координаты центра каждого кластера, затем найдите два числа: \(Q_1\) – в кластере с наибольшим количеством точек число таких точек, которые находятся на расстоянии не менее 1,0 от центра кластера, и \(Q_2\) – в кластере с наибольшим количеством точек число точек, которые находятся на расстоянии не более 0,5 от центра кластера. Гарантируется, что во всех кластерах количество точек различно.

В ответе запишите четыре числа: в первой строке – сначала целую часть произведения \(P_1 \times 10\,000\), затем целую часть произведения \(P_2 \times 10\,000\); во второй строке – сначала \(Q_1\), затем \(Q_2\).

Возможные данные одного из файлов проиллюстрированы графиком.

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

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

Алгоритм формирования рейтинга выглядит следующим образом:

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

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

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

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

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

Типовой пример организации данных во входном файле

5
800 120
150 200
250 300
60 100
180 220

Пример организации данных приведён для пяти смартфонов.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

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

Напишите программу, которая перебирает целые числа, большие 13 200 000, в порядке возрастания и ищет среди них такие, для которых значение M превышает 30 000 и оканчивается на 55.

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

Например, для числа 20 M = 2 + 5 = 7.

Количество строк в таблице для ответа избыточно.

Текстовый файл состоит из десятичных цифр и заглавных букв латинского алфавита. Определите в прилагаемом файле максимальное количество идущих подряд символов, среди которых буква W встречается ровно 36 раз, чётная цифра встречается ровно один раз, искомая последовательность начинается с этой единственной чётной цифры.

В ответе запишите число – количество символов в найденной последовательности.

Для выполнения этого задания следует написать программу.

Исполнитель преобразует число, записанное на экране. У исполнителя есть три команды, которые обозначены латинскими буквами:

• A. вычти 2
• B. вычти 4
• C. найди целую часть от деления на 2

Программа для исполнителя – это последовательность команд.

Сколько существует программ, для которых при исходном числе 86 результатом является 14, при этом траектория вычислений содержит число 39 и не содержит чисел 26 и 76?

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

Например, для программы CBA при исходном числе 23 траектория состоит из чисел 11, 7, 5.

В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы A и B могут выполняться только последовательно.

Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы – время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение 0.

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

Типовой пример организации данных в файле

Для приведённой таблицы процесс 3 начинается на 8-й мс, заканчивается на 9-й мс.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

Для игры, описанной в задании 19, найдите минимальное значение S, при котором одновременно выполняются два условия:

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