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

Добраться до игрушек#44034

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

Так как место засекречено, завод постоянно меняет вход в хранилище игрушек.

Дед Мороз знает, что вход в фабрику сегодня расположен у двери с числом X. Также известно, что в коридоре, рядом с числом Y находится дверь, перекрывающая проход по коридору. Чтобы ее открыть необходимо взять ключ, который располагается на стене на полке в коридоре рядом с числом Z.

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

Входные данные
Программа получает на вход строку, содержащую 3 различных ненулевых числа: X, Y, Z (-10³ <= X, Y, Z <= 10³).

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

Примеры

№	Входные данные	Выходные данные
1	10 -10 1	10
2	20 10 -10	40
3	100 1 1000	-1

Простые задачи на перебор Условный оператор

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

Эффективные сборы#43870

Лука часто ездит на сборы по программированию. Сборы длятся n дней. Лука фиксирует количество решенных задач в каждый день сборов. Лука считает сборы «эффективными», если только один непрерывный не нулевой промежуток дней (от l до r), когда выполнялись следующие условия по числу решенных задач:

1 <= l <= r <= n;
a_l = a_l+1 = a_l+2 =…=a_r;
l = 1 или a_l-1 > a_l;
r = n или a_r < a_r+1;

Примеры

Пусть массив A хранит информацию о решении задач за каждый день сборов, тогда:

1) массив A = [5, 3, 3, 2, 3, 3, 4] описывает «эффективные», по мнению Луки, сборы (промежуток в 1 день l = r = 4 удовлетворяет условию);

2) массив А = [2, 2, 2, 3, 4, 4, 5, 6, 7, 7, 8] также описывает «эффективные» сборы (промежут l = 1, r = 3 удовлетворяет условию);

3) массив А = [1, 2, 3, 4, 3, 2, 1] описывает не «эффективные» сборы (есть два промежутка удовлетворяющих условию l = r = 1 и l = r = 7).

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

Входные данные
Первая строка содержит одно целое число n (1 <= n <= 2·10⁵) — длину массива. Вторая строка n целых чисел a_i (1 <= a_i<= 10⁹) — количество решенных Лукой задач в i-й день .

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

Примеры

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

"Два указателя"

✓ 6✗ 12—Войти и решать

Громозека и валерьянка#43474

Громозека очень любит валерьянку. На его родной планете Чумароза можно купить за k чумриков (местная валюта) первую упаковку валерьянки, за 2·k чумриков - вторую и так далее (иными словами, за i-ю упаковку надо заплатить i·k чумриков). Громозека хочет купить w упаковок валерьянки. У него есть n чумриков. Сколько чумриков ему придется взять в кредит в чумарозском банке, чтобы купить w упаковок валерьянки?

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

В первой строке записано три положительных целых числа k, n, w (1 <= k, w <= 1000, 0 <= n <= 10⁹), стоимость первой упаковки, изначальное количество чумарозиков у Громозеки и количество упаковок валерьянки, которые он хочет купить.

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

Выведите единственное целое число - количество чумарозиков, которое Громозеке необходимо взять в кредит в банке. Если брать кредит не надо, выведите 0.

Примеры

№	Входные данные	Выходные данные
1	3 17 4	13

Задача на реализацию Простые задачи на перебор Цикл for Циклы

✓ 160✗ 448500лёгкаяВойти и решать

Секретная последовательность#43349

Алиса оставила для своего отца профессора Селезнева секретную последовательность a[1..n]. Чтобы ее не прятать, она решила написать ее на самом видном месте, но в другом порядке следования чисел. Профессор Селезнев знает, что Алиса переписала секретную последовательность в следующем виде:

первым числом слева записано число a₁;
первым числом справа записано число a₂;
вторым числом слева (после a₁) записано число a₃;
вторым числом справа (то есть перед числом a₂) записано число a₄;
все остальные числа записаны аналогичным образом.

То есть, если бы секретная последовательность была a = [1, 2, 3, 4, 5, 6], то профессор бы увидел следующую последовательность [1, 3, 5, 6, 4, 2]. Профессор Селезнев очень торопился и успел только сохранить в компьютер последовательность, которую увидел. Напишите программу, которая покажет профессору исходную секретную последовательность.

Входные данные
Первая строка содержит размер последовательности n (1 <= n <= 300), записанной Алисой для своего отца. Вторая строка содержит n чисел a_i (1 <= a_i <= 10⁹) - саму последовательность.

Выходные данные
Выведите исходную последовательность, которую Алиса выписывала для отца.

Примеры

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

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

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

Порадомой#43137

В один осенний день чебаркульская сборная по американскому футболу возвращалась на поезде домой после дружеского матча с командой Чебоксар. Подъезжая к очередной реке, главные тренеры футболистов — Алексей Юрьевич и Михаил Леонидович — заметили, что мост через реку на их пути не выглядит слишком надёжно, и, если несколько вагонов с суммарной массой больше W тонн будут целиком находиться на нём, переправа обязательно рухнет. Вагоны, которые находятся на мосту не полностью, не учитываются в суммарной массе.
Алексей Юрьевич, как самый ответственный тренер, точно знает, сколько весит каждый из вагонов поезда: i-й вагон от начала состава имеет массу ai тонн. Михаил Леонидович же имеет идеальное зрение, а потому может сказать, что длина моста равняется длине ровно p вагонов.
Крушения допустить никак нельзя, а потому тренеры приняли волевое решение: отцепить минимальное число вагонов (возможно, все) с конца состава, чтобы поезд смог проехать опасное место. Помогите им и скажите, сколько вагонов придётся оставить до переправы.
Входные данные
В первой строке входных данных через пробел записаны три целых числа n,p и W — количество вагонов в поезде, длина моста в вагонах и максимальная нагрузка в тоннах, которую он выдерживает (1 <= n <= 10⁵, 1 <= p <=10⁵, 0 <= W <=10¹⁴).
Во второй строке через пробел записаны n целых чисел a_i — веса вагонов в порядке их следования от начала состава (1 <= a_i <= 10⁹).
Выходные данные
Выведите единственное число — минимальное количество вагонов, которое надо отцепить от хвоста поезда, чтобы тот смог безопасно проехать по мосту.

Примеры

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

Замечание
В данном тесте мост обрушится, только если на него заедут 3 и 4 вагон одновременно, а это значит, что достаточно отцепить лишь последний вагон.

Задачи на моделирование Префиксные суммы(минимумы, ...)

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

Чебаркульские спортсмены#43136

Алексей Юрьевич и Михаил Леонидович — тренера чебаркульской сборной по американскому футболу. Сегодня им нужно заполнить очень важную анкету на чемпионат мира, в которой необходимо указать всех членов команды в порядке возрастания их силы.
Для решения этой непростой задачи были собраны все игроки сборной, и каждый из спортсменов сказал несколько (возможно ноль) фраз вида: «Я сильнее, чем игрок k» (k может отличаться от высказывания к высказыванию, ни один спортсмен не говорил одинаковых фраз). Когда опрос был окончен, тренера поняли, что теперь могут однозначно упорядочить спортсменов по силе, соответствуя всем высказываниям.
Сразу после того, как Алексей Юрьевич и Михаил Леонидович написали ответ организаторам олимпиады, они задумались, а что было бы, если бы футболисты отвечали иначе? Ведь далеко не во всех случаях можно восстановить единственно возможный порядок игроков.
Теперь им интересно, сколько наборов ответов спортсменов однозначно задают их порядок? Так как это число может быть слишком большим, они просят найти лишь его остаток от деления на 10⁹+7.
Входные данные
Во входных данных записано единственное число n — количество спортсменов в сборной (1 <= n <= 10⁵) .
Выходные данные
Выведите единственное число — количество наборов ответов спортсменов, однозначно позволяющих упорядочить их по силе.

Примеры

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

Замечание
В данном тесте вариантов ответов всего 2: первый сказал, что сильнее второго, второй не сказал ничего, или первый не сказал ничего и второй сказал, что он сильнее первого.

Вывод формулы Комбинаторика

✓ 2✗ 0—Войти и решать

Засада на переговорах#43134

Саша Белый и его бригада приехали на переговоры в Сатку. Однако беседа обещает быть жаркой, поэтому Саша хочет спрятать свою братву в засаду. Переговоры будут проходить на квадратном поле размером 2N×2N, и в каждую клетку этого поля Белый может посадить от 0 до 2 братанов. Так как Саша не любит повторяться, то суммарное количество братанов в каждом столбце и в каждой строке квадратного поля должно быть различным.
Как вы знаете, из-за определённых обстоятельств Белый не закончил вуз, поэтому не силён в программировании, и вам нужно срочно помочь ему.
Подскажите Белому, сможет ли он расставить братву с заданным условием, и если сможет, то приведите пример расстановки.
Входные данные
Во входных данных записано единственное целое число N такое, что 2N — длина стороны поля (1 <= N <= 300).
Выходные данные
На первой строке выведите YES, если существует расстановка, что суммарное количество братанов в каждом столбце и в каждой строке квадратного поля различно, и NO в противном случае. Если расстановка существует, то на следующих 2N строках выведите пример. Если существует несколько подходящих расстановок, то можете вывести любую из них.

Примеры

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

Задача на реализацию Конструктив

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

Очередные операции над массивом#43128

Был обычный будний вечер в Магнитогорске. Фил и Космос возвращались на машине домой после тяжёлой рабочей смены. Тут Космос вспомнил, что Белый дал ему задание, которое он благополучно забыл выполнить. Чтобы уберечь Космоса от гнева Саши Белого, помогите ему выполнить задание.
Даны n целых чисел a₁,a₂,...,a_n. Требуется сделать наибольший общий делитель (НОД) всех чисел массива равным 1. За одну операцию можно сделать следующее:
• Выбрать произвольный индекс в массиве 1 <= i <= n;
• Сделать a_i = gcd(a_i,i). Стоимость такой операции равна n − i + 1.
Требуется найти минимальную суммарную стоимость операций, которые нужно будет сделать, чтобы НОД чисел массива стал равен 1.
Входные данные
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит целое число t (1 <= t <= 5000) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит единственное целое число n (1 <= n <= 20) — длину массива.
Вторая строка каждого набора входных данных содержит n целых чисел a₁,a₂,...,a_n (1 <= a_i <= 10⁹) — элементы массива.
Выходные данные
Для каждого набора входных данных выведите единственное целое число — минимальную суммарную стоимость операций, которые нужно будет сделать, чтобы НОД чисел массива стал равен 1.

Примеры

№	Входные данные	Выходные данные
1	7 1 1 1 2 2 2 4 3 3 6 9 4 5 10 15 20 5 120 60 80 40 80 6 150 90 180 120 60 30	0 1 2 2 1 3 3

Замечание
В первом наборе входных данных НОД всего массива уже равен 1, поэтому операции применять не нужно.
Во втором наборе входных данных выберем i = 1. После этой операции a1 = gcd(2,1) = 1. Стоимость этой операции была равна 1.
В третьем наборе входных данных нужно будет выбрать i = 1, после этого массив a будет равен [1,4]. НОД этого массива равен 1, а суммарная стоимость равна 2.
В четвертом наборе входных данных нужно выбрать i = 2, после этого массив a будет равен [3,2,9]. НОД этого массива равен 1, а суммарная стоимость равна 2.
В шестом наборе входных данных можно выбрать i = 3, после этого массив a будет равен [120,60,1,40,80]. НОД этого массива равен 1, а суммарная стоимость равна 3.

НОД и алгоритм Евклида

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

Длинный плакат#42975

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

Входные данные
В первой строке входных данных записано целое число N, записанное на изначальном длинном плакате. Гарантируется, что в N не менее двух и не более 200 000 цифр (10 ≤ N < 10^{200 000}).
Во второй строке содержится целое число K — количество цифр, которые необходимо вырезать из плаката. Гарантируется, что K не меньше одного и строго меньше количества цифр числа N (1 ≤ K, 10^K ≤ N).
Выходные данные
Выведите максимальное число, которое может получиться на плакате после его укорачивания

Примеры

№	Входные данные	Выходные данные
1	2023 1	223

Замечание
В примере из условия на плакате записано число 2023, из него нужно вырезать одну цифру.
Максимально число, которое можно при этом получить, равно 223.

Жадный алгоритм Стек

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

Лес#42971

Миша заблудился в лесу и пытается выйти из него. Он проходит A шагов на север, затем B шагов на восток, затем C шагов на юг, D шагов на запад, после чего повторяет свои действия (снова A шагов на север, B шагов на восток, C шагов на юг, D шагов на запад и т.д.).
Оказалось, что для того, чтобы выйти из леса из его первоначальной точки, ему нужно было пройти ровно K шагов в любом из четырёх направлений, то есть первоначально Миша находится в центре квадрата со стороной 2K шагов. Определите, сколько шагов Миша сделает, прежде чем выйдет из леса (впервые окажется на границе леса).

Входные данные
Первые четыре строки входных данных содержат по одному целому положительному числу A, B, C, D — количество шагов, которое Миша делает на север, восток, юг, запад. Пятая строка входных данных содержит целое число K — расстояние от начального расположения Миши до четырёх сторон квадрата (границ леса). Все входные числа не превосходят 10⁹.

Выходные данные
Программа должна вывести одно целое число — количество шагов, которое Миша сделает до выхода из леса. Гарантируется, что входные данные таковы, что Миша когда-нибудь выйдет из леса.
Обратите внимание, что значение ответа может быть больше, чем возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C и C++, тип long в Java и C#).

Примеры

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

Замечание
На рисунке изображён пример из условия. Миша делает 1 шаг на север (вверх), 1 шаг на восток (вправо), 2 шага на юг (вниз), 3 шага на запад (влево). От начального расположения Миши до стороны квадрата — 3 шага. Первоначальное расположение Миши и точка выхода из леса обозначены синими кругами. Путь Миши обозначен жёлтой линией. Миша пройдёт 13 шагов, прежде чем впервые окажется на границе леса.

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

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

Круговой велопробег#42697

В деревне Круглая первые дома построены вдоль главной кольцевой дороги длиной M километров. Эти дома имеют номера от 1 до M. Василий ведет здоровый образ жизни и ежедневно проезжает на велосипеде K километров по этой дороге. Сегодня он начал движение от дома с номером S. Возле какого дома он сегодня закончит свой велопробег? Василий всегда двигается в сторону увеличения номеров домов.

Входные данные
Программа получает на вход три строки. В первой строке записано число M (1 <= M <= 100) - протяженность главной кольцевой дороги. Во второй строке записано число K (1 <= K <= 10⁵) - количество километров, которые проезжает Василий по этой дороге. В третьей строке записано число S (1 <= S <= M) - номер дома, от которого начал движение Василий.

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

Примеры

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

Остатки

✓ 4 916✗ 10 165400лёгкаяВойти и решать

Меняю конфеты на ноутбук#42450

Антон Б., суперспособный ученик 8 класса, обладает неудивительными математическими способностями. Побывав однажды на экскурсии в Колоколамске, он понял, что легко может написать программу, которая бы предсказывала стоимость его любимых конфет на любой промежуток дней вперед.
Используя эту программу, Антон Б. решил приобрести на все свои карманные деньги конфеты (а их у него было всего 10 рублей), затем, чуть позже, продать все купленные им конфеты. Таким образом, Антон Б. хочет заработать как можно больше денег на новый ноутбук.
Так как Антон Б. еще несовершеннолетний и один ездить в другие города не может, ему нужно понять, в какие из двух дней попросить старшего брата отвезти его в Колоколамск. Старший брат совершеннолетний и очень любит своего младшего брата, поэтому всегда готов ему помочь.
Так как Антон Б. очень торопится на кружок по информатике, он просит вас определить эти два дня в ближайшие N дней.

Входные данные
В первой строке записано число N (2 <= N <= 100000) количество дней, на которые Антон Б. делает прогноз. Вторая строка содержит N целых положительных чисел a_i(1 <= i <= N , 1 <= a_i<= 5000 ), где a_i - предсказанная стоимость конфет в i-й день.

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

Выведите два числа: первое число - номер дня, в который Антон Б. поедет покупать конфеты, второе - номер дня, в который он поедет продавать конфеты. В случае, если таких вариантов дней несколько, выведите любой из них. Если Антон Б. в итоге не сможет получить прибыль ни при каких вариантах, то выведите два нуля.

Примеры

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

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

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

Кривая дракона#42263

Сегодня мальчик Саша на уроке математики узнал про фракталы. Учитель показывал так называемую «кривую дракона». Она представляет собой геометрическую фигуру, которая строится следующим образом: на первом шаге проводится отрезок из начала координатной плоскости в точку (0; 1). Далее на каждом шаге из конца фрактала повторяется уже нарисованная часть фигуры, повернутая на 90 градусов против часовой стрелки (см. рисунок).

После уроков Саша попробовал сам изобразить «кривую дракона», и теперь он хочет знать, в какой точке координатной плоскости он закончил рисовать фрактал, проделав описанные выше N шагов. Требуется написать программу, которая по заданному числу N определяет координаты конца фрактала после выполнения N шагов.

Входные данные
Вводится одно целое число N (1 <= N <= 30).

Выходные данные
Выведите два числа через пробел - координаты конца фрактала.

Примеры

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

Арифметические алгоритмы (Теория чисел)Циклы

✓ 24✗ 40600лёгкаяВойти и решать

Последняя ненулевая факториала#42251

Для заданного натурального N найдите последнюю ненулевую цифру числа N!.

Входные данные
Программа получает на вход целое число N (0 <= N <= 10⁶).

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

Примеры

№	Входные данные	Выходные данные
1	8	2
2	10	8

Остатки теория чисел Цикл for

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

Степень#42245

Напишите программу, вычисляющую \(2^N\).

Входные данные
Программа получает на вход натуральное число N (N<=30).

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

Примеры

№	Входные данные	Выходные данные
1	4	16

Быстрое возведение в степень Цикл for

✓ 115✗ 266300лёгкаяВойти и решать

Номер числа Фибоначчи#42242

Дано натуральное число A > 1. Определите, каким по счету числом Фибоначчи оно является, то есть выведите такое число n, что f_n=A. Если A не является числом Фибоначчи, выведите число -1.

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

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

Примеры

№	Входные данные	Выходные данные
1	8	6
2	10	-1

Рекуррентные последовательности Цикл while

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

N-е число Фибоначчи#42241

Последовательность Фибоначчи определяется так: \(f_0 = 0, f_1 = 1, ..., f_n = f_{n-1}+f_{n-2}\).

По данному числу n определите n-е число Фибоначчи f_n.

Входные данные
Программа получает на вход натуральное число n.

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

Примеры

№	Входные данные	Выходные данные
1	6	8

Рекуррентные последовательности

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

Двоичный логарифм#42239

По данному натуральному числу N выведите такое наименьшее целое число k, что \(2^k >= N\).

Входные данные
Программа получает на вход натуральное число N.

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

Примеры

№	Входные данные	Выходные данные
1	10	4

Двоичная система счисления Цикл while

✓ 56✗ 168400лёгкаяВойти и решать

Точная степень двойки#42238

Дано натуральное число N. Выведите слово YES, если число N является точной степенью двойки, или слово NО в противном случае. Операцией возведения в степень пользоваться нельзя!

Входные данные
Программа получает на вход натуральное число N (N < 10⁹).

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

Примеры

№	Входные данные	Выходные данные
1	5	NO
2	32	YES
3	1	YES

Двоичная система счисления Цикл for Цикл while

✓ 12✗ 15600лёгкаяВойти и решать

Степени двойки#42237

По данному числу N распечатайте все целые степени двойки, не превосходящие N, в порядке возрастания. Операцией возведения в степень пользоваться нельзя!

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

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

Примеры

№	Входные данные	Выходные данные
1	`30`	`1 2 4 8 16`

Двоичная система счисления Цикл while

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