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

ПТИЦЫ#27173

Всеволод Юрьевич устроился работать охранником на склад. Работа монотонная, и от скуки Всеволод Юрьевич считает ворон и других птиц, пролетающих мимо будки охраны. За годы работы он обнаружил следующую закономерность. Вороны летают поодиночке, начиная с 8:00 утра с периодичностью P1 минут, а после 8:00 вечера летать перестают. Утки пролетают стайками по N штук, начиная с 10:00 утра, с периодичностью P2 минут и перестают летать после 5:00 вечера. Голуби летают поодиночке с 7:00 утра до 8:00 вечера с периодичностью P3 минут. Три раза в день Всеволоду Юрьевичу приходится отвлечься от своего занятия ровно на полтора часа, чтобы принять на склад товар. Приемка начинается ровно в 11:00, 15:00 и 17:00. Сколько птиц (M) Всеволод Юрьевич насчитает за смену, если смена начинается в 6:00 утра и заканчивается в 6:00 утра на следующий день?

Во всех временных интервалах левый конец входит в него, а правый - нет. Например, одна из приемок начинается в 11:00 и Всеволод Юрьевич не считает птиц пролетающих в моменты с 11:00 до 12:29 включительно, а птиц, пролетающих в 12:30 - считает.

Формат входных данных
В строке указываются 4 целых положительных числа не превышающих 10000 каждое: P1, P2, N, P3, разделенные пробелом.
Формат выходных данных
В единственной строке указывается целое число M – количество птиц, которых Всеволод Юрьевич насчитает за смену при указанных условиях входа.

Ввод	Вывод
P1 P2 N P3	M
23 57 5 7	123

Разбор случаев

✓ 2✗ 51 000средняяВойти и решать

Intelligence in Perpendicularia#27118

There are only two directions in Perpendicularia: vertical and horizontal. Perpendicularia government are going to build a new secret service facility. They have some proposed facility plans and want to calculate total secured perimeter for each of them.
The total secured perimeter is calculated as the total length of the facility walls invisible for the perpendicularly-looking outside observer. The figure below shows one of the proposed plans and corresponding secured perimeter.

Write a program that calculates the total secured perimeter for the given plan of the secret service facility.

Input
The plan of the secret service facility is specified as a polygon. The first line of the input contains one integer n — the number of vertices of the polygon (4 ≤ n ≤ 1000). Each of the following n lines contains two integers xi and yi – the coordinates of the i-th vertex (−10⁶ ≤ x_i , y_i ≤ 10⁶ ). Vertices are listed in the consecutive order. All polygon vertices are distinct and none of them lie at the polygon’s edge. All polygon edges are either vertical (x_i = x_i+1) or horizontal (y_i = y_i+1) and none of them intersect each other.

Output
Output a single integer — the total secured perimeter of the secret service facility.

Input	Output
10 1 1 6 1 6 4 3 4 3 3 5 3 5 2 2 2 2 3 1 3	6

Вывод формулы

✓ 5✗ 01 000средняяВойти и решать

КОЛОНИЗАЦИЯ МАРСА#27072

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

Формат входных данных
Задается одно число N ( 1<= N <= 10⁹ ) – необходимое количество воды.

Формат выходных данных
Одно целое число M – минимально необходимое количество суток.

Ввод	Вывод
2	3

Замечание
Одна из правильных последовательностей действий выглядит так:
? В первые сутки мини-фабрика производит дрона для сбора воды;
? За вторые сутки мини-фабрика производит еще одного дрона, а первый дрон собирает одну единицу воды;
? За третьи сутки мини-фабрика может произвести еще одного дрона или мини- фабрику, при этом первый дрон собирает еще одну единицу воды (итого он собрал 2 единицы воды), а второй дрон собирает единицу воды. Таким образом, накоплено 3 единицы воды за трое суток.

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

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

✓ 11✗ 151900средняяВойти и решать

Огромное число#27070

Вася получил длинную последовательность из цифр следующим образом. Он брал подряд натуральные числа, начиная с 1, переводил их в четверичную систему счисления и записывал результаты перевода друг за другом. Вот начало этой последовательности:
123101112132021222330313233100…
Вася остановился только тогда, когда дописал в конец последовательности четверичную запись числа 1023₁₀. Затем он представил, что это одно большое число, записанное в четверичной системе счисления, и перевел его в шестнадцатеричную систему счисления.

Определите, какая шестнадцатеричная цифра стоит в этом числе на a-ой позиции, считая слева направо от начала числа. В ответе укажите эту шестнадцатеричную цифру.

Задача на реализацию Системы счисления

✓ 29✗ 137800средняяВойти и решать

Тяжелая, вариант-2#27065

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

Машины в Берляндии представляют собой отрезки длинной l. Автостоянка представляет отрезок на прямой [0;M]. В точке 0 и точке M находятся стены. В некоторых точках Xi этого отрезка могут стоять машины, то есть левая граница отрезка, образующего машину, находится в точке Xi. Уже стоящие на стоянке машины не пересекаются, но могут стоят вплотную друг к другу или к стене.

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

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

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

В первой строке записаны четыре целых неотрицательных числа n, M, l и b (0 ≤ n ≤ 100, 1 ≤ M ≤ 100000, 1 ≤ l ≤ 100000, 0 ≤ b ≤ 100000) — количество автомобилей на стоянке, длина стоянки, длина автомобиля в Берляндии и необходимое расстояние от границ приехавшего автомобиля до ближайшего препятствия.

В следующей строке находятся n неотрицательных чисел Xi (Xi < M) — точки, в которых располагаются левые границы машин.

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

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

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

Если не существует машины, которую можно было бы поставить, удовлетворяя все условия, выведите 0.

Пример входных и выходных данных

Ввод	Вывод	Примечание
4 21 1 1 7 12 3 16	1
4 30 3 1 24 5 11 18	1
2 20 3 1 7 10	0	В данном примере машины стоят вплотную, и между ними нельзя поставить никакую машину.

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

✓ 15✗ 21900средняяВойти и решать

Легкая, вариант-2#27063

Сервер одной крупной аналитической компании делает резервное копирование всех данных каждые пол часа. Системный администратор Илья Филиппович Яковлев заступит сегодня на смену в известное время. Он знает, что сервер делает резервное копирование в полночь (00:00:00), но не может посчитать, когда же будет следующее резервное копирование после момента его заступления на смену.

Ваша задача — написать программу, которая определит время следующего резервного копирования после начала смены Ильи Филипповича. Считается, что резервное копирование происходит мгновенно. Таким образом, если Илья Филиппович заступает в момент резервного копирования, считается, что оно происходит уже в его смену.

Формат входного файла

На вход программе подается строка, в которой находится время заступления Ильи Филипповича в формате hh:mm:ss, где hh обозначает часы в 24-часовом формате, mm — минуты, а ss — секунды. Гарантируется, что время корректно.

Формат выходного файла

Требуется вывести время следующего резервного копирования в аналогичном формате.

Пример входных и выходных данных

Ввод	Вывод
12:55:00	13:00:00
00:00:00	00:00:00
18:30:03	19:00:00

Дата и время Задачи на моделирование

✓ 31✗ 53800средняяВойти и решать

Пираты!#27043

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

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

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

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

Помогите ему определить, на какое минимальное расстояние придјтся подойти к пиратской базе, двигаясь по самому безопасному маршруту.

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

В первой строке записано натуральные числа N и M (1 <= N, M <= 1 000 000) количество строк и столбцов на игровом поле.

Во второй строке записано натуральное число K (1 <= K <= 500) количество пиратских баз.

В следующих K строках записаны пары чисел R_i , C_i (1 <= R_i <= N, 1 <= C_i <= M) координаты пиратских баз (строка, столбец).

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

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

Система оценки

Решения, верно работающие при N, M 6<=500, будут набирать не менее половины баллов.

Ввод	Вывод
10 10 4 2 2 5 3 5 9 8 8	3

Замечание

Пример одного из безопасных маршрутов показан на рисун ке. Пиратские базы обозначены чјрным, клетки маршрута серым. Минимальное расстояние от пиратской базы до маршрута 3 хода.

Двумерные массивы Использование сортировки

✓ 9✗ 221 100средняяВойти и решать

Время полета#27040

При полутах на самолетах в качестве времени вылета и прилета используется местное время аэропортов вылета и прилета.

Часовые пояса характеризуются разницей во времени с меридианом, на котором расположена Гринвичская обсерватория. Для каждого часового пояса вводится отклонение от UTC (Всемирного координированного времени).

Например, Москва расположена в часовом поясе UTC+3, а Новосибирск в часовом поясе UTC+7. Если вылететь из Москвы рейсом в 11:15 и временем полјта ровно в 4 часа, то прилет будет в Новосибирск будет в 19:15 (4 часа полёта и 4 часа разницы во времени).

Например, Москва расположена в часовом поясе UTC+3, а Новосибирск в часовом поясе UTC+7. Если вылететь из Москвы рейсом в 11:15 и временем полјта ровно в 4 часа, то прилјт будет в Новосибирск будет в 19:15 (4 часа полёта и 4 часа разницы во времени).

Часовые пояса могут изменяться от UTC-11 (Американское Самоа) до UTC+14 (острова Лайн, Кирибати).

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

пути.

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

В первой строке записаны целые числа H_D, M_D (0 <= H_D <= 23, 0 <= M_D <= 59) время вылета.

Во второй строке записаны целые числа H_F , M_F (0 <= H_F <= 10⁹, 0 <= M_F <= 59) время полёта.

В третьей строке записаны целые числа D, A (-11 6 D, A <= 14) часовые пояса аэропорта вылета и прилёта.

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

Выведите три числа H_A;M_A; Days время прилёта в часах и минутах, а также разницу в датах между датой вылета и датой прилёта.

Система оценки

Решения, верно работающие для рейсов, дата вылета и прилјта которых не отличаются, будут набирать не менее половины баллов.

Ввод	Вывод
11 15 4 0 3 7	19 15 0
12 0 1 0 -10 13	12 0 1

Замечание

Первый тест соответствуте разобранному в условии примеру с Москвой и Новосибирском.

Второй тест соответствует, например, часовому перелету из Американского Самоа на Самоа.

Самолет вылетает в 12:00, летит в течение часа и приземляется в 12:00 местного времени. Т.к. он пересёк линию перемены даты, то на Самоа уже наступил следующий день.

В реальности существуют часовые пояса, которые отличаются от UTC на нецелое число часов, однако в задаче они не рассматриваются.

Вывод формулы

✓ 28✗ 114800средняяВойти и решать

Алгоритмизация и программирование#27033

Дан фрагмент программы:

Операции MOD, mod и функция ост_дел вычисляют остаток от деления первого аргумента на второй. Операции \, div и функция цел_дел осуществляют целочисленное деление. Какое минимальное значение целочисленной переменной X должно было быть перед началом выполнения этого фрагмента, если после его выполнения получилось значение R=A?, где А - вводится с клавиатуры.
В ответе укажите целое число.

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

✓ 16✗ 34900средняяВойти и решать

Сумма ряда - 7#27009

Дан числовой ряд и малая величина eps=0.001. С точностью eps (то есть, если сумма при очередном добавлении слагаемого будет отличаться на величину меньшую чем 0.001 от предыдущей, то это слагаемое считается последним) найти сумму ряда, общий член которого задан формулой (n>0):

\(a_n = {2^n \cdot n! \over{n^n}}\)

Выведите на экран сумму такого ряда.

Циклы

✓ 23✗ 186800средняяВойти и решать

Сумма ряда - 4#27006

\(a_n = {1 \over{(3 \cdot n - 2)\cdot(3\cdot n+1)}}\)

Выведите на экран сумму такого ряда.

Циклы

✓ 25✗ 85800средняяВойти и решать

Сумма ряда - 1#27003

\(a_n = {(-1)^{n-1} \over{n^n}}\)

Выведите на экран сумму такого ряда.

Циклы

✓ 33✗ 154800средняяВойти и решать

Пароль#26999

Антон вводит пароль. Артур подглядывает за Антоном и записывает последовательность клавиш, которые тот нажимает. Иногда Артур не разбирает клавишу и пишет вместо неё символ «*». Артур знает, что пароль Антона является сочетанием (без пробелов) его часто произносимых слов.

Каждое слово может присутствовать в пароле любое количество раз, в том числе 0. Артур решил восстановить пароль Антона. Какое минимальное количество вариантов ему потребуется перебрать?

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

В первой строке находятся два числа N и K (1 <= N <=1000,1 <=K <= 10). Во второй строке находится строка из N символов - последовательность, которую записал Артур. Последовательность может содержать строчные буквы латинского алфавита и знак «*».

Далее идут K строк, которые обозначают часто произносимые слова Антона. Каждое слово состоит не более чем из 10 строчных латинских букв. Других символов в словах нет.

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

Если количество вариантов не более 10⁹, выведите это количество. Иначе выведите единственную строку «MNOGO».

Ввод	Вывод
12 3 r*mm** mama mila ramu	4
10 8 ********** a b c d e f g h	MNOGO

Динамическое программирование: один параметр Строки

✓ 2✗ 41 100средняяВойти и решать

Массив#26995

У Пети есть массив отсортированных в порядке неубывания натуральных чисел. Известно, что чисел N. Петя пытливый мальчик, поэтому хочет найти в массиве три числа x, y и z (x <= y <= z), такие, что сумма (x - y)² + (x - z)² + (z - y)² была бы максимальна. Помогите ему в этом.

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

В первой строке входного файла находится число N> (3<=N <= 100000). На следующей строке находятся N натуральных чисел, каждое из которых не превышает 10000.

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

Нужно вывести три числа x, y и z в порядке возрастания. Если вариантов такой тройки несколько, вывести любой.

Ввод	Вывод
4 1 2 3 5	1 2 5

Одномерные массивы

✓ 12✗ 65800средняяВойти и решать

2048#26981

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

Напомним правила игры 2048. На поле 4 × 4 разбросаны числа, являющиеся степенями двойки от 2 до 1024, некоторые клетки могут быть пустыми. Каждый ход игрок может сдвинуть все плитки игрового поля в одну сторону. Если при сдвиге две плитки одного номинала «налетают» одна на другую, то они слипаются в одну, номинал которой равен сумме соединившихся плиток. За каждое соединение игровые очки увеличиваются на номинал получившейся плитки. Плитка, получившаяся при слипании двух других, не может больше участвовать в слипании.

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

Программа получает на вход четыре строки, в каждой из которых записано четыре числа. Числа являются степенями двойки от 2 до 1024. В некоторых клетках записано число 0, означающий, что данная клетка пуста.

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

Выведите единственное число — максимальное количество очков, которое можно получить за один ход из данной позиции.

Примеры

№	Входные данные	Выходные данные
1	2 0 0 0 2 0 0 0 2 0 0 0 0 0 0 0	4
2	2 0 0 0 2 0 0 0 2 0 0 0 2 0 0 0	8
3	2 2 4 0 0 0 0 0 0 0 0 0 0 0 0 0	4
4	2 2 4 0 0 2 2 2 0 2 4 0 2 4 4 0	16

Примечания

Внимательно прочитайте этот раздел для лучшего понимания правил игры.

Наилучший ответ на первый тест достигается движением вниз.
0 0 0 0
0 0 0 0
2 0 0 0
4 0 0 0

Наилучший ответ на второй тест достигается движением вниз.
0 0 0 0
0 0 0 0
4 0 0 0
4 0 0 0

Наилучший ответ на третий тест достигается движением влево.
4 4 0 0
0 0 0 0
0 0 0 0
0 0 0 0

Наилучший ответ на четвертый тест достигается движением вниз.
0 0 0 0
0 2 4 0
0 4 2 0
4 4 8 2

Двумерные массивы

✓ 5✗ 161 000средняяВойти и решать

Бумага для олимпиады#26980

Лёлик решил провести у себя в школе олимпиаду. Для этого ему необходимо закупить много упаковок бумаги. Лёлику очень повезло, потому что один крупный канцелярский магазин объявил две рекламных акции: «купи A одинаковых товаров и получи еще один товар бесплатно», а также «купи B товаров по цене B-1 товара».

Лёлик узнал, что одна пачка бумаги в этом магазине стоит n рублей. Теперь он хочет определить сколько упаковок бумаги он сможет купить на p рублей. Помогите ему.

Формат ввода

На вход подаются четыре натуральных числа, разделенных пробелом: A, B, p и n (1 ≤ A ≤ 100, 2 ≤ B ≤ 100, 1 ≤ p, n ≤ 10000).

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

Выведите единственное целое число — максимальное количество упаковок бумаги, которое сможет купить Лёлик.

Пример

Ввод	Вывод
4 4 13 2	8
3 4 8 3	2
3 4 7 1	9

Примечания

В первом примере, дважды используя вторую акцию, можно купить 8 упаковок бумаги, заплатив за 6.

Во втором примере акциями воспользоваться нельзя.

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

Вывод формулы

✓ 28✗ 170900средняяВойти и решать

Логические выводы#26979

Болик решает логическую задачу. Для ее решения, он сначала сделал N базовых предположений. После этого происходит следующий процесс: Холмс разбивает все предположения на пары, из каждой пары отбрасывает наименее вероятное предположение (предположения таковы, что всегда есть наименее вероятное). Если получилось так, что какому-то предположению, пары не хватило, то Болик оставляет его для рассмотрения. Алгоритм повторяется пока у Болика не останется последнее предположение.

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

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

Формат ввода

На вход подается натуральное число N (1 ≤ N ≤ 10²¹⁸) — количество базовых предположений.

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

Выведите единственное целое число — количество логических выводов.

Пример

Ввод	Вывод
3	3

Вывод формулы

✓ 33✗ 222800средняяВойти и решать

Выборка чисел для максимальной суммы, кратной 4#25979

Имеется набор данных, состоящий из троек натуральных чисел. Необходимо выбрать из каждой тройки два числа так, чтобы сумма всех выбранных чисел была кратна 4 и при этом была максимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0.

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

Выходные данные
Выведите ответ на задачу

Примеры

№	Входные данные	Выходные данные
1	6 8 3 4 4 8 12 9 5 6 2 8 3 12 3 5 1 4 12	88

ЕГЭ - вычислительные задачи

✓ 208✗ 2 3191 000средняяВойти и решать

Дело в шляпах#25919

Как-то раз в город Шляп заехал известный парикмахер. До его приезда парикмахеры были явно не очень, так как все жители города предпочитали ходить в шляпах. Но наконец-то настало время снять шляпы!

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

Стоять в очереди скучно, поэтому если подряд приходят двое или более людей в шляпах одинакового фасона они начинают между собой активно общаться и необычайно гордиться своими шляпами (но всё равно заходят на стрижку, если уж их очередь подошла). Однако, если следом за ними в очередь встаёт человек в шляпе другого фасона, то вся группа подряд стоящих людей в одинаковых шляпах подозрительно смотрит на только что пришедшего "чужого" и совсем уходит из очереди. При этом очередь сдвигается и может появиться новая группа общающихся людей.

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

Местного шляпника теперь интересует, каким жителям ему больше не нужно будет делать шляпы, так как они будут ходить с новыми стильными стрижками?

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

В первой строке содержится число N (1 <= N <= 10⁵) количество людей, которые придут к парикмахеру.

Каждая из следующих N строк обозначает пришедшего к парикмахеру жителя и содержит по три числа: фасон шляпы (все фасоны местного шляпника пронумерованы от 1 до 10⁹), момент времени прихода s (1 <= s <= 10⁹), и время на стрижку t (1 <= t <= 10⁹). Строки упорядочены по времени прихода жителей. Гарантируется, что все приходят в разное время. Так как парикмахер очень крут, гарантируется, что он успеет постричь всех жителей до момента времени 2 · 10⁹, даже если бы из очереди никто не уходил.

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

В единственной строке выведите через пробел номера людей в очереди в порядке возрастания, которых парикмахер всё-таки пострижёт. Люди нумеруются в порядке прихода в очередь, начиная с 1.

Ввод	Вывод
5 1 2 7 2 4 3 2 6 2 1 7 3 3 8 2	1 4 5

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

✓ 5✗ 22900средняяВойти и решать

Держать строй#24911

Ник Фьюри решил, что бойцы отряда спецназа, являющегося подразделением организации S.H.I.E.L.D., помогут мстителям отразить атаку войска Локи. Он решил, что в бой отправятся n бойцов, а все остальные понадобятся в других местах. Теперь ему осталось только выбрать, какие именно бойцы пойдут в атаку.

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

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

Формат входного файла

Первая строка входного файла содержит два числа n и m (1 ≤ n ≤ 100 000, 0 ≤ m ≤ 200 000) количество солдат в строю и количество команд, которые подаст Ник. Вторая строка содержит n целых неотрицательных чисел, не превосходящих 10⁹ исходный рост солдат в строю. Следующие m строк содержат команды, подаваемые Ником. Если первый символ в строке, описывающей очередную команду, '!', то за ним следуют два числа k и x (1 ≤ k ≤ n, 0 ≤ x ≤ 10⁹), где k место в строю того солдата, которого должен заменить солдат роста x. Команда второго типа описывается знаком '?'.

Формат выходного файла

Для каждой команды второго типа в отдельной строке выведите "YES", если в данный момент солдаты в строю стоят по неубыванию роста, и "NO" в противном случае.

Ввод	Вывод
5 5 2 4 6 8 10 ? ! 2 7 ? ! 3 8 ?	YES NO YES

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

✓ 11✗ 56900средняяВойти и решать