Информатика

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

Множество 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

Символ	Множитель	Очки	Пояснение
x	×1	+1	Обычный режим
x	×1	+1	Обычный режим
(	—	—	Поле активировано, ×2
x	×2	+2	Внутри поля
(	—	—	Второе поле, ×4
x	×4	+4	Двойная вложенность
x	×4	+4	Двойная вложенность
)	—	—	Внутреннее поле снято, ×2
x	×2	+2	Снова одинарное поле
)	—	—	Все поля сняты, ×1
x	×1	+1	Обычный режим

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

Формат ввода

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

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

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

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

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

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

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

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

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

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

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

Свиток: abbaca

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

Космическая станция «Орион» принимает сигналы от спутников-разведчиков. Приёмная матрица станции имеет размер 640 строк на 480 позиций. При получении каждого сигнала в журнал записываются координаты активированного элемента матрицы: номер строки и номер позиции в строке.

Элемент матрицы, который принял хотя бы один сигнал, считается активным. Элемент, который не принял ни одного сигнала, считается неактивным.

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

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


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

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

В каждой из следующих N строк записаны по два числа через пробел:
- номер строки (целое число от 1 до 640)
- номер позиции в строке (целое число от 1 до 480)

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

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

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

Программист Вася заказывает пиццу. В меню есть N топпингов, пронумерованных от 1 до N. Вася хочет попробовать ВСЕ возможные комбинации топпингов (включая пиццу без топпингов).

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

ВАЖНО: Пиццы в списке должны быть отсортированы в лексикографическом порядке. Топпинги внутри каждой пиццы должны быть в порядке возрастания номеров.

ВХОДНЫЕ ДАННЫЕ:
Одно число N (1 ≤ N ≤ 10) - количество топпингов в меню.

ВЫХОДНЫЕ ДАННЫЕ:
Выведите 2^N строк - все возможные пиццы.
Пустая пицца (без топпингов) обозначается как "-".
Для непустых пицц выведите номера топпингов через пробел.
 

Кролик Роджер находится в начале числовой прямой (позиция 0) и хочет добраться  до позиции N, где лежит гигантская морковка.

Кролик умеет делать только два вида прыжков:
- Короткий прыжок: +1 позиция (тратит 1 единицу энергии)
- Длинный прыжок: +2 позиции (тратит 1 единицу энергии)

Сколько РАЗЛИЧНЫХ способов есть у Роджера добраться до морковки?

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

ВХОДНЫЕ ДАННЫЕ:
Одно число N (0 ≤ N ≤ 45) - позиция морковки.

ВЫХОДНЫЕ ДАННЫЕ:
Одно число - количество различных способов добраться до морковки.

В подземелье живут гномы. У них есть древняя традиция деления золота:

Когда гном получает N монет:
1. Если N = 0, гном грустит и ничего не делает
2. Если N = 1, гном оставляет монету себе и кричит "МОЁ!"
3. Если N > 1:
   - Гном берёт себе 1 монету и кричит "МОЁ!"
   - Остальные (N-1) монет делит пополам
   - Левую половину (N-1)/2 отдаёт левому ученику-гному
   - Правую половину (N-1) - (N-1)/2 отдаёт правому ученику-гному
   - Каждый ученик делает то же самое по традиции

Подсчитайте, сколько раз прозвучит крик "МОЁ!" при делении N монет.

Формат входных данных
Одно число N (0 ≤ N ≤ 10^9) - начальное количество монет.

Формат выходных данных
Одно число - сколько раз прозвучит "МОЁ!"
 

В университетской столовой осталось K порций борща. В очереди стоят студенты, каждый хочет съесть определённое количество порций (голодные студенты бывают!).

Студент подходит к раздаче:
- Если борща хватает на его запрос - он получает всё и уходит СЧАСТЛИВЫМ
- Если борща осталось меньше, но хоть что-то есть - забирает остатки и уходит ГОЛОДНЫМ  
- Если борща совсем нет - уходит ЗЛЫМ

После обслуживания всех студентов повар хочет знать:
1. Сколько студентов ушли СЧАСТЛИВЫМИ
2. Сколько студентов ушли ГОЛОДНЫМИ
3. Сколько студентов ушли ЗЛЫМИ
4. Сколько порций борща осталось

Пояснение к примеру
- Было 10 порций
- Студент 1 хочет 3: получает 3, осталось 7 (СЧАСТЛИВ)
- Студент 2 хочет 5: получает 5, осталось 2 (СЧАСТЛИВ)  
- Студент 3 хочет 4: получает только 2, осталось 0 (ГОЛОДЕН)
- Студент 4 хочет 2: борща нет (ЗОЛ)
- Итого: 2 счастливых, 1 голодный, 1 злой, 0 остаток

 

Программа получает на вход размеры матрицы n и m (количество строк и столбцов), затем элементы матрицы (n строк по m чисел в каждой). Все числа целые, не превышают по модулю 1000. Программа должна вывести количество локальных максимумов. Элемент является локальным максимумом, если он строго больше всех своих соседей (соседями считаются элементы слева, справа, сверху и снизу, если они существуют).

Программа получает на вход размер квадратной матрицы n, затем элементы матрицы (n строк по n чисел в каждой). Все числа целые, не превышают по модулю 1000. Программа должна вывести сумму элементов, расположенных выше главной диагонали (элементы, где номер столбца больше номера строки при нумерации с 0).

Программа получает на вход размер квадратной матрицы n, затем элементы матрицы (n строк по n чисел в каждой). Все числа целые, не превышают по модулю 1000. Программа должна вывести сумму элементов побочной диагонали (элементы, где сумма номера строки и номера столбца равна n+1 при нумерации с 1).