Темы --> Информатика
    Язык программирования(952 задач)
    Алгоритмы(1657 задач)
    Структуры данных(279 задач)
    Интерактивные задачи(17 задач)
    Другое(54 задач)
---> 2656 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 278 279 280 281 282 283 284 >> Отображать по:
#2879
Робот
  
#2880
Санта Клаус
  
#2881
Подстрока
  
+ структуры данных (например, двумерное дерево интервалов)

Недавно разведка перехватила зашифрованное сообщение — строку s. Все ресурсы аналитического центра, в котором вы работаете, были брошены на его декодирование. Ваш отдел занимается шифрами нового поколения. На данный момент известно всего n таких шифров. Для каждого из них есть три характерных параметра — целые числа l, r и строка t. Пусть строка g была получена в результате применения этого метода. Тогда строка glgl+1 . . . gr−1gr (здесь gi — это i-й символ строки g) содержит t как подстроку.

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

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

Первая строка входного файла содержит строку s (1 ≤ |s| ≤ 100 000, где |s| — длина строки s).

Вторая строка входного файла содержит целое число n — количество типов шифрования (1 ≤ n ≤ 100 000). Последующие nстрок содержат по два целых числа li, ri и строку ti, разделенные пробелами — характерные параметры i-го метода шифрования (1 ≤ li ≤ ri ≤ |s|).

Все строки состоят из строчных букв латинского алфавита. Суммарная длина всех ti не превосходит 100 000.

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

Выведите одну строку — для каждого типа шифрования «+», если сообщение s могло быть получено в результате его применения, или «-» в противном случае.

Примеры
Входные данные
frommarsiam
3
6 10 i
2 11 am
1 9 human
Выходные данные
++-
#2882
Вода
  
#2883
Swimming pool
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

В бассейне плавает \(S\) людей.

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

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

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

Первая строка содержит единственное целое число \(N\) – количество дорожек \((1 \le N \le 400)\). Следующая строчка содержит \(N\) чисел, разделённых пробелами. \(i\)-ое число описывает количество пловцов на \(i\)-ой дорожке. Сумма этих чисел \(S (0 \le S \le 1500)\).

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

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

Система оценивания

В первой группе тестов \(N\) не превосходят 15, она оценивается в 40 баллов.
Во второй группе тестов \(S\) не превосходит 400, дополнительные ограничения на \(N\) отсутствуют, она оценивается в 25 баллов при условии прохождения всех тестов первой группы.
Во третьей группе тестов дополнительные ограничения отсутствуют, она оценивается в 35 баллов при условии прохождения всех тестов первой и второй групп.

Примеры
Входные данные
3
8 0 2
Выходные данные
5
Входные данные
3
8 5 7
Выходные данные
1
Страница: << 278 279 280 281 282 283 284 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест