Информатика

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

+ 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).

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

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

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

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

Из большой фотографии нужно вырезать прямоугольную область для аватарки. Программа получает на вход размеры исходной фотографии n и m, затем n строк по m чисел - пиксели, затем координаты вырезаемой области: r1, c1, r2, c2 (номера строк и столбцов начальной и конечной точек, нумерация с 1, включительно). Программа должна вывести вырезанную область: сначала её размеры (количество пикселей: по строкам и по столбцам через пробел), затем сами пиксели вырезанной части. Значения пикселей в вырезанной части выводятся построчно через пробел.

Детектор границ помогает найти контуры объектов на фото. Граница - это место, где яркость резко меняется. Программа получает на вход размеры изображения n и m (2<=n,m<=10), затем n строк по m чисел - яркость пикселей, затем порог чувствительности T. Программа должна вывести карту границ: n строк по m чисел (0 или 1). Пиксель является границей (выводим 1), если разница по модулю между ним и хотя бы одним из соседей (сверху, снизу, слева, справа) больше или равна T. Иначе выводим 0. Для крайних пикселей проверяем только существующих соседей. Пиксели в одной строке выводить через один пробел.

Фотография получилась блёклой! Нужно увеличить контраст: тёмные пиксели сделать ещё темнее, а светлые - ещё светлее. Программа получает на вход размеры фото n и m, затем n строк по m чисел - яркость пикселей (от 0 до 255). Программа должна применить увеличение контраста по правилу:
- Если яркость < 128 (тёмный пиксель): новая_яркость = старая_яркость / 2
- Если яркость >= 128 (светлый пиксель): новая_яркость = 128 + (старая_яркость - 128) / 2
Ответ округлять до целого вниз.

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

Помните плёночные фотоаппараты? У них были негативы, где светлое становилось тёмным, а тёмное - светлым! Давайте создадим негатив цифрового фото. Программа получает на вход размеры фото n и m, затем n строк по m чисел - яркость пикселей (от 0 до 255, где 0 - чёрный, 255 - белый). Программа должна вывести негатив: n строк по m чисел. Каждый пиксель инвертируется по формуле: новая_яркость = 255 - старая_яркость.