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

Упорядочите шарики#27053

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

Для того, чтобы упорядочить шарики перед началом следующей партии, используется следующее устройство. Это устройство состоит из головки, которая, перемещаясь над шариками, может «засасывать» и «выплевывать» шарики. Чтобы получить большее представление об этом устройстве, представьте себе пылесос, который может засасывать шарики, перемешаться в нужное место, и там, включаясь на продув в обратном направлении, шарики «выплевывать».

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

В устройство может быть одновременно засосано больше одного шарика, при этом при выплевывании шарика первым выплевывается последний засосанный шарик, затем - предпоследний и т.д. (т.е. устройство работает по принципу стека). Шарики выплевываются по одному, т.е. можно выплюнуть только один шарик, остальные оставив внутри устройства (при этом дальше можно как продолжать «выплевывать» шарики в том же или в другом месте, так и засасывать новые шарики).

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

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

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

Во входном файле задано сначала число N — количество шариков (1<= N <= 1000). Далее идет N чисел, задающих номера шариков в порядке слева направо в их текущем расположении (каждое число — от 1 до N, и каждое из чисел встречается в последовательности ровно один раз).

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

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

Комментарии к примерам тестов

1.Можно засосать, например, шарик номер 2 и выплюнуть его между 1-м и 3-м шариком.

2. Можно действовать, например, так. Сначала засосем шарик номер 1, затем – шарик номер 2. Затем переместимся в начало и перед 4-м шариком выплюнем шарик (это будет шарик номер 2). Дальше засосем шарик номер 3, и выплюнем его между шариками 2 и 4. Дальше переместимся в начало и там выплюнем шарик номер 1. Впрочем, это не единственный возможный вариант упорядочения шариков в этом примере.

Примеры

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

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

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

S.L.O.T.#27023

Вчера знаменитый певец S.L.O.T. исполнил на концерте свой лучший трек "10 марта" и множество других. Дамир ОЧЕНЬ захотел на этот концерт и уже купил билеты, как вдруг понял, что до концерта всего час, а ему нужно доехать до места проведения концерта (естественно, на трамвае).

Трамвай необходимое расстояние преодолевает за 59 минут. Будем считать, что концерт проводится на трамвайной остановке, то есть Дамир вполне на него успевает, но ему подходит только ему подходят лишь трамваи, номера которых являются перестановками от 1 до n. При этом он только что увидел, как с его остановки уезжает трамвай с номером p. Однако Дамир - великий эстет, и он хочет сесть на трамвай, номер которого равен следующей перестановке после p. Поскольку трамваи подходят к его остановке мнгновенно, на концерт любимого исполнителя он успеет в любом случае.

Вам дана последовательность из номеров трамваев, которые в ближайшем времени подойдут к остановке Дамира и Ваша задача состоит в том, чтобы сообщить порядковый номер трамвая, который подойдёт Дамиру(все номера нумеруются с единицы. то есть если на вход вам даётся 6 номеров, то их порядковые номера идут в таком порядке: 1, 2, 3, 4, 5, 6)

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

В первой строке вводится число n - количество чисел в перестановке в номере трамвая

Во второй строке ЧЕРЕЗ ПРОБЕЛ!! вводится n чисел, которые задают p - номер трамвая, который только что отошёл от остановки Дамира

Третья строка содержит k - количество трамваев, которые скоро подъедут к остановке Дамира (гарантируется, что один из трамваев подходит Дамиру)

Далее идут k строк, которые содержат по n чисел через пробел - номера трамваев

(n <= 7, k <= 5)

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

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

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

Комбинаторика Перестановки

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

Сложные пароли#27022

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

Ввод:
в первой строке вводится n - количество слов и наборов цифр, в следующих n строках вводятся слова / наборы цифр. (n<20, длина строк не превышает 20).

Вывод:
Необходимо вывести все возможные перестановки слов и наборов цифр, если это невозможно, вывести "unreal".

Ввод	Вывод
3 cat 123 215	123cat215 215cat123

(с) Вероника Пеутина

Комбинаторика Простые задачи на перебор реализация

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

"Гробы" из 43-го#27021

На уроке информатике Антон Витальевич задал придумать задачи на перестановки. Ребята в 43 кабинете очень обрадовались этому заданию и решили придумать n гробов для своего класса. Сложность каждой задачи – это число от 1 до n. Ребята хотят узнать насколько, они «загробили» контест, коэффициент «загробленности» (КЗ) считается, как номер перестановки, которую подали на ввод. Ребята радуются, если КЗ будет больше, чем сумма разниц между двумя подряд идущими элементами в данной перестановки по модулю умноженная на количество гробов в контесте.

Вывести “positumque loculum” (гроб), если ребята будут рады своей работе, иначе вывести наименьшую подходящую перестановку (элементы разделять пробелами), номер которой |КЗ – номер текущей| <= k, а если это невозможно, то вывести “easily”.

В первой строке вводится количество гробов в контесте n <= 7 и k, 0 <= k <= n!

Во второй строке вводится сама перестановка.

Ввод	Вывод
7 2518 7 5 2 4 1 6 3	positumque loculum
4 1 3 2 4 1	easily
4 2 3 2 4 1	3 4 2 1

Приятного решения ♥♥
(с) Елизавета Ястреба

Генерация по номеру Комбинаторика

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

Номер перестановки#27020

Вам даны две строки - S и одна из её перестановок - P. Требуется найти номер строки P среди всех перестановок строки S, отсортированных по убыванию в лексикографическом порядке.

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

На вход подаются две строки - S и P (1 =< |S| <= 9). В строках содержатся только строчные буквы латинского алфавита.

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

Выведите одно число - номер перестановки P.

Ввод	Вывод
abcd dcba	1
abc abc	6

(с) Ахмад Ибрахим

Комбинаторика Перестановки

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

Алгоритм#27018

Реализуйте алгоритм, представленный блок-схемой, на одном из языков программирования.

В первой строке ввода содержится одно целое число N (2 ≤ N ≤ 10⁹).

Каждое число, которое выводится в алгоритме, вывести на отдельной строке.

Ввод	Вывод
12	2 2 3

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

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

Курьер#26986

Курьеру Васе поручили доставить n посылок. Вася начинает работать в первый день и каждый день может доставить ровно одну посылку. Про каждую посылку известен последний день, когда ее можно доставить d_i, и штраф w_i, который придется заплатить, если посылка не будет доставлена в срок.

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

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

Формат ввода

В первой строке дано единственное натуральное число n (1 n 200 000) — количество посылок.

Затем следует n строк, в каждой из которых содержится по два числа d_i и w_i (1 d_i 200 000, 1 w_i 200 000) — последний день, когда можно доставить посылку без штрафа и стоимость опоздания для i-й посылки.

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

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

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

Пример

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

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

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

Максимальное число делителей#26984

Напишите программу, которая по заданному числу n находит такое число от 1 до n, включительно, что оно имеет максимальное число положительных целых делителей. Например, если n = 15, то ответом на задачу будет число — 12, так как у него 6 делителей: 1, 2, 3, 4, 6 и 12.

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

Дано одно натуральное число n (1 ≤ n ≤ 100 000).

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

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

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

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

Пути в музее#26978

Болик добрался до музея, здание которого представляет собой квадрат N × N, разбитый на N² равных квадратных залов. Вход в музей расположен в левом нижнем зале, а Лёлик ждет Болика в правом верхнем. Из каждого зала можно пройти в соседний с ним зал (два зала называются соседними, если у них есть общая стена).

Теперь Болик хочет определить сколько возможных путей до Лёлика у него есть. Конечно, его интересуют только пути кратчайшей длины.

Формат ввода

На вход подается одно натуральное число N (2 ≤ N ≤ 22).

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

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

Пример

Ввод	Вывод
3	6

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

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

Числа Фибоначчи#25962

Числа Фибоначчи определяются рекуррентной формулой:

\(F_0 = F_1 = 1, \\ F_n = F_{n-1} + F_{n-2}, \text{ при}\ n \ge 2\)

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

В единственной строке входных данных записано натуральное число n (\(1<=n<=45\)).

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

Вывести одно n-е число Фибоначчи - F_n.

Примеры

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

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

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

Двоичный поиск#25959

Реализуйте алгоритм бинарного поиска.

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

В первой строке входных данных содержатся натуральные числа N и K (\(0<N,\ K <= 100000\)). Во второй строке задаются N элементов первого массива, отсортированного по возрастанию. В третьей строке – K элементов второго массива.
Элементы обоих массивов - целые числа, каждое из которых по модулю не превосходит \(10^9\).

Формат выходных данных
Требуется для каждого из K чисел вывести в отдельную строку "YES", если это число встречается в первом массиве, и "NO" в противном случае.

Алгоритмы поиска Бинарный поиск в массиве

✓ 1 523✗ 2 610400лёгкаяВойти и решать

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

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

Известно, что организации необходимо выполнить n задач, пронумерованных натуральными числами от одного до n. На выполнение каждой задачи требуется ровно один день, и в каждый день может быть выполнена только одна задача. Таким образом, на выполнение всех задач потребуется n дней, а расписание выполнения задач выглядит как назначение определенного дня на выполнение каждой задачи. Для каждой задачи известно также число a_i — номер дня, ранее которого не может быть начато выполнение этой задачи.

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

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

В первой строке находится натуральное число n (1 ≤ n ≤ 8) — количество задач, которые необходимо выполнить.

Следующая строка содержит n натуральных чисел a_i (1 ≤ a_i ≤ n) — для каждой работы номер дня, ранее которого не может быть начато выполнение этой задачи. Числа отделены друг от друга одним пробелом.

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

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

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

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

Комбинаторика Теория расписаний

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

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

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

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

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

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

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

В первой строке находится натуральное число n (2 ≤ n ≤ 100) — количество сотрудников в фирме.

Следующая строка содержит n-1 натуральное число — номера непосредственных начальников сотрудников с номерами от 2 до n в соответствующем порядке. Числа отделены друг от друга одним пробелом. Гарантируется, что номер непосредственного начальника очередного сотрудника меньше номера самого сотрудника.

Следующая строка содержит одно натуральное число x (1 ≤ x ≤ n) — номер отправляемого в командировку сотрудника.

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

Выведите одно число — количество сотрудников, остающихся на своих рабочих местах после выполнения описанной операции.

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

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

Деревья Поиск компонент связности

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

Воздушные потоки#24765

Колобок ушёл от бабушки и поехал путешествовать. Неожиданно для себя он забрёл в страну Ивэнлэнд. Первые трудности встали на его пути: Колобка и вход в страну отделял огромный ров с водой, которая, как известно, не очень хорошо влияет на нашего героя. К счастью, повсюду рас- положены воздушные потоки, которые могли поднимать того, кто на них встает, на определённую высоту. Страна не просто так названа Ивэнлэнд, поэтому все высоты, на которые могут поднять героя воздушные потоки — это чётные числа.

Представим воздушные потоки как массив h[1..n] из n натуральных чисел — высот потоков. Для каждого 1 ≤ i ≤ n посчитаем G[i] — индекс ближайшего элемента слева, строго большего h[i]. Более формально, g[i] = max{j | j < i и h[j] > h[i]}. Если i = 1 или до h[i] нет ни одного элемента больше него, то G[i] считается равным 0.

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

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

Помогите Колобку сделать оптимальное изменение, которое позволит добиться, чтобы сумма S(h), описанная выше, после проделанного действия была минимальна.

Формат входного файла
В первой строке входного файла даны числа n, m (1 ≤ n ≤ 10⁵ , 1 ≤ m ≤ 10⁹ ) — количество воздушных потоков и максимальное значение, на которое можно увеличить высоту одного из них. Во второй строке даны высоты воздушных потоков h[i] (1 ≤ h[i] ≤ 10⁹ ). Гарантируется, что все высоты — чётные числа.

Формат выходного файла
В единственной строке выходного файла выведите одно целое число — минимальную искомую сумму.

Ввод	Вывод
3 100 4 2 6	4
3 2 4 2 6	5
3 10 2 2 2	4

Деревья Наименьший общий предок Разреженные таблицы (sparse table)Структуры данных

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

Постройка забора#24762

После побега Колобка Дед и Баба решили построить забор вокруг своего дома, чтобы не допустить повторения истории.

Забор представляет собой многоугольник ненулевой площади, сторонами которого являются доски. Пилить или ломать доски нельзя. Например, из трех досок с длинами 10, 11 и 12 можно построить забор, а из четырех досок с длинами 100, 1, 2 и 3 — нельзя.

У Деда нашлось целых n досок, поэтому они с Бабой задались вопросом: а сколько различных способов выбрать несколько досок из имеющихся, чтобы из них затем можно было построить забор? Способы считаются различными, если существует доска, которая используется в одном из них, но не используется в другом.

Пожилым людям надо помогать, так что вам не составит труда решить для них эту задачу! Количество способов может быть довольно большим, поэтому выведите остаток от деления этого количества на число 10⁹ + 7.

Формат входного файла
В первой строке входного файла находится одно натуральное число n (1 ≤ n ≤ 4000) — количе- ство досок. Во второй строке дано n чисел li (1 ≤ l_i ≤ 4000) — длины досок.

Формат выходного файла
В выходной файл выведите одно число — количество способов выбрать доски для постройки забора, взятое по модулю 10⁹ + 7.

Ввод	Вывод
3 10 11 12	1
4 100 1 2 3	0
4 5 5 5 5	5

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

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

Путь в никуда#24761

Колобку снится странный сон.
В нём Колобок находится на клетчатом поле размера n × m в клетке с координатами (x, y).
Изначально Колобок смотрит вдоль положительного направления оси X. Затем он начинает идти по полю со следующей закономерностью:
• Пройти на одну клетку вперед. Повернуть на 90^oвправо.
• Пройти на одну клетку вперед. Повернуть на 90^o вправо.
• Пройти на две клетки вперед. Повернуть на 90^o вправо.
• Пройти на две клетки вперед. Повернуть на 90^o вправо.
• Пройти на три клетки вперед. Повернуть на 90^o вправо.
• Пройти на три клетки вперед. Повернуть на 90^o вправо.
• Пройти на четыре клетки вперед. Повернуть на 90^o вправо.
• И так далее...

Движение продолжается до тех пор, пока Колобок не выйдет за границы поля. После этого Колобок просыпается.

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

Формат входного файла
В первой строке входного файла находятся два натуральных числа n, m (1 ≤ n, m ≤ 10⁹ ) — размеры доски вдоль оси X и оси Y соответственно. Во второй строке находятся два натуральных числа x, y (1 ≤ x ≤ n; 1 ≤ y ≤ m) — координаты стартовой позиции колобка.

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

Вывод	Ввод
7 6 3 4	36
2 2 1 1	2
2 2 1 2	4

Комментарий
На рисунке наглядно показан первый пример.

Бинарный поиск Деревья Префиксные суммы(минимумы, ...)Разреженные таблицы (sparse table)Структуры данных

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

Тяжелая, вариант-1#24759

Известно, что организации необходимо выполнить n задач, пронумерованных натуральными числами от одного до n. На выполнение каждой задачи требуется ровно один день, и в каждый день может быть выполнена только одна задача. Таким образом, на выполнение всех задач потребуется n дней, а расписание выполнения задач выглядит как назначение определенного дня на выполнение каждой задачи. Для каждой задачи известно также число a_i — номер дня, не позднее которого эта задача должна быть выполнена.

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

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

В первой строке находится натуральное число n (1 ≤ n ≤ 8) — количество задач, которые необходимо выполнить.

Следующая строка содержит n натуральных чисел a_i (1 ≤ a_i ≤ n) — для каждой работы номер дня, не позднее которого она должна быть выполнена. Числа отделены друг от друга одним пробелом.

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

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

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

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

Комбинаторика Теория расписаний

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

Легкая, вариант-1#24758

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

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

В первой строке находится натуральное число n (2 ≤ n ≤ 100) — количество сотрудников в фирме.

Следующая строка содержит одно натуральное число x (1 ≤ x ≤ n) — номер отправляемого в командировку сотрудника.

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

выведите одно число — количество сотрудников, отправляющихся в командировку после выполнения описанной операции.

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

Ввод	Вывод
9 1 2 1 4 4 2 7 8 2	5

Деревья Поиск компонент связности

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

Топологическая сортировка#24753

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

Входные данные: В первой строке содержатся два натуральных числа n и m (1≤n≤10⁵, 1≤m≤10⁵) — количество вершин и рёбер в графе соответственно. Далее в m строках перечислены рёбра графа. Каждое ребро задаётся парой чисел — номерами начальной и конечной вершин соответственно (нумерация вершин начинается с 1).

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

Примеры

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

Обход в глубину Топологическая сортировка

✓ 726✗ 1 854600лёгкаяВойти и решать

Тяжелая, вариант-1#24736

В школьную столовую пришли n учеников разных классов и выпили суммарно k стаканов компота. Кассирша тетя Таня хорошо знает всех учеников, поэтому про i-го пришедшего школьника она знает число a_i — минимальное количество стаканов компота, которое мог выпить этот школьник. Также она знает, i-й школьник выпьет явно не больше a_i+x стаканов компота. Теперь ей стало интересно: а какое максимальное количество стаканов компота гарантированно выпил один из школьников? То есть она хочет найти такое максимальное число m, что при любом корректном распределении количества выпитых стаканов компота между школьниками, школьник, выпивший максимальное количество стаканов компота, выпил их не менее чем m штук. Помогите ей с этой задачей.

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

В первой строке входного файла input.txt находятся три натуральных числа n, k, x (1 ≤ n ≤ 100; 1 ≤ k ≤ 2 · 10⁴; 1 ≤ x ≤ 100) — количество школьников, пришедших в столовую, количество стаканов компота, выпитого ими, и максимальное количество стаканов, которое каждый школьник мог выпить сверх своего минимального количества, соответственно.
В следующей строке находятся n целых чисел a_i (1 ≤ a_i ≤ 100), разделенных пробелами, — минимальное количество стаканов компота, которое выпил i-й школьник.
Гарантируется, что входные данные корректны.

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

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

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

Ввод	Вывод	Комментарий
3 4 1 1 1 2	2	Так как всего было выпито 4 стакана компота, а школьники выпили хотя бы 1, 1 и 2 стакана соответственно, первый школьник выпил ровно 1 стакан, второй — ровно 1 стакан, третий — ровно 2 стакана. Следовательно, ответ равен 2.
3 6 1 1 1 2	2	Каждый из школьников мог выпить по 2 стакана компота. Значит, ответ 3 гарантировать нельзя. Следовательно, ответ равен 2.
3 7 1 1 1 2	3	Так как всего выпито 7 стаканов компота, хотя бы один школьник выпил 3 стакана. Ответ 4, очевидно, недостижим. Следовательно, ответ равен 3.
3 12 2 1 2 4	5	Первый школьник выпил хотя бы 1 стакан и не более 3, второй — хотя бы 2 и не более 4, третий — хотя бы 4 и не более 6. Невозможно выпить 12 стаканов компота, если третий школьник выпьет ≤ 4 стакана, следовательно, ответ равен 5.

Жадный алгоритм Задачи на моделирование

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