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

Простые числа(2)#55095

Вывести все простые числа от M до N включительно.

Входные данные
В первой строке находятся разделённые пробелом M и N. 2 <= M <= N <= 1 000 000.

Выходные данные
Вывести числа в порядке возрастания, по одному в строке. Если между M и N включительно нет простых - вывести "Absent".

Одномерные массивы Простые числа и разложение на множители

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

Слияние списков#47668

У Максимуса есть коллекция волшебных амулетов, каждый из которых обладает своей магической силой. Список имеющихся у него амулетов отсортирован в порядке неубывания магической силы. Вернувшись из очередного путешествия, Максимус составил список новых амулетов, предварительно отсортировав их по невозрастанию магической силы. Теперь у него два отдельных списка и он хочет объединить их в один упорядоченный по неубыанию список.
Он хочет сделать это как можно быстрее. Помогите ему отсортировать два этих списка. Максимус просит вас написать программу, которая будет работать за O(len(A)+len(B)).

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

Выходные данные
Программа должна вывести последовательность неубывающих чисел, полученных объединением двух данных списков.

Примеры

№	Входные данные	Выходные данные
1	`1 5 7 2 4 4 5`	`1 2 4 4 5 5 7`

"Два указателя"Одномерные массивы

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

Два массива - 2#45460

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

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

В первой строке содержится число n (1 <= n <= 100000) - количество чисел, записанных Алисой. Во второй строке идет n целых чисел, не превосходящих по модулю 10⁹ – числа Алисы. Третья строка содержит целое число m - количество чисел, записанных профессором Селезневым (1 <= m <= 100000) . В четвертой строке идет m целых чисел, не превосходящих по модулю 10⁹ – числа профессора Селезнева.

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

Выведите YES, если профессор и Алиса записали одни и те же числа, и слово NO в противном случае.

Примеры

№	Входные данные	Выходные данные
1	3 2 0 7 4 2 0 0 7	YES

Одномерные массивы Сортировка слиянием

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

Книжки с полки#43532

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

Особенность полок в библиотеке Пети такова, что он может брать только крайнюю книгу с полки (то есть либо самую левую, либо самую правую).

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

Входные данные
В первой строке записано одно целое число n (2 <= n <= 100) - количество книг на полке. Во второй строке находится n целых различных чисел a₁, a₂, ..., a_n (1 <= a_i <= 10⁶) - количество страниц в книге.

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

Примеры

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

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

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

Дети в круг#42273

Анна Николаевна в детском саду играет с детьми в игру. По кругу стоят стулья. Все стулья пронумерованы от 1 до N (1 <= N <= 100000). Имя каждого ребенка закодировано натуральным числом, не превышающим 10⁹. Анна Николаевна хлопает в ладоши K раз (|K| <= 100000) тихо или громко. Если Анна Николаевна хлопает в ладоши тихо, то все дети должны быстро пересесть на K стульев вправо. Если же Анна Николаевна хлопает в ладоши громко, то все дети должны быстро пересесть на K стульев влево.

Чтобы Анне Николаевна было проще определять все ли дети пересели верно, напишите для нее программу, которая бы определяла положение каждого ребенка после пересаживания.

В данной задаче нельзя использовать дополнительные массивы (списки). Обратите внимание, что нужно именно преобразовать имеющийся массив(список) и распечатать его целиком, а не создать новый, даже назвав его тем же самым именем (это возможно в языке Python).

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

В первой строке дано натуральное число N, во второй строке N целых чисел, а в последней целое число K. Все числа во входных данных не превышают 10⁹. Если число K > 0, это означает, что Анна Николаевна хлопала в ладоши тихо. Число K < 0, это означает, что Анна Николаевна хлопала в ладоши громко.

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

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

Примеры

№	Входные данные	Выходные данные
1	5 5 3 7 4 6 3	7 4 6 5 3

Одномерные массивы Работа с элементами (вставка, удаление, сдвиг)

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

Безумный ученый#39516

Фермер Джон упорядочил N своих коров (1 ≤ N ≤ 1000) каждая из которых имеет одну из двух пород Holsteins или Guernseys. Он зафиксировал этот порядок в виде строки из N символов, каждый из которых либо H, либо G соответственно. К несчастью, когда коровы прибыли на ферму и он снова их выстроил, они образовали строку, отличную от исходной.

Назовём эти две строки A и B, где A - исходная строка, которую он хотел увидеть, B - строка которая получилась по прибытию коров. ФД попросил помощи у кузена Бена.

После нескольких месяцев работы, Бен создал замечательную машину MCBF-3000, которая способна взять любую подстроку и поменять в ней все G на H, а все H на G. Теперь ФД хочет узнать минимальное количество применений этой машины, которые позволят превратить строку B в строку A. Помогите ФД.

Входные данные
Первая строка содержит N, а следующие две строки содержат строки A и B. Каждая из строк состоит только из символов H и G.
Выходные данные
Выведите минимальное количество раз применения машины MCBF-3000 для трансформации строки B в строку A.

Примеры

№	Входные данные	Выходные данные
1	7 GHHHGHH HHGGGHH	2

Одномерные массивы Цикл for

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

Громозека и Алиса - 2#39397

Алиса и Громозека пошли гулять по городу. Заходя в первое кафе, Алиса посмотрела на часы и запомнила время входа. Далее она запоминала только количество минут, которое они с Громозекой тратили между двумя посещенными кафе (от входа в одно кафе, до входа в другое). По окончании прогулки, Алиса решила восстановить хронологию - время входа в очередное кафе.
Напишите программу, которая определит, в какое время Алиса и Громозека заходили в очередное кафе.

Входные данные
В первой строке задан, момент времени, в который Громозека и Алиса вошли в первое кафе. Формат времени: часы (число от 00 до 23), далее идет двоеточие, затем минуты (число от 00 до 59). Строка времени записана без пробелов.
Во второй строке записано натуральное число N (2 <= N <= 1000) - количество посещенных кафе (включая кафе из которого они вышли в начальный момент времени и последнее кафе). В третьей строке записано N-1 число: первое показывает время в минутах от входа в первое кафе до входа во второе, второе - время от входа во второе кафе до входа в третье и т.д. Каждое из этих чисел натуральное и не превышает 1000.

Выходные данные
Выведите для каждого кафе время входа Алисы и Громозеки. Формат времени должен быть такой же, как и во входных данных.

Примеры

№	Входные данные	Выходные данные
1	07:00 4 10 5 3	07:00 07:10 07:15 07:18

Задача на реализацию Одномерные массивы Циклы

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

Набор с максимальной средней суммой#38582

Дан набор из N элементов. Значение i-го элемента (\(1<=i<=N\)) равно v_i. Из данного набора выбирается не менее A и не более B элементов. Найти максимально возможное среднее арифметическое значений выбранных элементов. Кроме того, найти количество способов выбора элементов, чтобы среднее значение выбранных элементов было максимальным.

Входные данные
В первой строке задается три целых числа через пробел: N (\(1<=N<=50\)), A и B (\(1<=A,B<=N\)). В следующих N строках записаны целые числа v_i (\(1<=v_i<=10^{15}\)), по одному числу в строке.

Выходные данные
Выведите две строки.
Первая строка должна содержать максимально возможное среднее арифметическое значений выбранных элементов. Вывод следует считать правильным, если абсолютная или относительная погрешность не превышает \(10^{-6}\).
Вторая строка должна содержать количество способов выбора элементов, чтобы среднее значение выбранных элементов было максимальным.

Примеры

№	Входные данные	Выходные данные	Пояснения
1	5 2 2 1 2 3 4 5	4.500000 1	Среднее значение выбранных элементов будет максимальным при выборе четвертого и пятого элементов. Следовательно, первая строка вывода должна содержать 4.5. Нет другого способа выбрать элементы, чтобы среднее значение было 4,5, и поэтому вторая строка вывода должна содержать 1.
2	4 2 3 10 20 10 10	15.000000 3	Может быть несколько способов выбора элементов, чтобы среднее значение было максимальным.
3	5 1 5 1000000000000000 999999999999999 999999999999998 999999999999997 999999999999996	1000000000000000.000000 1

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

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

Конфеты и коробки#38505

В ряд расположены N ящиков. Изначально в i-м ящике слева находится a_i конфет. Громозека выбирает ящик, содержащий хотя бы одну конфету, и съедает одну из конфет в выбранном ящике.Он может выполнять это действие любое количество раз. Его цель добиться того, чтобы в любых двух соседних коробках содержалось не более x конфет.
Найдите минимальное количество операций, необходимых для достижения цели Громозеки.

Входные данные
В первом строке задается два числа N (\(2<=N<=10^5\)) и x (\(0<=x<=10^9\)). Во второй строке содержится N целых чисел a_i(\(0<=a_i<=10^9\)).

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

Примеры

№	Входные данные	Выходные данные	Пояснения
1	3 3 2 2 2	1	Необходимо съесть одну конфету во второй коробке. Тогда количество конфет в каждой коробке станет (2,1,2).
2	6 1 1 6 1 2 0 4	11	Например, можно съесть шесть конфет во второй коробке, две в четвертой и три в шестой. Тогда количество конфет в каждой коробке станет (1,0,1,0,0,1).
3	5 9 3 1 4 1 5	0	Цель уже достигнута
4	2 0 5 5	10	Все конфеты должны быть съедены.

Одномерные массивы Перебор Цикл for

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

Черепахи#38364

Широко известна следующая задача для младших школьников. Три черепахи ползут по дороге. Одна черепаха говорит: “Впереди меня две черепахи”. Другая черепаха говорит: “Позади меня две черепахи”. Третья черепаха говорит: “Впереди меня две черепахи и позади меня две черепахи”. Как такое может быть? Ответ: третья черепаха врет!

По дороге одна за другой движутся N черепах. Каждая черепаха говорит фразу вида: “Впереди меня a_i черепах, а позади меня b_i черепах”. Ваша задача определить самое большое количество черепах, которые могут говорить правду.

Входные данные
В первой строке вводится целое число N (1 ≤ N ≤ 10000) . Далее следуют N строк, содержащих целые числа ai и bi, по модулю не превосходящие 10000, описывающие высказывание i-ой черепахи.

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

Выходные данные
Выведите целое число M – максимальное количество черепах, которые могут говорить правду.

Примеры

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

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

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

Блины#38339

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

N гостей сидят за столом, и перед каждым стоит тарелка с блинами. На тарелке i-го гостя лежит ai блинов. Каждый гость съедает один блин за одну минуту, таким образом, время, когда закончит есть блины последний человек, равно наибольшему значению из ai.

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

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

Программа получает на вход натуральное число N, не превосходящее 100.000, – первоначальное количество гостей. Следующие N строк содержат натуральные числа a_i – количество блинов на тарелке i-го человека. Значения a_i даны в порядке неубывания, то есть a_i ≤ a_i+1. Сумма значений всех a_i не превосходит 2·10⁹.

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

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4 1 3 5 6	4	За столом сидят 4 человека, у них на тарелках 1, 3, 5, 6 блинов. Новому гостю последний гость отдаст 2 блина, а предпоследний – 1 блин, и тогда у всех, включая нового гостя, будет не более 4 блинов.

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

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

Дома и магазины#38330

На Новом проспекте построили подряд 10 зданий. Каждое здание может быть либо жилым домом, либо магазином, либо офисным зданием.

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

Входные данные
Программа получает на вход десять чисел, разделенных пробелами. Каждое число задает тип здания на Новом проспекте: число 1 обозначает жилой дом, число 2 обозначает магазин, число 0 обозначает офисное здание. Гарантируется, что на Новом проспекте есть хотя бы один жилой дом и хотя бы один магазин.

Выходные данные
Выведите одно целое число: наибольшее расстояние от дома до ближайшего к нему магазина. Расстояние между двумя соседними домами считается равным 1 (то есть если два дома стоят рядом, то между ними расстояние 1, если между двумя домами есть еще один дом, то расстояние между ними равно 2 и т.д.)

Примеры

№	Входные данные	Выходные данные	Пояснение
1	2 0 1 1 0 1 0 2 1 2	3	В примере из условия дальше всего идти до ближайшего магазина жителям четвертого дома: ближайший к их дому магазин находится в первом доме, и им нужно пройти три дома до него. Жителям других домов придется пройти меньшее расстояние до ближайшего магазина, поэтому ответ 3.

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

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

Лавочки#38306

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

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

Входные данные
В первой строке входных данных содержатся два числа: L - длина лавочки и K - количество гранитных блоков-ножек. Оба числа натуральные и не превышают 10 000.

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

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

Примеры

№	Входные данные	Выходные данные
1	5 2 0 2	2
2	13 4 1 4 8 11	4 8
3	14 6 1 6 8 11 12 13	6 8

Одномерные массивы Условный оператор

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

Нужно больше конфет!#38298

У Карлсона дома есть набор из n банок с конфетами. Банки пронумерованы от 1 до n , в i -й из них лежит a i конфет. Карлсон считает набор банок симпатичным , если в этом наборе нет трех банок с разным числом конфет.

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

Входные данные
Первая строка входных данных содержит натуральное число n ( 1 ≤ n ≤ 10⁵ ) — количество банок в наборе Карлсона.

Вторая строка входных данных содержит n целых чисел a_i ( 0 ≤ a_i ≤ 10⁹ ) — число конфет в банках. Соседние числа отделены друг от друга одним пробелом.

Выходные данные
Выведите одно число — минимальное общее количество конфет, которое придется добавить, чтобы Карлсон считал набор банок симпатичным.

Примечание
В первом тесте из примера Карлсон может добавить в первую банку две конфеты, а во вторую банку — одну конфету. Тогда в первой и четвертой банках будет лежать по 7 конфет, а во второй и третьей — по 2 конфеты.

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

Примеры

№	Входные данные	Выходные данные
1	4 5 1 2 7	3
2	3 1 1 1	0

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

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

Мне только справочку!#38295

У доктора Риты сегодня трудный рабочий день, и она ушла на обеденный перерыв. За это время к ее кабинету выстроилась очередь из n человек! Очередь большая, поэтому в помещении быстро стало очень душно.

Для удобства пронумеруем пациентов натуральными числами от 1 до n в том порядке, в котором они изначально стояли в очереди: первым стоял человек с номером 1 , вторым — с номером 2 , и так далее. Последним был человек с номером n .

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

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

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

Входные данные
В первой строке входных содержатся два числа n и t — число людей в очереди и количество событий, что человек вышел на улицу подышать ( 1 ≤ n , t ≤ 100 000 ).

Во второй строке входных данных содержатся t чисел a i ( 1 ≤ a_i ≤ n ) — номера людей, выходивших подышать и затем встававших в конец очереди в том порядке, в котором они это делали.

Выходные данные
Выведите n чисел — номера людей в порядке очереди после всех перестановок.

Примечание
В тесте из примера происходили следующие изменения с очередью:

Человек с номером 2 перешёл в конец. Порядок людей: 1 , 3 , 4 , 2
Человек с номером 3 перешёл в конец. Порядок людей: 1 , 4 , 2 , 3
Человек с номером 1 перешёл в конец. Порядок людей: 4 , 2 , 3 , 1
Человек с номером 2 перешёл в конец. Порядок людей: 4 , 3 , 1 , 2
Человек с номером 1 перешёл в конец. Порядок людей: 4 , 3 , 2 , 1
Порядок людей в очереди в конце: 4 , 3 , 2 , 1 .

Примеры

№	Входные данные	Выходные данные
1	4 5 2 3 1 2 1	4 3 2 1

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

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

Выбор конфет#38292

Скоро у Гарри Поттера день рождения! Гермиона хочет приготовить для него необычный подарок. Она хочет подарить Гарри набор из n волшебных конфет. Каждая конфета характеризуется её вкусом — целым числом t_i . Удовольствие , которое получит Гарри от набора конфет — это сумма вкусов всех конфет в этом наборе. Обратите внимание, что вкусы конфет, как и удовольствие Гарри, не обязательно должны быть положительными.

У Гермионы есть огромная коробка с конфетами, в которой для каждого целого числа t от - 10⁹ до 10⁹ лежит ровно одна конфета со вкусом t . Гермиона хочет взять из этой коробки n конфет, из которых будет состоять набор для Гарри.

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

Входные данные
Первая строка входных данных содержит единственное целое число n ( 1 ≤ n ≤ 100 ) — количество конфет, которое хочет Гермиона положить в набор. Вторая строка входных данных содержит единственное целое число s ( - 10⁹ ≤ s ≤ 10⁹ ) — удовольствие, которое должен получить Гарри от набора.

Выходные данные
Если составить желаемый набор из имеющихся у Гермионы конфет невозможно, выведите « NO ». Иначе, в первой строке выведите « YES », а во второй строке в произвольном порядке n чисел — вкусы конфет в искомом наборе. Если правильных ответов несколько, выведите любой из них.

Примеры

№	Входные данные	Выходные данные
1	3 10	YES 500000000 -500000000 10

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

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

Подборка новостей#38289

Игорь читает новостную ленту в своей любимой социальной сети, состоящую из n последовательно расположенных записей. Каждая запись в ленте имеет свою характеристику — позитивность a_i , заданную натуральным числом. После прочтения i -й записи настроение Игоря улучшается на a_i .

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

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

Входные данные
Первая строка содержит два числа n и p ( 1 ≤ n ≤ 1000 , 1 ≤ p ≤ 10⁷ ) — количество записей в новостной ленте и величину, на которую Игорь хочет увеличить своё настроение.

Вторая строка содержит n целых неотрицательных чисел a i ( 1 ≤ a_i ≤ 10⁴ ) — позитивности записей в ленте. Соседние числа разделены ровно одним пробелом.

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

Если же решения нет, выведите - 1.

Примеры

№	Входные данные	Выходные данные
1	9 10 1 2 3 4 5 4 3 2 1	3 3
2	5 6 3 1 1 1 4	5 2
3	3 100 10 10 10	-1

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

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

Водопады#38262

Недавно дядя Фёдор прочитал в журнале «Мурзилка», что самый высокий водопад в мире — это водопад Анхель, высота которого составляет 1054 метра. «Вот было бы здорово посмотреть на такой водопад!», — размечтался он.

Но Венесуэла далеко, поэтому пока дядя Фёдор решил начать с исследования речки Сметанки, которая течет рядом с Простоквашино. Она начинается в холмах и постепенно спускается вниз, к деревне. Дядя Фёдор вместе с Шариком прошли вдоль всего течения Сметанки от ее истока. Иногда по пути им встречались водопады. Как дядя Фёдор узнал из той статьи в «Мурзилке», водопадом считается участок реки с постоянным углом наклона, превышающим 45 градусов, то есть такой участок, высота которого больше его длины.

Уже после путешествия, раз за разом перерисовывая карту Сметанки на бумагу, дядя Фёдор заметил, что если нарисовать вид Сметанки сбоку (то есть чем выше нарисована точка — тем выше она над уровнем моря, а чем правее — тем дальше она от истока и ближе к Простоквашино), то получается невозрастающая ломаная, которую очень легко анализировать. Каждый отрезок этой ломаной — это как раз участок реки с постоянным углом наклона, который может оказаться водопадом!

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

Теперь дяде Фёдору стало интересно, а какова высота самого высокого каскада водопадов на Сметанке? Помогите ему: по описанию реки, сделанному Шариком и дядей Фёдором, найдите это число.

Входные данные
В первой строке вводится число n (2<=n<=10⁵ ) — количество вершин ломаной, описывающей речку Сметанку. В следующих n строках перечислены координаты этих точек, в i-й строчке записаны числа x_i и y_i — расстояние от точки до истока по горизонтали и высота точки над уровнем моря (0x_i<=10⁹, y_i<=10⁹ ). Точки перечислены начиная от истока реки, то есть начиная с точки, x-координата которой равна нулю, а y-координата — максимальная среди всех точек. Гарантируется, что река течет сверху вниз и слева направо, то есть каждая следующая точка находится не выше и не левее предыдущей.

Выходные данные
Выведите одно целое число: высоту самого высокого каскада водопадов на этой реке. Если на реке на самом деле нет водопадов, выведите 0.

Примеры

№	Входные данные	Выходные данные
1	3 0 15 1 10 5 5	10

Одномерные массивы Условный оператор

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

Метро#38251

Ваня не очень-то любит людей, но, к сожалению, ему иногда все-таки приходится ездить на метро. В таких случаях ему помогают две вещи: наушники с любимыми «Scoprions» и правильно выбранное место. Поскольку Ваня хочет быть как можно дальше от всех людей, правильным местом считается такое место, расстояние от которого до ближайшего из соседей будет максимально возможным в вагоне. В вагоне N мест и они все расположены вдоль одной стены, причем вход в вагон находится у места с номером 1. Места идут подряд, без пропусков. Ваня понимает, что иногда правильных мест может быть несколько, и хочет сесть на ближайшее ко входу правильное место (то есть правильное место с минимальным номером).

Угадайте, какое место в вагоне займет Ваня.

Входные данные
В первой строке записано число N (1 ≤ N ≤ 105). В следующей строке через пробел записаны N чисел — 0 или 1. Число 0 обозначает свободное место, 1 — занятое; места нумеруются слева направо. Гарантируется, что хотя бы одно место свободно.

Выходные данные
Выведите номер места, на которое Ваня сядет.

Примеры

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

Одномерные массивы Условный оператор

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

Билеты на Сапсан#38242

Саша и Лиза — две самые обычные девочки, которые живут в Москве и очень любят Санкт-Петербург. На каникулы они запланировали обширную экскурсионную программу в северной столице, осталось только купить билеты. Девочки знают, что быстрее всего добраться до Санкт-Петербурга можно на скоростном поезде «Сапсан». В каждом вагоне есть N рядов, в каждом из которых по 4 места, которые нумеруются так:

Саша и Лиза выбрали вагон, в котором они планируют ехать. Оказалось, что в этом вагоне уже продано M билетов и известно, какие места уже заняты. Девочки решили купить билеты таким образом:

если есть два места рядом, то они покупают их (например, 1 и 2 или 3 и 4)
если двух мест рядом нет, то они пытаются купить места рядом через проход (например, 2 и 4)
если нет и таких мест, то они покупают любые два свободных места.

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

Входные данные
В первой строке входных данных содержатся числа N — количество рядов в вагоне (1 ≤ N ≤ 10⁵) и M — количество проданных билетов (1 ≤ M ≤ 4N - 2). В следующей строке записаны M различных чисел — номера мест, на которые билеты уже проданы.

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

Примеры

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

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

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