| | | |
|
Двоичный поиск
Бинарный поиск в массиве
Алгоритмы поиска
Реализуйте алгоритм бинарного поиска.
Формат входных данных
В первой строке входных данных содержатся натуральные числа N и K (\(0<N,\ K <= 100000\)). Во второй строке задаются N элементов первого массива, отсортированного по возрастанию. В третьей строке – K элементов второго массива.
Элементы обоих массивов - целые числа, каждое из которых по модулю не превосходит \(10^9\).
Формат выходных данных
Требуется для каждого из K чисел вывести в отдельную строку "YES", если это число встречается в первом массиве, и "NO" в противном случае.
| |
|
|
Словарь
Обработка текста
Алгоритмы поиска
Словари
Однажды, разбирая старые книги на чердаке, школьник Вася нашёл англо-латинский словарь. Английский он к тому времени знал в совершенстве, и его мечтой было изучить латынь. Поэтому попавшийся словарь был как раз кстати.
К сожалению, для полноценного изучения языка недостаточно только одного словаря: кроме англо-латинского необходим латинско-английский. За неимением лучшего он решил сделать второй словарь из первого.
Как известно, словарь состоит из переводимых слов, к каждому из которых приводится несколько слов-переводов. Для каждого латинского слова, встречающегося где-либо в словаре, Вася предлагает найти все его переводы (то есть все английские слова, для которых наше латинское встречалось в его списке переводов), и считать их и только их переводами этого латинского слова.
Помогите Васе выполнить работу по созданию латинско-английского словаря из англо-латинского.
Формат входных данных
В первой строке содержится единственное целое число \(N\) (\(1 \le N \le 100\)) — количество английских слов в словаре. Далее следует \(N\) описаний. В первой строке каждого описания содержится английское слово. В следующей строке записано единственное число \(K \ge 1\) — количество переводов. В следующих \(K\) строках приведены переводы текущего английского слова на латинский, по одному в каждой строке.
Все слова состоят только из маленьких латинских букв. Общее количество слов на входе не превышает \(100\). Длина каждого слова не превосходит 15 символов.
Формат выходных данных
Выведите соответствующий данному латинско-английский словарь в следующем формате. В первую строку запишите единственное целое число \(N\) — количество латинских слов в словаре. Далее выведите \(N\) описаний, каждое описание в отдельной строке: сначала латинское слово, затем отделённый пробелами дефис (символ номер 45), затем разделённые запятыми с пробелами переводы этого латинского слова на английский.
При этом порядок английских слов внутри перевода одного латинского может быть каким угодно. Кроме того, порядок следования латинских слов для перевода в словаре также не важен.
| |
|
|
Маяк 1. Пропавшая радиограмма
Алгоритмы поиска
Бинарный поиск
Бинарный поиск в массиве
Маяк 1. Пропавшая радиограмма
Экспедиция «МАЯК». Диспетчер получил запрос на радиограмму с кодом x. Все радиограммы хранятся в архиве по возрастанию кода, и двух сообщений с одинаковым кодом не бывает. Диспетчеру нужен номер ячейки, в которой хранится нужная радиограмма. Если такой радиограммы никогда не поступало, нужно сообщить об этом.
Входные данные
В первой строке записаны целые числа n и x — количество радиограмм и код запроса. Во второй строке — n различных кодов, расположенных в строго возрастающем порядке.
Выходные данные
Выведите номер ячейки с кодом x (нумерация с 0). Если радиограммы нет, выведите -1.
Ограничения
0 ≤ n ≤ 200000; 0 ≤ x ≤ 1000000000; 0 ≤ a[i] ≤ 1000000000. Значения строго возрастают. При n = 0 вторая строка пустая.
Алгоритм должен работать за O(log n) после чтения входных данных; полный перебор при поиске не используйте.
| |
|
|
Маяк 2. Граница безопасной зоны
Алгоритмы поиска
Бинарный поиск
Бинарный поиск в массиве
Маяк 2. Граница безопасной зоны
Экспедиция «МАЯК». Перед запуском капсулы инженеры рассортировали результаты измерения радиационного фона: от самого большого показания к самому маленькому. Равные результаты стоят рядом. Значение не выше x считается безопасным. Диспетчеру нужна первая запись в этом списке, с которой начинаются безопасные показания. Если безопасных показаний нет, запуск пока не разрешён.
Входные данные
В первой строке даны n и x — число измерений и допустимый радиационный фон. Во второй строке — n измерений по невозрастанию (от больших к меньшим).
Выходные данные
Выведите индекс первого измерения, не превышающего x. Если безопасных измерений нет, выведите -1.
Ограничения
0 ≤ n ≤ 200000; 0 ≤ x ≤ 1000000000; 0 ≤ a[i] ≤ 1000000000. Значения не возрастают (совпадения разрешены). При n = 0 вторая строка пустая.
Алгоритм должен работать за O(log n) после чтения входных данных; полный перебор при поиске не используйте.
| |
|
|
Маяк 3. Подбор аккумулятора
Алгоритмы поиска
Бинарный поиск
Бинарный поиск в массиве
Маяк 3. Подбор аккумулятора
Экспедиция «МАЯК». Для дальнего выхода роботу требуется запас энергии не меньше x. Батареи на складе стоят в порядке неубывания ёмкости, некоторые имеют одинаковую ёмкость. Снабженец хочет взять первую подходящую батарею: так он не потратит более ёмкий запас без необходимости.
Входные данные
В первой строке записаны n и x — число батарей и минимально необходимая ёмкость. Во второй строке — n ёмкостей по неубыванию.
Выходные данные
Выведите индекс первой батареи, ёмкости которой хватит для выхода. Если такой батареи нет, выведите -1.
Ограничения
0 ≤ n ≤ 200000; 0 ≤ x ≤ 1000000000; 0 ≤ a[i] ≤ 1000000000. Значения не убывают (совпадения разрешены). При n = 0 вторая строка пустая.
Алгоритм должен работать за O(log n) после чтения входных данных; полный перебор при поиске не используйте.
| |
|
|
Маяк 4. До закрытия шлюза
Алгоритмы поиска
Бинарный поиск
Бинарный поиск в массиве
Маяк 4. До закрытия шлюза
Экспедиция «МАЯК». Шлюз исследовательской базы закроется в момент x. Компьютер хранит время событий в отсортированном журнале; события с одинаковым временем возможны. Инженеру нужен номер самого позднего события, которое произошло именно до закрытия. Событие с отметкой ровно x уже не подходит.
Входные данные
В первой строке находятся n и x — количество записей и момент закрытия. Во второй строке — n временных отметок по неубыванию.
Выходные данные
Выведите индекс последнего события, произошедшего строго раньше x. Если ни одно событие не успело, выведите -1.
Ограничения
1 ≤ n ≤ 200000; 0 ≤ x ≤ 1000000000; 0 ≤ a[i] ≤ 1000000000. Значения не убывают (совпадения разрешены).
Алгоритм должен работать за O(log n) после чтения входных данных; полный перебор при поиске не используйте.
| |
|
|
Маяк 5. Последний опасный замер
Алгоритмы поиска
Бинарный поиск
Бинарный поиск в массиве
Маяк 5. Последний опасный замер
Экспедиция «МАЯК». Перед стартом исследовательского модуля тепловые замеры отсортировали от самой высокой температуры к самой низкой. Одинаковые показания встречаются несколько раз. Тревога включается только при значении строго выше x, а ровно x уже не считается перегревом. Оператор ищет последнюю запись в опасной части отсортированного журнала.
Входные данные
Первая строка содержит n и x — количество измерений и порог тревоги. Во второй строке записаны n температур по невозрастанию (от больших к меньшим).
Выходные данные
Выведите индекс последнего измерения с температурой строго больше x. Если превышения нет, выведите -1.
Ограничения
0 ≤ n ≤ 200000; 0 ≤ x ≤ 1000000000; 0 ≤ a[i] ≤ 1000000000. Значения не возрастают (совпадения разрешены). При n = 0 вторая строка пустая.
Алгоритм должен работать за O(log n) после чтения входных данных; полный перебор при поиске не используйте.
| |
|
|
Карточки на квадратном стенде
Алгоритмы поиска
Бинарный поиск
К школьной выставке подготовили N одинаковых прямоугольных карточек. Ширина каждой карточки — A сантиметров, высота — B сантиметров.
Карточки нужно разместить на квадратном стенде ровными горизонтальными рядами. В каждом ряду карточки стоят рядом, а ряды располагаются один над другим. Все карточки ориентированы одинаково: сторона A расположена горизонтально, сторона B — вертикально. Поворачивать карточки, накладывать их друг на друга и выпускать за края стенда нельзя. Зазоры между карточками не нужны; часть мест может остаться пустой.
Найдите наименьшую целую длину стороны стенда, на котором поместятся все карточки.
Входные данные
В одной строке записаны три целых числа A B N. 1 ≤ A, B ≤ 1000; 1 ≤ N ≤ 106.
Выходные данные
Выведите одно целое число — минимальную длину стороны стенда в сантиметрах.
| |
|
|
Фабрика игрушек
Алгоритмы поиска
Бинарный поиск
Для школьного праздника нужно изготовить не менее K игрушек. На фабрике есть N автоматов. Автомат с номером i изготавливает одну игрушку за Ai минут.
Все автоматы начинают работу одновременно в момент времени 0 и работают независимо друг от друга. Закончив игрушку, автомат сразу начинает следующую. Материалов достаточно, готовых игрушек в начале нет.
Игрушка учитывается только после полного завершения работы над ней. Например, автомат, которому нужны 3 минуты, выпускает игрушки в моменты 3, 6, 9 минут и так далее.
Найдите минимальное время, за которое будет готово не менее K игрушек.
Входные данные
В первой строке записаны два целых числа N K — количество автоматов и необходимое количество игрушек. Во второй строке записаны N целых чисел A1, A2, …, AN — время изготовления одной игрушки каждым автоматом. 1 ≤ N ≤ 1000; 1 ≤ K ≤ 109; 1 ≤ Ai ≤ 106.
Выходные данные
Выведите одно целое число — минимальное время в минутах.
| |
|
|
Ленточки для медалей
Алгоритмы поиска
Бинарный поиск
Для турнира приготовили N лент. Длина ленты с номером i равна Ai сантиметров.
Из них нужно вырезать не менее K одинаковых ленточек для медалей. Длина каждой полученной ленточки должна быть целым положительным числом сантиметров.
Каждая ленточка вырезается целиком из одной исходной ленты. Склеивать кусочки нельзя. Остатки можно не использовать; при разрезании длина не теряется.
Найдите наибольшую возможную длину одной ленточки.
Входные данные
В первой строке записаны два целых числа N K — количество исходных лент и необходимое количество ленточек. Во второй строке записаны N целых чисел A1, A2, …, AN — длины исходных лент. 1 ≤ N ≤ 1000; 1 ≤ Ai ≤ 109; 1 ≤ K ≤ A1 + A2 + … + AN. Таким образом, ленточек длиной 1 см всегда хватит.
Выходные данные
Выведите одно целое число — максимальную длину ленточки в сантиметрах.
| |
|
|
Древесина для домика
Алгоритмы поиска
Бинарный поиск
В игре нужно собрать древесину для строительства домика. Рядом растут N деревьев. Высота дерева с номером i равна Ai метрам.
Игрок выбирает одну целую неотрицательную высоту среза H для всех деревьев. У каждого дерева выше H срезается верхняя часть. Её длина добавляется к запасу древесины. Деревья высотой не больше H остаются без изменений.
Например, при высоте среза 6 м дерево высотой 10 м даст 4 м древесины, а дерево высотой 5 м не даст древесины.
Для домика нужно не менее K метров древесины. Найдите наибольшую высоту среза, при которой удастся собрать нужное количество.
Входные данные
В первой строке записаны два целых числа N K — количество деревьев и необходимая суммарная длина срезанных частей. Во второй строке записаны N целых чисел A1, A2, …, AN — высоты деревьев. 1 ≤ N ≤ 1000; 1 ≤ Ai ≤ 109; 1 ≤ K ≤ A1 + A2 + … + AN. При высоте среза 0 древесины всегда достаточно.
Выходные данные
Выведите одно целое число — максимальную высоту среза в метрах.
| |
|