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

Loan Repayment#90112

Фермер Джон должен Беси \(N\) галлонов молока (\(1\le N\le 10^{12}\)). Он должен вернуть ей молоко в течение \(K\) дней. Однако он не хочет отдавать молоко слишком быстро. С другой стороны, он должен показывать прогресс в возвращении долга. Поэтому он должен возвращать Беси не менее \(M\) галлонов молока (\(1\le M\le 10^{12}\)) каждый день.

ФД собирается делать так. Он выбирает положительное целое число \(X\). А затем повторяет следующую процедуру каждый день:

Предположим, что ФД уже отдал Беси \(G\) галлонов молока, он вычисляет \(\frac{N-G}{X}\) с округлением вверх. Назовём это число \(Y\).
Если \(Y\) меньше чем \(M\), то устанавливает \(Y\) равным \(M\).
Даёт Беси \(Y\) галлонов молока.

Определите максимальное \(X\) такое, что если ФД будет следовать этой процедуре, то ФД отдаст Беси не менее \(N\) галлонов молока после \(K\) дней (\(1\le K\le 10^{12}\)).

ОЦЕНИВАНИЕ:

Тесты 2-4 удовлетворяют ограничению \(K\le 10^5.\)
Тесты 5-11 не имеют дополнительных ограничений.

ФОРМАТ ВВОДА (файл loan.in):

Единственная строка ввода содержит три разделённых пробелом целых положительных числа \(N\), \(K\), \(M\) удовлетворяющих \(K\cdot M<N\).

ФОРМАТ ВЫВОДА (файл loan.out):

Выведите наибольшее положительное целое число \(X\) такое, что ФД отдаст Беси не менее \(N\) галлонов молока используя описанную выше процедуру.

Бинарный поиск по ответу Задачи на моделирование

—Войти и решать

Where Am I_#90038

Фермер Джон идёт по дорожке и думает, что не может потеряться.

Вдоль дороги имеется \(N\) ферм (\(1 \leq N \leq 100\)). На фермах нет номеров, поэтому ФД тяжело ориентироваться. Зато на каждой ферме имеется цветной почтовый ящик со стороны дороги. поэтому ФД надеется, что если он посмотрит на цвета ближайших почтовых ящиков, он сможет однозначно определить, где он находится.

Каждый цвет почтового ящика обозначается буквой в интервале A..Z, таким образом, последовательность \(N\) почтовых ящиков вдоль дороги представляется строкой длины \(N\), содержащей символы в интервале A..Z. Некоторые почтовые ящики могут иметь одинаковые цвета. ФД хочет узнать минимальное число \(K\) такое, что если он посмотрит на любую последовательность из \(K\) последовательных ящиков, он уникально определит местоположение этой последовательности на дороге.

Например, предположим, что последовательность ящиков вдоль дороги есть 'ABCDABC'. ФД не может выбрать \(K=3\), поскольку если он увидит 'ABC', то имеется два расположения такой строки вдоль дороги. Минимальное значение \(K\), которое работает, \(K=4\), поскольку любые последовательные 4 символа уникально определяют его позицию вдоль дороги.

ФОРМАТ ВВОДА (файл whereami.in):

Первая строка ввода содержит \(N\), вторая строка содержит строку из \(N\) символов, каждый в интервале A..Z.

ФОРМАТ ВЫВОДА (файл whereami.out):

Выведите строку, содержащую одно целое число, указывающее минимальное значение \(K\), которое решает задачу ФД.

Поиск подстроки в строке

—Войти и решать

Milking Order#90027

\(N\) коров (\(1 \leq N \leq 10^5\)), фермера Джона, пронумерованных \(1 \ldots N\), разработали социальную иерархию, в соответствии с которой ФД доит их каждое утро.

ФД сделал \(M\) наблюдений об этой структуре (\(1 \leq M \leq 50,000\)). Каждое наблюдение - упорядоченный список некоторых из его коров, указывающий что их нужно доить именно в таком порядке. Например список 2 5 1 означает, он должен подоить корову 2, некоторое время спустя - корову 5 и некоторое время после - корову 1.

Наблюдения ФД приоритезированы, поэтому его цель - максимизировать значение \(X\) так, чтобы выполнились условия первых \(X\) наблюдений. Если несколько порядков дойки могут удовлетворять \(X\) наблюдениям, он выбирает тот, в котором корова с меньшим номером доится раньше. Иными словами, если несколько порядков дойки удовлетворяют этим условиям, ФД выбирает лексикографически наименьший. Порядок \(x\) является лексикографически меньшим, чем порядок \(y\), если для некоторого \(j\), , \(x_i = y_i\) для всех \(i < j\) и \(x_j < y_j\) (другими словами два порядка идентичны до некоторой точки, в которой \(x\) меньше чем \(y\)).

Помогите ФД определить наилучший порядок дойки его коров.

ФОРМАТ ВВОДА (файл milkorder.in):

Первая строка содержит числа \(N\) и \(M\). Каждая из следующих \(M\) строк описывает одно наблюдение. Строка \(i+1\) описывает наблюдение \(i\) и начинается с количества коров \(m_i\) в этом наблюдении, за которым следует список из \(m_i\) целых чисел, определяющих порядок коров в этом наблюдении. Сумма \(m_i\) не превышает \(200,000\).

ФОРМАТ ВЫВОДА (файл milkorder.out):

Выведите \(N\) разделённых пробелом целых чисел дающих перестановку чисел of \(1 \ldots N\), содержащую порядок в котором ФД должен доить своих коров.

Бинарный поиск по ответу графы Топологическая сортировка

—Войти и решать

Convention#89997

На ферме Джона состоится съезд по поеданию травы.

Коровы со всего мира прибывают в местный аэропорт, чтобы посетить съезд и поесть траву. А именно \(N\) (\(1 \leq N \leq 10^5\)) коров прибывают в аэропорт, и корова \(i\) прибывает в момент времени \(t_i\) (\(0 \leq t_i \leq 10^9\)). ФД организовал \(M\) (\(1 \leq M \leq 10^5\)) автобусов для транспортировки коров из аэропорта. Каждый автобус может вместить до \(C\) (\(1 \leq C \leq N\)) коров. ФД ждёт вместе с автобусами в аэропорту и собирается распределить прибывающих коров по автобусам. Автобус убывает из аэропорта в момент, когда прибывает последняя корова. ФД хочет, чтобы прибывающие коровы не ждали в аэропорту слишком долго. Каково наименьшее значение максимального времени ожидания из всех коров, если ФД оптимально назначит их по автобусам. Время ожидания коровы есть разность между временем её прибытия и временем отправления автобуса, в который она распределена.

Гарантируется, что \(MC \geq N\).

ФОРМАТ ВВОДА (файл convention.in):

Первая строка содержит три разделённых одиночными пробелами целых числа \(N\), \(M\), \(C\). Следующая строка содержит \(N\) разделённых одиночными пробелами целых чисел, представляющих время прибытия каждой коровы.

ФОРМАТ ВЫВОДА (файл convention.out):

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

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

—Войти и решать

Haybale Feast#89981

Фермер Джон готовит деликатесную еду для своих коров. В его амбаре имеется \(N\) стогов сена (\(1 \le N \le 100,000\)). \(i\)-ый стог имеет опредённый вкус \(F_i\) (\(1 \le F_i \le 10^9\)) и определённую пряность \(S_i\) (\(1 \le S_i \le 10^9\)).

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

ФД хочет определить минимальную пряность, кторую можно достичь, чтобы вкус был не менее \(M\) (\(1 \le M \le 10^{18}\)).

ФОРМАТ ВВОДА (файл hayfeast.in):

Первая строка содержит целые числа \(N\) и \(M\), количество стогов сена и минимальный вкус, которого нужно достичь, соответственно. Следующие \(N\) строк описывают \(N\) стогов сена парой чисел в строке - первое вкус \(F\), а второе - пряность \(S\).

ФОРМАТ ВЫВОДА (файл hayfeast.out):

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

"Два указателя"Жадный алгоритм Префиксные суммы(минимумы, ...)

—Войти и решать

Diamond Collector#89963

Беси собрала \(N\) алмазов (\(N \leq 1000\)) различных размеров. И хочет разместить их специальным образом в амбаре.

Она не будет включать в размещение два алмаза, если их размеры отличаются более чем на \(K\). По данному \(K\) определите максимальное количество алмазов, которые Беси разместит в амбаре.

ФОРМАТ ВВОДА (файл diamond.in):

Первая строка ввода содержит \(N\) и \(K\) (\(0 \leq K \leq 10,000\)). Каждая из следующих \(N\) строк содержит целое число, определяющее размер одного из алмазов. Все размеры - положительные числа, не превышающие \(10,000\)

ФОРМАТ ВЫВОДА (файл diamond.out):

Выведите одно положительное целое число - максимальное количество алмазов, которое Беси сможет показать.

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

—Войти и решать

Sabotage#89938

Фермер Пауль решил саботировать доильное оборудование Фермера Джона. Доильное оборудование составляет ряд из N (3 <= N <= 100,000) доильных машин, где i-ая машина производит M_i единиц молока. ФП планирует отсоединить непрерывный блок этих машин от i-ой до j-ой (2 <= i <= j <= N-1). Заметим, что ФД не собирается отключать первую и последнюю машины, поскольку это очень заметно и легко обнаружить. Цель ФП – минимизировать среднее производство молока оставшимися машинами.
Пожалуйста, помогите ФД определить минимальное среднее значение производства молока оставшимися машинами в случае оптимальных действий ФП.
PROBLEM NAME: sabotage
Формат входных данных
* Строки 1: Целое число N.
* Строки 2..1+N: Строка i+1 содержит M_i.
Формат выходных данных
* Строка 1: Минимально возможное среднее, которого может достичь ФП, округлённое до 3 цифр после десятичной точки и с выводом 3 цифр после десятичной точки.
Примечание
Оптимальное решение – удалить машины 7 т 8 оставив 5 1 2, среднее которых равно 8/3.

Бинарный поиск по ответу

—Войти и решать

Cross Country Skiing#89932

Лыжная трасса описана решёткой из M x N высот (1 <= M,N <= 500), каждая из высот в диапазоне 0 .. 1,000,000,000.
Некоторые из этих ячеек обозначены как точки маршрута гонки. Организаторы хотят назначить маршруту рейтинг трудности D так, чтобы корова могла попасть в любую точки маршрута из любой другой точки маршрута, последовательно перемещаясь между соседними ячейками, абсолютная разность высот которых не превышает D. Две ячейки считаются соседними, если они граничат по стороне (в направлении на север, юг, запад или восток одна от другой). Рейтинг трудности маршрута это минимальное значение D такое, что все точки маршрута взаимно достижимы при выполнении вышеописанного требования.
PROBLEM NAME: ccski
Формат входных данных
* Строка 1: Целые числа M и N.
* Строки 2..1+M: Каждая из этих M строк содержит N целых высот.
* Строки 2+M..1+2M: Каждая из этих M строк содержит N величин 0 или 1, 1 указывает, что данная высота – точка маршрута гонки.

Формат выходных данных
* Строка 1: Рейтинг трудности маршрута (минимальное значение D такое, что все точки маршрута взаимно достижимы)
Примечание
Если D = 21, то все 3 точки маршрута взаимно достижимы. Если D<21 верхняя правая точка не достижимы из других двух.

Бинарный поиск по ответу графы Обход в ширину

—Войти и решать

Cow Lineup#89882

N коров (1 <= N <= 100,000) Фермера Джона выстроились в ряд. Каждая корова идентифицирована числом в диапазоне 0...1,000,000,000; которое обозначено B(i). Множество коров могут иметь один и тот же идентификатор.
ФД думает, что ряд коров будет впечатлять больше, если бы там был большой непрерывный участок, на котором все коровы имеют одинаковый идентификатор. Для того чтиобы создать такой участок, ФД выбирает до K идентификаторов и удаляет из своего ряда всех коров имеющих эти идентификаторы.
Помогите ФД вычислить длину наиблоьшего последовательного блока коров с одним и тем же идентификатором, после такого удаления.

PROBLEM NAME: lineup
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа: N и K.
* Строки 2..1+N: Строка i+1 содержит идентификатор B(i).
Формат выходных данных
* строка 1: Размер наибольшего непрерывного блока коров с одним идентификатором, который может создать ФД.
Примечание
Удалив всех коров с идентификатором 3, ФД получит ряд: 2, 7, 7, 7, 7, 5, 7. Имеется наибольший непрерывный участок из четырех чисел 7.

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

—Войти и решать

Tractor#89878

Одно из полей Фермера Джона весьма холмисто. И он хочет купить новый трактор для работы на этом поле. Поле описывается решеткой из N x N (1 <= N <= 500) неотрицательных целых высот ячеек. Трактор может перемещаться из ячейки в соседнюю (на один шаг на север, юг, запад или восток), с разницей их высот D ровно за D единиц денег.
ФД хочет заплатить достаточно, так чтобы его трактор, начиная с некоторой ячейки поля мог посетить как минимум половину ячеек поля. Если число ячеек в поле - нечетное, то половина, округленная вверх.
Определите минимальную стоимость покупки трактора способного выполнить эту задачу.

PROBLEM NAME: tractor
Формат входных данных
* Строка 1: Значение N.
* Строки 2..1+N: Каждая строка содержит N разделенных одиночными пробелами неотрицательных целых чисел (каждое не более миллиона), определяющих строку поля ФД.
Формат выходных данных
* Line 1: Минимальная стоимость трактора, который способен объехать не менее половины этого поля.
Примечание
Трактор стоимостью 3 способен перемещаться из ячейки с высотой 0 в ячейку с высотой 3. Поэтому он может посетить все ячейки с высотами 0 и 3. Вместе они представляют не менее половины фермы.

Бинарный поиск по ответу Обход в ширину Поиск компонент связности

—Войти и решать

Partitioning the Farm#89873

Ферма Джона разделена на N x N квадратов пастбищ (2<=N<=15). Снаружи есть изгородь, но между пастбищами коровы могут переходить свободно.
ФД решил построить изгороди, чтобы отделить коров друг от друга. Каждая изгородь может быть горизонтальной или вертикальной через всю ферму, и изгороди не могут проходить через пастбища. По финансовым соображениям ФД может построить не более чем K изгородей (1 <= K <= 2N - 2).
ФД хочет построить изгороди так, чтобы минимизировать размер наибольшей из получившихся в результате групп коров (две коровы находятся в одной группе, если они могут посетить друг друга, не пересекая никакую изгородь).
По заданным количествам коров на пастбищах, вычислите размер наибольшей группы коров, если ФД построит изгороди оптимально.

PROBLEM NAME: partition
Формат входных данных
* Строка 1: Два целых числа, N and K
* Строки 2..1+N: Имеется N чисел на каждой строке, описывающих количества коров в каждом пастбище одной строки фермы. На каждом пастбище не менее 0 и не более 1000 коров.

Формат выходных данных
* Строка 1: Минимально возможный размер наибольшей группы коров.
Примечание
ФД должен построить изгороди между колонками 2 и 3 и между строками 2 и 3. В результате получится 4 группы по 4 коровы в каждой.

Бинарный поиск по ответу жадные алгоритмы Задачи на моделирование

—Войти и решать

Cow Baseball#89861

N (3 <= N <= 1000) коров Фермера Джона стоят в ряд, каждая в различной позиции на числовой прямой. Они бросают друг другу мяч по кругу в порядке подготовки к важной игре с коровами с соседней фермы.
ФД заметил, что группа из 3 коров (X,Y,Z) делает два успешных броска. Корова X бросает мяч вправо от себя корове Y, а затем корова Y бросает Мяч вправо от себя корове Z. ФД заметил также, что второй бросок получается на расстояние не менее чем первый бросок и не более чем в два раза превышает первый бросок. Посчитайте количество возможных троек коров, которые ФД мог наблюдать.
PROBLEM NAME: baseball
Формат входных данных
* Строка 1: Количество коров, N.
* Строки 2..1+N: Каждая строка содержит целую координату одной коровы (целое число в диапазоне 0..100,000,000).
Формат выходных данных
* Строка 1: Количество троек коров (X,Y,Z), где Y справа от X, а Z справа от Y и расстояние от Y до Z находится между XY и 2XY (включительно), где XY представляет расстояние от X до Y.
Примечание
Три возможных тройки: 1-3-7, 1-4-7, 1-4-10, 4-7-10.

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

—Войти и решать

Flowerpot#89839

Фермер Джон нуждается в Вашей помощи в организации поливки. Вам даны координаты N поливателей (1 <= N <= 100,000) на декартовой плоскости, где y представляет высоту поливателя. А x - его местоположение на прямой.

Каждая капля воды падает вертикально (по направлению к оси x) со скоростью 1 единица в секунду. Вы должны разместить клумбу (шириной W) с цветами так, чтобы разница во времени, когда первая капля упадет на клумбу и когда последняя капля упадет на клумбу была не менее некоторой величины D. Капля, которая попадает на границу клумбы, считается попавшей на клумбу.
Вам даны значения D, а также местоположения и высоты поливателей. Вычислите минимально возможную величину W.
PROBLEM NAME: fpot
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа N и D. (1 <= D <=1,000,000) * Строки 2..1+N: Строка i+1 содержит разделенные пробелом координаты (x,y) поливателя i, все величины в интервале 0...1,000,000.
Формат выходных данных
* Строка 1: Одно целое число, минимально-возможную ширину клумбы. Выведите -1, если невозможно построить клумбу, которая получала бы воду в течение не менее D единиц времени
Примечание
Клумба шириной 2 возможна, если разместить ее с x от 4 до 6. Тогда она будет получать капли с поливателей #1 и #3, втечение времени 10-3 = 7.

Бинарный поиск по ответу Сортировка событий

—Войти и решать

Cow Lineup#89804

Problem 2: Cow Lineup [Brian Dean]
Фермер Джон нанял профессионального фотографа, чтобы сфотографировать некоторых из своих коров. Поскольку у него есть коровы разных пород, он хочет иметь фото как минимум одной коровы каждой породы.
N коров ФД выстроены в ряд (позиция каждой указывается x-координатой) и целочисленным номером породы. ФД планирует сделать фотографию непрерывного участка коров. Стоимость фотографии равна ее размеру – то есть разностью между максимальной и минимальной x-координатами коров, представленных на фотографии.
Помогите ФД вычислить минимальную стоимость фотографии, в которой находится по крайней мере одна корова каждой породы.
PROBLEM NAME: lineup
Формат входных данных
* Строка 1: количество коров, N (1 <= N <= 50,000).
* Строки 2..1+N: Каждая строка содержит два числа, разделенных одиночным пробелом, указывающих x-координату и номер породы одной коровы. Оба числа не превосходят миллиард.
Формат выходных данных
* Строка 1: Минимальную стоимость фотографии, содержащей не менее одной коровы каждой породы.
Примечание
Диапазон от x=22 до x=26 (длиной 4) содержит коровы всех пород (1,3,7).

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

—Войти и решать

Moo Sick#89799

Problem 3: Moo Sick [Rob Seay]
Каждый знает, что коровы любят слушать музыку. Великий композитор Мууцарт однажды открыл, некоторые последовательности нот действуют на коров угнетающе. Поэтому их нужно избегать во всех композициях для коров.
Фермер Джон, не знакомый с этим фактом, решил проигрывать свою любимую песню через громкоговорители в амбаре. Ваша задача – определить все угнетающие последовательности нот в его песне, чтобы оценить, насколько она вредна для коров.
Песня, которую озвучивает ФД, представляет собой последовательность из N нот, каждая в диапазоне от 1 до 88. Угнетающая последовательность состоит из С (1<=C<=10) различных нот, также целых чисел от 1 до 88. Однако, если ноты транспонированы (увеличены или уменьшены на одну и ту же величину), или переупорядочены, то эта последовательность нот все равно остается угнетающей. Например, если «4 6 7» - угнетающая последовательность нот, то последовательности «3 5 6» (транспонирована на -1), «6 8 9» (транспонирована на +2), «6 4 7» (переупорядочена), «5 3 6» (транспонирована и переупорядочена) , также являются угнетающими.
Таким образом, угнетающей последовательностью нот являются C подряд идущих нот, удовлетворяющих вышеописанному критерию. Поэтому она однозначно определяется своим стартовым положением в песне. Определите стартовое положение всех угнетающих последовательностей.
PROBLEM NAME: moosick
Формат входных данных
* Строка 1: Одно целое число: N.
* Строки 2..1+N: N нот в песне ФД, по одной ноте на строке.
* Строка 2+N: Одно целое число: C.
* Строки 3+N..2+N+C: C нот определяющих угнетающую последовательность. Все транспозиции и переупорядочивания также угнетающие последовательности.

Формат выходных данных
* Строка 1: Количество, K, угнетающих последовательностей, которые есть в песне ФД. Заметим, что различные экземпляры угнетающих последовтельностей могут перекрываться друг с другом.
* Строки 2..1+K: Каждая строка указывает начальную позицию угнетающей последовательности (1 – первая нота в песне ФД, N - последняя). Эти начальные позиции должны указываться в порядке возрастания.
Примечание
Две угнетающих последовательности встретились в песне ФД и они перекрываются в одной ноте. Первая – 8,5,7 (транспонирована на 1 и переупорядочена), начинается с позиции 2, а вторая 7,9,10 (транспонирована на 3) , начинается с позиции 4.

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

—Войти и решать

Выбор участка - 1 (24-25)#89300

Маша хочет построить дачу на одной приглянувшейся ей улице. Эта улица имеет длину n, то есть состоит из n одинаковых идущих подряд участков. На каждом участке указан уровень шума от 1 до 9 (где 1 — тишина, 9 — очень шумно).

Маша хочет найти участок с уровнем шума ровно 1 (тихий участок), который находится максимально далеко от шумных участков. Шумным считается участок с уровнем шума 7 или больше.

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

Если таких участков несколько, выбрать участок с наименьшим номером.

Гарантируется, что есть хотя бы один тихий участок (уровень шума 1) и хотя бы один шумный участок (уровень шума ≥ 7).

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

В первой строке натуральное число n (1 ≤ n ≤ 6 000 000)
Во второй строке n чисел от 1 до 9 через пробел

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

Номер участка и расстояние до ближайшего шумного (через пробел)

Линейный поиск

✓ 1✗ 4—Войти и решать

Бинарный поиск в подмножестве#84682

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

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

В первой строке — число N (1 ≤ N ≤ 100000) — размер набора.

Во второй строке — N целых чисел (1 ≤ число ≤ 1000000).

В третьей строке — число Q (1 ≤ Q ≤ 100000) — количество запросов.

В следующих Q строках — по одному числу X (1 ≤ X ≤ 1000001).

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

Для каждого запроса выведите ответ на отдельной строке.

Бинарный поиск в массиве

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

Длина последовательности#57757

Рассмотрим отрезок целых неотрицательных чисел от \(l\) до \(r\). Запишем их подряд в десятичной системе счисления, получив строку \(a\). Например, если \(l=3\), \(r=10\), то \(a=345678910\).

Найдите такой отрезок подряд идущих неотрицательных чисел \([l,r]\) (\(0 \le l \le r \le 10^{18}\)), что записанная для него строка \(a\) имеет длину ровно \(S\), а количество чисел на отрезке \([l,r]\) максимально.

Формат входных данных
Первая строка содержит одно целое число \(S\) (\(1 \le S \le 10^{18}\)).

Формат выходных данных
В первой строке выведите длину отрезка \([l,r]\). Если решения не существует, выведите одно целое число \(-1\).

Если решение существует, во второй строке выведите искомые границы отрезка \(l\) и \(r\).

Если существуют несколько решений, выведите любое из них.

"Два указателя"Префиксные суммы(минимумы, ...)

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

Ленивое призерство#57756

Алексей, возможно, самый умный и при этом самый ленивый человек в мире. Сегодня он участвует в олимпиаде.

На олимпиаде участникам даны \(n\) задач, за правильное решение \(i\)-й задачи, участник получит \(a_i\) баллов, за неправильное решение баллов не дают. Дипломы призера дадут тем участникам, которые наберут хотя бы половину от суммарного числа баллов. Например, если на олимпиаде дано три задачи, стоимости которых в баллах равны \(1\), \(3\) и \(4\), соответственно, для получения диплома призера достаточно набрать четыре балла.

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

Алексей настолько ленив, что даже задачи, которые он будет решать, выбирает лениво. Он хочет выбрать некоторую задачу с номером \(k\), а затем решать задачи с номерами \(k, k+1, k+2 \ldots\) до тех пор, пока ему не будет хватать баллов на диплом призера. Максимум, на что готов Алексей, это пропустить одну задачу и не решать ее, чтобы решить в итоге еще меньше задач.

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

Формат входных данных
В первой строке дано одно натуральное число \(n\) — количество задач на олимпиаде (\(1 \le n \le 10^5\)).

Во второй строке заданы \(n\) чисел \(a_1, a_2, \dots a_n\) — стоимости каждой задачи в баллах (\(1 \le a_i \le 10^9\)).

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

Примечание

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

Во втором тесте достаточно решить только вторую задачу, набрав три балла.

"Два указателя"Множества Разреженные таблицы (sparse table)

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

Контрольная по ударениям#56051

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

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

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

Входные данные
Вводится сначала число N — количество слов в словаре (0≤N≤100).

Далее идет N строк со словами из словаря. Каждое слово состоит не более чем из 30 символов. Все слова состоят из маленьких и заглавных латинских букв. В каждом слове заглавная ровно одна буква — та, на которую попадает ударение. Слова в словаре расположены в алфавитном порядке. Если есть несколько возможностей расстановки ударения в одном и том же слове, то эти варианты в словаре идут в произвольном порядке.

Далее идет упражнение, выполненное Петей. Упражнение представляет собой строку текста, суммарным объемом не более 30000 символов. Строка состоит из слов, которые разделяются между собой ровно одним пробелом. Длина каждого слова не превышает 30 символов. Все слова состоят из маленьких и заглавных латинских букв (заглавными обозначены те буквы, над которыми Петя поставил ударение). Петя мог по ошибке в каком-то слове поставить более одного ударения или не поставить ударения вовсе.

Выходные данные
Выведите количество ошибок в Петином тексте, которые найдет Вася.

Примечание
1) В слове cannot, согласно словарю возможно два варианта расстановки ударения. Эти варианты в словаре могут быть перечислены в любом порядке (т.е. как сначала cAnnot, а потом cannOt, так и наоборот).
Две ошибки, совершенные Петей — это слова be (ударение вообще не поставлено) и fouNd (ударение поставлено неверно). Слово thE отсутствует в словаре, но поскольку в нем Петя поставил ровно одно ударение, признается верным.
2) Неверно расставлены ударения во всех словах, кроме The (оно отсутствует в словаре, в нем поставлено ровно одно ударение). В остальных словах либо ударные все буквы (в слове PAGE), либо не поставлено ни одного ударения.

Бинарный поиск в массиве Строки

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