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

Словарь

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

Входные данные
Сначала на вход программы поступает текст, введенный Васей – одна строка из не более чем 100 латинских строчных букв. В следующей строке входных данных задается значение N – количество слов в словаре (N – натуральное число, не превосходящее 2000). В следующих N строках записаны слова из словаря – по одному слову в  строке, каждое слово содержит не более 20 латинских строчных букв. Слова записаны в алфавитном порядке.


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

Примеры

То березка, то рябина…

В целях улучшения ландшафтной архитектуры и экологической обстановки управление городского хозяйства разработало проект программы озеленения центрального проспекта. Согласно проекту, с одной стороны проспекта планируется высадить в ряд деревья K различных видов, для чего были закуплены саженцы деревьев, причем i-го вида было закуплено a_i саженцев.

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

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

Входные данные
В первой строке вводятся два целых числа: K — количество различных видов деревьев (1 ≤ K ≤ 100 000), и P — требуемое количество подряд идущих деревьев разных видов (2 ≤ P ≤ K). Последующие K строк  входных данных содержат целые числа ai, задающие количество закупленных саженцев деревьев i-го вида  (1 ≤ a_i ≤ 10⁹), по одному числу в каждой строке.

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

 

Примеры

Межрегиональная олимпиада

На межрегиональной олимпиаде по программированию роботов соревнования проводятся в один тур и в необычном формате. Задачи участникам раздаются последовательно, а не все в самом начале тура, и каждая i-я задача (1 ≤ i ≤ n) становится доступной участникам в свой момент времени s_i. При поступлении очередной задачи каждый участник должен сразу определить, будет он ее решать или нет. В случае, если он выбирает для решения эту задачу, то у него есть t_i минут на то, чтобы сдать ее решение на проверку, причем в течение этого времени он не может переключиться на решение другой задачи. Если же участник отказывается от решения этой задачи, то в будущем он не может к ней вернуться. В тот момент, когда закончилось время, отведенное на задачу, которую решает участник, он может начать решать другую задачу, ставшую доступной в этот же момент, если такая задача есть, или ждать появления другой задачи. При этом за правильное решение i-й задачи участник получает c_i баллов.

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

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

Входные данные
Первая строка содержит одно целое число n (1 ≤ n ≤ 10⁵) количество задач на олимпиаде.

Последующие n строк содержат описания задач, по три числа на каждой строке: si момент появления i-й задачи в минутах, t_i время, отведенное на ее решение в минутах, и ci сколько баллов получит участник за решение этой задачи (1 ≤ s_i, t_i, c_i ≤ 10⁹).

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

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

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

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

Примеры

Сложность двоичного поиска

Ближайшее слева

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

В первой строке входных данных содержатся числа n и k (0 < n, k <= 10⁵) — длина массива и число запросов. Во второй строке содержатся n элементов массива, отсортированного по неубыванию. В третьей строке содержатся k запросов. Все элементы массива и запросы — целые числа, каждое из которых по модулю не превосходит 2⋅10⁹ .

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

Примеры

5 5
3 3 5 8 9
2 4 8 1 10

0
2
4
0
5

Последний элемент > x

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

В первой строке входных данных содержатся числа n и k (0 < n, k <= 10⁵) — длина массива и число запросов. Во второй строке содержатся n элементов массива, отсортированного по невозрастанию. В третьей строке содержатся k запросов. Все элементы массива и запросы — целые числа, каждое из которых по модулю не превосходит 2⋅10⁹ .

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

Примеры

5 5
9 8 5 3 3
2 4 8 1 10

5
3
1
5
0

Первый, меньший данного

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

В первой строке входных данных содержатся числа n и k (0 < n, k <= 10⁵) — длина массива и число запросов. Во второй строке содержатся n элементов массива, отсортированного по невозрастанию. В третьей строке содержатся k запросов. Все элементы массива и запросы — целые числа, каждое из которых по модулю не превосходит 2⋅10⁹ .

Для каждого из k запросов выведите минимальный номер элемента массива, меньше данного. Если таких нет, выведите 0.

Примеры

5 5
9 8 5 3 3
2 4 8 1 10

0
4
3
0
1

Бинарный поиск в невозрастающем массиве - 1

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

Бинарный поиск в невозрастающем массиве - 3

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

Бинарный поиск в невозрастающем массиве - 4.2

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

Бинарный поиск в невозрастающем массиве - 6

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

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

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

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

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

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

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

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

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

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

Медиана объединений

Дано N упорядоченных по неубыванию последовательностей целых чисел (т.е. каждый следующий элемент больше либо равен предыдущему), в каждой из последовательностей ровно L элементов. Для каждых двух последовательностей выполняют следующую операцию: объединяют их элементы (в объединенной последовательности каждое число будет идти столько раз, сколько раз оно встречалось суммарно в объединяемых последовательностях), упорядочивают их по неубыванию и смотрят, какой элемент в этой последовательности из 2L элементов окажется на месте номер L (этот элемент называют левой медианой).

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

Входные данные
Сначала вводятся числа N и L (2≤N≤100, 1≤L≤300). В следующих N строках задаются параметры, определяющие последовательности.

Каждая последовательность определяется пятью целочисленными параметрами: x₁, d₁, a, c, m. Элементы последовательности вычисляются по следующим формулам: x₁ нам задано, а для всех i от 2 до L: x₁ = x₁–1+d_i-1. Последовательность d_i определяется следующим образом: d₁ нам задано, а для i≥2 di=((a*d_i-1+c) mod m), где mod – операция получения остатка от деления (a*d_i-1+c) на m.

Для всех последовательностей выполнены следующие ограничения: 1≤m≤40000, 0≤a<m, 0≤c<m, 0≤d1<m. Гарантируется, что все члены всех последовательностей по модулю не превышают 10⁹.

Выходные данные
В первой строке выведите медиану объединения 1-й и 2-й последовательностей, во второй строке — объединения 1-й и 3-й, и так далее, в (N-1)-ой строке — объединения 1-й и N-ой последовательностей, далее медиану объединения 2-й и 3-й, 2-й и 4-й, и т.д. до 2-й и N-ой, затем 3-й и 4-й и так далее. В последней строке должна быть выведена медиана объединения (N–1)-й и N-ой последовательностей.

Подарки в хранилище

Дед Мороз хранит огромные запасы подарков в своих тайных хранилищах. Хранилище состоит из ячеек, нумерация которых начинается с единицы. В каждой ячейке находится строго один подарок. Одинаковые подарки хранятся в идущих подряд ячейках. Подарки в хранилище отсортированы по алфавиту.

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

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

Формат ввода

В первой строке вводится натуральное число \(n\) — количество ячеек в ближайшем в данный момент к Деду Морозу хранилище (\(1\leqslant n\leqslant 10^6\)).

В последующих \(n\) строках вводятся названия подарков, хранящихся в ячейках рассматриваемого хранилища (в порядке возрастания номеров ячеек), — слова, состоящие из строчных латинских букв.

Далее в отдельной строке вводится натуральное число \(k\) — количество подарков, указанных в письме Вити (\(1\leqslant k\leqslant 10^5\)).

В последующих \(k\) строках вводятся названия подарков из списка Вити.

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

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

Если указанный Витей подарок имеется в хранилище, программа должна вывести сообщение "In stock".

В противном случае должно быть выведено сообщение "Not in stock".

Подарки в хранилище 2

Вы уже знаете, что Дед Мороз хранит запасы подарков в своих тайных хранилищах. Напомним, что хранилище состоит из ячеек, нумерация которых начинается с единицы. В каждой ячейке находится строго один подарок. Одинаковые подарки хранятся в идущих подряд ячейках. Подарки в хранилище отсортированы по алфавиту.

В одном из хранилищ имеется \(n\) ячеек. Ячейки объединяются в камеры хранения, по \(m\) ячеек в каждой. Камеры хранения нумеруются так же, как и ячейки, начиная с единицы. То есть ячейки с номерами с 1 по \(m\) находятся в первой камере, с \(m+1\) по \(2m\) — во второй камере, и так далее.

Вам дана информация о подарках, хранящихся во всех \(n\) ячейках данного хранилища. Напишите программу, определяющую номер камеры, в которой хранится каждый из \(k\) подарков из списка пожеланий одного школьника. Гарантируется, что все подарки из списка имеются в наличии в хранилище. Если подарок хранится сразу в нескольких соседних камерах, то требуется вывести номер первой из них.

Формат ввода

В первой строке вводятся натуральное число \(n\) — количество ячеек в рассматриваемом хранилище и натуральное число \(m\) — количество ячеек в камере хранения (\(1\leqslant n\leqslant 10^6\), \(2\leqslant m\leqslant 10^5\)).

В последующих \(n\) строках вводятся названия подарков, хранящихся в ячейках рассматриваемого хранилища (в порядке возрастания номеров ячеек), — слова, состоящие из строчных латинских букв.

Далее в отдельной строке вводится натуральное число \(k\) — количество подарков, указанных в пожеланиях школьника (\(1\leqslant k\leqslant 10^5\)).

В последующих \(k\) строках вводятся названия подарков из списка.

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

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

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

Программа полёта Деда Мороза

Одна из самых сложных и важных задач Деда Мороза в новогоднюю ночь — составление маршрута перемещения по городам России. Для этого он заранее измеряет расстояния от его усадьбы до каждого города (по прямой). Далее дедушка руководствуется следующим правилом. Пусть очередным пунктом маршрута является город, расстояние до которого от усадьбы равно \(x_i\) км. Тогда следующим пунктом маршрута станет город, находящийся от усадьбы на расстоянии \(x_j\) км, где значение \(\left|x_i-x_j\right|\) наименьшее. Если таких городов несколько, то будет выбран первый из них по алфавиту.

Напишите программу, определяющую по информации о городах, требующих посещения, и текущем городе следующий город маршрута.

Формат ввода

В первой строке вводится одно натуральное число \(n\) — количество ещё не посещённых городов (\(1\leqslant n\leqslant 10^6\)).

Далее в \(n\) строках вводятся названия этих городов и расстояния от них до усадьбы Деда Мороза (расстояния целые, положительные, не превосходят \(10^9\)). Гарантируется, что названия всех городов различны. Название города состоит строго только из латинских букв (все буквы строчные, кроме первой — она заглавная).

В следующей строке вводится натуральное число \(k\) — количество рассматриваемых случаев текущего местоположения Деда Мороза (\(1\leqslant k\leqslant 10^5\)).

В последней строке через пробел вводится \(k\) натуральных чисел, не превосходящих \(10^9\), — расстояния от усадьбы до возможных текущих городов.

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

Для каждого возможного варианта текущего положения Деда Мороза выведите в отдельной строке название следующего города на маршруте новогоднего волшебника.