Темы --> Информатика --> Алгоритмы --> Алгоритмы поиска --> Бинарный поиск --> Бинарный поиск в массиве
---> 24 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 1 2 3 4 5 >> Отображать по:
#3041
Поиск в словаре
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Словарь задан массивом отсортированных в лексикографическом порядке строк. Напишите программу эффективного поиска слова в словаре.

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

На вход программе сначала подается искомое слово, во второй строке — число n (1 <= n <= 100000) — количество слов в словаре. В следующих n строках расположены слова словаря, по одному слову в строке. Все слова состоят только из строчных латинских букв, слова упорядочены по алфавиту (расположены в лексикографическом порядке).

Длина слов не превосходит 20. Пустых слов нет.

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

Выведите YES или NO в зависимости от того, есть искомое слово в словаре или нет.

Примеры
Входные данные
abba
4
a
ab
aba
baba
Выходные данные
NO
#3728
Бинарный поиск-2
  
ограничение по времени на тест
6.0 second;
ограничение по памяти на тест
256 megabytes

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

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

В первой строке вводится одно натуральное число N, не превосходящее 105: количество чисел в массиве.

Во второй строке вводятся N натуральных чисел, не превосходящих 109, каждое следующее не меньше предыдущего.

В третьей строке вводится количество искомых чисел M - натуральное число, не превосходящее 106.

В четвертой строке вводится M натуральных чисел, не превосходящих 109.

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

Для каждого запроса выведите в отдельной строке одно число: количество элементов массива, равных числу-запросу. Элементы массива нумеруются с единицы.

Если в массиве нет такого числа, выведите 0.

Примеры
Входные данные
4
1 2 2 4
4
1 4 3 2
Выходные данные
1
1
0
2
#3729
Бинарный поиск-1
  
ограничение по времени на тест
6.0 second;
ограничение по памяти на тест
256 megabytes

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

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

В первой строке вводится одно натуральное число N, не превосходящее 105: количество чисел в массиве.

Во второй строке вводятся N натуральных чисел, не превосходящих 109, каждое следующее не меньше прелылущего.

В третьей строке вводится количество искомых чисел M - натуральное число, не превосходящее 106.

В четвертой строке вводится M натуральных чисел, не превосходящих 109.

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

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

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

Примеры
Входные данные
4
1 2 2 3
4
4 3 2 1
Выходные данные
0 0
4 4
2 3
1 1
#3871
«Abracadabra»
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Строка s называется супрефиксом для строки t, если t начинается с s и заканчивается на s. Например, «abra» является супрефиксом для строки «abracadabra». В частности, сама строка t является своим супрефиксом. Супрефиксы играют важную роль в различных алгоритмах на строках.

В этой задаче требуется решить обратную задачу о поиске супрефикса, которая заключается в следующем. Задан словарь, содержащий n слов t1, t2, …, tn и набор из m строк-образцов s1, s2, …, sm. Необходимо для каждой строки-образца из заданного набора найти количество слов в словаре, для которых эта строка-образец является супрефиксом.

Требуется написать программу, которая по заданному числу n, n словам словаря t1, t2, …, tn, заданному числу m и m строкам-образцам s1, s2, …, sm вычислит для каждой строки-образца количество слов из словаря, для которых эта строка-образец является супрефиксом.

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

Первая строка входного файла содержит целое число n (1 ≤ n ≤ 200 000).

Последующие n строк содержат слова t1, t2, …, tn, по одному слову в каждой строке. Каждое слово состоит из строчных букв латинского алфавита. Длина каждого слова не превышает 50. Суммарная длина всех слов не превышает 106. Словарь не содержит пустых слов.

Затем следует строка, содержащая целое число m (1 ≤ m ≤ 200 000).

Последующие m строк содержат строки-образцы s1, s2, …, sm, по одной на каждой строке. Каждая строка-образец состоит из строчных букв латинского алфавита: Длина каждой строки-образца не превышает 50. Суммарная длина всех строк-образцов не превышает 106. Никакая строка-образец не является пустой строкой.

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

Выходной файл должен содержать m чисел, по одному на строке.

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

Система оценки

Решения, работающие при \(n\), \(m\) не превосходящими 100 оцениваются из 30 баллов.

Примеры
Входные данные
4
abacaba
abracadabra
aa
abra
3
a
abra
abac
Выходные данные
4
2
0
#3878
Калитка в заборе
  
ограничение по времени на тест
0.3 second;
ограничение по памяти на тест
256 megabytes

Дядя Фёдор, кот Матроскин и Шарик решили обновить забор вокруг своего сада в Простоквашино. Матроскин и Шарик, недолго думая, вкопали \(N\) столбов вдоль одной из сторон участка. Это очень сильно расстроило Дядю Фёдора, так как его друзья забыли о самом главном — калитка должна находиться именно на этой стороне, и для неё необходимо было оставить проём шириной как минимум \(W\). Теперь им придётся выкапывать некоторые столбы.

Чтобы работа не пропадала даром, выкопать надо как можно меньше столбов. Помогите Дяде Фёдору определить, какие именно столбы надо выкопать. После выкапывания столбов должен найтись промежуток (между двумя оставшимися столбами, или между оставшимся столбом и концом стороны участка, или между двумя концами стороны участка) ширины больше или равной \(W\).

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

Первая строка содержит два целых числа \(N\) и \(W\) — количество вкопанных столбов и минимально необходимую ширину проёма для калитки соответственно. Гарантируется, что \(0 \leq N \leq 30\,000\) и что \(0 \leq W \leq 60\,000\).

Будем считать, что вдоль интересующей нас стороны участка введена ось координат. Во второй строке входного файла находятся два числа \(L\) и \(R\) — координаты левого и правого конца этой стороны (\(L \lt R\)). Далее следуют \(N\) чисел — координаты вкопанных столбов. Все координаты (включая \(L\) и \(R\)) — различные целые числа, по модулю не превосходящие \(30\,000\). Гарантируется, что все столбы вкопаны между левым и правым концами стороны.

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

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

Если решений несколько, то вы можете вывести любое. Если решения нет, то выведите в выходной файл одну строку, содержащую число -1.

Примечание

Time Limit : 0.3 секунды.

Примеры
Входные данные
3 2
2 6
3 4 5
Выходные данные
1
2
Входные данные
3 2
1 6
4 3 5
Выходные данные
0
Входные данные
3 5
1 7
5 3 4
Выходные данные
3
2
1
3
Страница: << 1 2 3 4 5 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест