Темы --> Информатика --> Алгоритмы --> Алгоритмы поиска --> Бинарный поиск --> Бинарный поиск в массиве
---> 2 задач <---
Источники --> Личные олимпиады --> Московская олимпиада школьников
    6-9 классы(30 задач)
    7-9 классы(25 задач)
    10-11 классы(114 задач)
Страница: 1 Отображать по:
#515
Словарь
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Дана строка и словарь. Требуется разбить строку на слова из словаря.

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

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

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

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

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

Примеры
Входные данные
whatcanido
6
a
an
can
do
i
what
Выходные данные
what can i do
#111185
K-квест
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

В одной из компьютерных игр-квестов есть следующее задание. На карте игрового мира размещены N персонажей, с каждым из которых может встретиться игрок. От общения с i-м персонажем карма игрока меняется на величину ai, которая может быть как положительной, так отрицательной или даже нулем.

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

Комнаты, в которых находятся персонажи, соединены односторонними магическими порталами, поэтому игроку придется встречать персонажей в определенной последовательности: после персонажа номер i он попадает к персонажу номер i + 1, затем к персонажу номер i + 2, и т.д. В комнате последнего персонажа с номером N портала к другому персонажу нет.

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

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

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

В первой строке входных данных записаны два числа: количество персонажей N и необходимый уровень кармы K (|K| ≤ 109, K ≠ 0). Во второй строке через пробел записаны N целых чисел a1, a2, ..., aN — величины, на которые меняется карма героя после общения с персонажами с номерами 1, 2, ..., N соответственно.

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

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

Примеры тестов

Входные данные
5 3
-2 2 -1 2 4
Выходные данные
2 4
Входные данные
7 1
1 -1 1 -1 1 -1 2
Выходные данные
5 5
Входные данные
4 3
2 2 2 2
Выходные данные
-1

Примечание

Тесты по этой задачи разбиты на группы. На 1-3 группах тестов проверка проводится во время тура (online), на последней группе — после окончания тура (offline).

В первой группе тестов 1 ≤ N ≤ 100, |ai| ≤ 100. Баллы начисляются только при прохождении всех тестов группы, группа оценивается в 20 баллов.

Во второй группе тестов 1 ≤ N ≤ 2000, |ai| ≤ 1 000 000. Баллы начисляются только при прохождении всех тестов группы, группа оценивается в 20 баллов.

В третьей группе тестов 1 ≤ N ≤ 200 000, 0 ≤ ai ≤ 109. Баллы начисляются только при прохождении всех тестов группы, группа оценивается в 20 баллов.

В четвертой группе тестов 1 ≤ N ≤ 200 000, |ai| ≤ 109. Каждый тест этой группы оценивается отдельно. Общее число баллов за тесты этой группы равно 40.

Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест