Темы --> Информатика --> Язык программирования --> Типы данных
    Символы(9 задач)
    Строки(121 задач)
    Целые числа(112 задач)
    Битовые операции(28 задач)
    Логический тип(3 задач)
    Структуры(18 задач)
    Вещественные числа(33 задач)
    Множества(16 задач)
    Словари(21 задач)
---> 356 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 54 55 56 57 58 59 60 >> Отображать по:
#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
#111145
Две подпоследовательности
  
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
256 megabytes

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

Пусть {a1, a2, ..., an} — данная последовательность строк, которую необходимо сжать. Здесь и далее будем считать, что все строки имеют одинаковую длину и состоят только из символов 0 и 1. Определим функцию сжатия:

  • f(пустая последовательность) = пустая строка
  • f(s) = s.
  • f(s1, s2) = наименьшая по длине строка, у которой один из префиксов равен s1, а один из суффиксов равен s2. Например, f(001, 011) = 0011, f(111, 011) = 111011.
  • f(a1, a2, ..., an) = f(f(a1, a2, an - 1), an). Например, f(000, 000, 111) = f(f(000, 000), 111) = f(000, 111) = 000111.

Перед Валерой стоит серьезная задача — разделить данную последовательность {a1, a2, ..., an} на две подпоследовательности {b1, b2, ..., bk} и {c1, c2, ..., cm}, m + k = n, так, чтобы величина S = |f(b1, b2, ..., bk)| + |f(c1, c2, ..., cm)| приняла минимально возможное значение. Здесь |p| обозначает длину строки p.

Обратите внимание, что запрещается менять относительный порядок строк в подпоследовательностях. Разрешается делать одну из подпоследовательностей пустой. Каждый элемент исходной последовательности должен принадлежать ровно одной из получившихся подпоследовательностей. Элементы подпоследовательностей b и c не обязательно должны идти подряд в исходной последовательности a, то есть они могут чередоваться (смотрите примеры 2 и 3).

Помогите Валере найти минимальное возможное значение S.

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

В первой строке входных данных содержится целое число n — количество строк (1 ≤ n ≤ 2·105). Далее в n строках даны элементы последовательности — строки длиной от 1 до 20 символов, состоящие только из символов 0 и 1. На i + 1 строке входных данных находится i-ый член последовательности. Элементы последовательности разделены исключительно символом перевода строки. Гарантируется, что все строки имеют одинаковую длину.

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

Выведите единственное число — минимально возможное значение S.

Примеры тестов
Входные данные
3
01
10
01
Выходные данные
4
Входные данные
4
000
111
110
001
Выходные данные
8
Входные данные
5
10101
01010
11111
01000
10010
Выходные данные
17
Примечание

Подробные ответы к тестам:

  • Оптимальный вариант: сделать одну из подпоследовательностей пустой, а вторую — равной всей данной последовательности. S = |f(01, 10, 01)| = |f(f(01, 10), 01)| = |f(010, 01)| = |0101| = 4.
  • Оптимальный вариант: b = {000, 001}, c = {111, 110}. S = |f(000, 001)| + |f(111, 110)| = |0001| + |1110| = 8.
  • Оптимальный вариант: b = {10101, 01010, 01000}, c = {11111, 10010}. S = |10101000| + |111110010| = 17.

Подзадача 1. N ≤ 10. Решение оценивается в 30 баллов.

Подзадача 2. N ≤ 1 000. Решение оценивается в 30 баллов.

Подзадача 3. Дополнительные ограничения отсутствуют. Решение оценивается в 40 баллов.

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

#111184
Питон
  
Темы: [Строки]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Витя изучает новый язык программирования Питон. Пока он только успел изучить арифметические операции и условную инструкцию «if», но он уже полюбил этот язык за красоту и лаконичность синтаксиса.

Отличительной особенностью языка Питон является то, что блоки после инструкций «if» и «else» (а также в циклах «for» и «while», но Витя еще не успел изучить циклы) выделяются не ключевыми словами (например, в языке Паскаль используются слова «begin» и «end») и не скобками (например, в языке C используются фигурные скобки), а величиной отступа от начала строки, то есть количеством пробелов, которые идут в начале строки. Например, в такой программе:


if a < 0:
    print("Число a - отрицательное")
    a = -a
print("Теперь a - положительное")

если условие «a < 0» будет истинно, то выполнятся две следующие строки «print("Число a - отрицательное")» и «a = -a», а вот следующая строка «print("Теперь a - положительное")» уже находится вне блока условной инструкции «if» и будет выполнена после этой условной инструкции независимо от истинности проверенного условия.

Более формально правила расстановки пробелов в программе такие. Первая строка программы, а также все инструкции в программе, если они не находятся внутри блоков условных инструкций, не содержат отступа, то есть пробелов в начале строки. Если в программе встречается условная инструкция «if», то блок после этой инструкции пишется с отступом. Величина отступа может быть произвольной (1, 2, 3 и более пробелов), но для всех инструкций внутри блока отступ должен быть одинаковым. Если после инструкции «if» идет инструкция «else», то она должна иметь такой же отступ, что и соответствующая ей инструкция «if», после инструкции «else» идет блок из одной и более инструкций с дополнительным отступом. При этом отступ у блока «if» и блока соответствующего ему «else» может быть различным (смотрите примеры верных программ ниже), но внутри одного блока отступ должен быть одинаковым.

Каждой инструкции «if» может соответствовать не более одной инструкции «else». Не допускаются инструкции «else», перед которыми нет инструкции «if». После каждой инструкции «if» и «else» обязательно следует хотя бы одна инструкция с отступом.

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

Правильно (разрешается разный отступ в блоках «if» и «else») Правильно (вложенные условные инструкции) Неправильно (разный отступ в одном блоке) Неправильно (нет блока с отступом после инструкции «if») 
if x > 0:
    print("x > 0")
    print(x)
else:
  print("x < 0")
  print(-x)
print("Bye")

if a > b:
  if a > c:
        print(a)
  else:
      print(c)
else:
      if b > c:
        print(b)
      else:
        print(c)

if x > 0:
        print(x)
    print("x > 0")

if x > 0:
else:
    print(x)

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

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

Во входном файле записан некоторый текст, содержащий не более 100 строк. Длина каждой строки не превосходит 100 символов. Каждая строка состоит из символов, ASCII-коды которых не менее 32 и не более 126.

Строка считается инструкцией «if», если первыми непробельными символами строки является слово «if», после которого идет пробел, а затем — любое число любых символов. Строка считается инструкцией «else», если она содержит только одно слово «else:» (с двоеточием после него) и, возможно, отступ в начале строки.

Любая строка содержит хотя бы один непробельный символ. Последняя строка программы обязательно содержит ровно одно слово «exit()» без пробелов, завершающееся символом конца строки.

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

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

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

Входные данные
a, b, c = map(int, input().split())
if a > b:
    if a > c:
        print(a)
    else:
        print(c)
else:
    if b > c:
      print(b)
    else:
          print(c)
exit()
Выходные данные
0
Входные данные
x = int(input())
if x < 0:
  print("Negative")
    x = -x
else:
    print("Positive")
exit()
Выходные данные
4

Примечание

Online-группа тестов оценивается в 50 баллов. Тесты этой группы не содержат инструкции «else».

Offline-группа тестов оценивается в 50 баллов.

Программа, которая выдает правильный ответ только на тех примерах, в которых ответ 0, будет оцениваться в 0 баллов (то есть для получения ненулевого числа баллов за задачу программа должна выдавать правильный ответ хотя бы на одном тесте, помимо теста из условия, в котором ответ не 0).

#111423
Поиск шаблона
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Шаблоном называется любая непустая строка, состоящая из маленьких латинских букв и символов "*".

Будем говорить, что строка T подходит под шаблон P, если в P можно символы "*" так заменить на последовательности букв латинского алфавита (возможно, пустые), что в итоге получится строка T. К примеру, строка aadbc походит под шаблон a*b*c, т.к. можно первую звездочку заменить на последовательность букв ad, а вторую — на пустую последовательность, в результате чего получится искомая строка.

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

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

Первая строка входных данных содержит шаблон P, длиной не более 100 символов. Вторая строка содержит исходную строку T, длиной не более 100 000 символов. Все строки имеют длину не менее одного символа.

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

Выведите единственное число — искомое число циклических сдвигов, подходящих под шаблон.

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

Входные данные
aaaa
aaaa
Выходные данные
4
Входные данные
a*a
aaaaaa
Выходные данные
6
Входные данные
*a*b*c*
abacabadabacaba
Выходные данные
15

#111506
Скучная лекция
  
Темы: [Строки]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Лёша сидел на лекции. Ему было невероятно скучно. Голос лектора казался таким далеким и незаметным...

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

Тут ему пришла в голову мысль — времени до конца лекции все равно ещё очень много, почему бы не продолжить выписывать всеми возможными способами это слово без какой-то части с начала и какой-то части с конца?

После лекции Лёша рассказал Максу, как замечательно он скоротал время. Максу стало интересно посчитать, сколько букв каждого вида встречается у Лёши в листочке. Но к сожалению, сам листочек куда-то запропастился.

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

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

На вход подаётся строка, состоящая из строчных латинских букв — любимое слово Лёши.

Длина строки лежит в пределах от 5 до 100 000 символов.

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

Для каждой буквы на листочке Лёши, выведите её, а затем через двоеточие и пробел сколько раз она встретилась в выписанных Лёшей словах (см. формат вывода в примерах). Буквы должны следовать в алфавитном порядке. Буквы, не встречающиеся на листочке, выводить не нужно.

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

Входные данные
hello
Выходные данные
e: 8
h: 5
l: 17
o: 5
Входные данные
abacaba
Выходные данные
a: 44
b: 24
c: 16

Примечание

Пояснение к первому примеру. Если любимое Лёшино слово — "hello", то на листочке у Лёши будут выписаны следующие слова:

  • "hello"
  • "hell"
  • "ello"
  • "hel"
  • "ell"
  • "llo"
  • "he"
  • "el"
  • "ll"
  • "lo"
  • "h"
  • "e"
  • "l"
  • "l"
  • "o"
Среди этих слов 8 раз встречается буква "e", 5 раз — буква "h", 17 раз — буква "l" и 5 раз буква "o".

Страница: << 54 55 56 57 58 59 60 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест