Темы --> Информатика
    Язык программирования(952 задач)
    Алгоритмы(1657 задач)
    Структуры данных(279 задач)
    Интерактивные задачи(17 задач)
    Другое(54 задач)
---> 2656 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 454 455 456 457 458 459 460 >> Отображать по:
#111769
Шифр
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
128 megabytes

Жюри N-ской олимпиады по информатике решило зашифровать свои материалы подстановочным шифром. Для шифрования таким шифром задаётся взаимно-однозначное соответствие между буквами алфавита в открытом (т. е. до шифрования) тексте и буквами алфавита в закрытом (т. е. после шифрования) тексте, это соответствие и является ключом шифра. В процессе шифрования каждая буква в открытом тексте заменяется на соответствующую ей букву в закрытом тексте, порядок букв в слове при этом не меняется.

Однако, память у членов жюри оказалась уже не та, что в молодые годы, поэтому часто они путали, какие буквы надо было заменять на какие. В результате теперь они не могут восстановить свои материалы, а олимпиада уже на носу!

Чтобы разрешить свои проблемы, они обратились к вам. Для облегчения вашей задачи они выписали на бумажку все возможные варианты зашифрования букв, которые они могли применять, в виде набора пар "открытая буква" и "зашифрованная буква". Также вам известны все пары букв N-ского алфавита, которые могут следовать одна за другой в открытом тексте. Ваша задача состоит в том, чтобы по заданному зашифрованному слову сказать, соответствует ли ему хоть одно расшифрованное слово, единственен ли вариант расшифровки, и привести пример вариантов расшифровки слова. Слово A считается возможной расшифровкой слова B, если, во-первых, его можно "зашифровать" (заменяя каждую букву на одну из соответствующих ей "зашифрованных" букв), получив слово B, и, во-вторых, каждая пара букв слова A, стоящих рядом, является допустимой для N-ского языка.

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

N-ский язык пользуется латинским алфавитом из 26 букв, регистр букв N-ское жюри не интересует, поэтому везде в открытом тексте используются большие буквы, а в закрытом — маленькие.

На первой строке входного файла находится одно целое число M (0 ≤ M ≤ 676) — число пар открытых — "зашифрованных" букв, указанных на бумажке, переданной N-ским жюри. Далее следуют M строк, на каждой находятся два символа — сначала открытая буква, потом вариант её "зашифрования". Пары не повторяются.

На следующей строке находится одно целое число K (0 ≤ K ≤ 676) — число пар открытых букв, которые могут идти одна за другой. Далее следуют K строк, на каждой из которых по две открытые буквы, образующие такую пару. Пары не повторяются. Заметим, что возможна ситуация, когда последовательность букв "AB" в слове допустима, а "BA" — нет, в этом случае списке будет дана только пара "AB", а пары "BA" не будет.

На следующей строке расположено одно целое число N (1 ≤ N ≤ 500) — длина зашифрованного слова, а на следующей строке — само слово (N маленьких латинских букв).

Может оказаться так, что какой-то открытой букве не соответствует ни одна "зашифрованная"; это означает, что эта буква в открытом тексте не использовалась.

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

Если вариантов дешифрования нет ни одного, в первую строку выходного файла выведите "no"

Если вариант дешифрования ровно один, в первую строку выходного файла выведите "only" , а во вторую — дешифрованное слово.

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

Примеры
Входные данные
0
0
1
u
Выходные данные
no
Входные данные
4
Ju
Cu
Uo
Ko
3
JC
UJ
JK
3
ouo
Выходные данные
only
UJK
#111771
Множества
  
ограничение по времени на тест
0.75 second;
ограничение по памяти на тест
128 megabytes

На вступительном экзамене по информатике в СУНЦ МГУ Вашему другу предложили реализовать структуру данных для хранения множеств чисел. Так как он специализируется на истории литературы, данную структуру придётся реализовать Вам.

Структура должна хранить m множеств чисел от 0 до n, при этом одно число может принадлежать сразу нескольким множествам.

Вы должны реализовать следующие операции на этой структуре:

  • ADD e s
    Добавить в множество №s (0 <= s <= m) число e (0 <= e <= n).

  • DELETE e s
    Удалить из множества №s (0 <= s <= m) число e (0 <= e <= n). Гарантируется, что до этого число e было помещено в множество

  • CLEAR s
    Очистить множество №s (0 <= s <= m).

  • LISTSET s
    Показать содержимое множества №s (0 <= s <= m), либо -1, если множество пусто.

  • LISTSETSOF e
    Показать множества, в которых лежит число e (0 <= e <= n), либо -1, если этого числа нет ни в одном множестве.

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

Сначала вводятся числа N (1 <= N <= 9223372036854775807), M (1 <= M <= 100000) и K (0 <= K <= 100000) — максимальное число, номер максимального множества и количество запросов к структуре данных. Далее следуют K строк указанного формата запросов.

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

На каждый запрос LISTSET Ваша программа должна вывести числа — содержимое запрошенного множества или -1, если множество пусто.

На каждый запрос LISTSETSOF Ваша программа должна вывести числа — номера множеств, содержащие запрошенное число или -1, если таких множеств не существует.

На прочие запросы не должно быть никакого вывода.

Гарантируется, что правильный вывод программы не превышает одного мегабайта.

Примеры
Входные данные
10 10
9
ADD 1 1
ADD 1 2
ADD 2 1
LISTSET 1
LISTSETSOF 1
DELETE 1 1
LISTSET 1
CLEAR 1
LISTSET 1
Выходные данные
1 2 
1 2 
2 
-1
Входные данные
10 10
5
ADD 1 1
LISTSET 10
LISTSET 1
CLEAR 1
LISTSET 1
Выходные данные
-1
1 
-1
#111772
Кордон
  
Темы: [Потоки]
ограничение по времени на тест
5.0 second;
ограничение по памяти на тест
128 megabytes

В одной из звездных систем Галактической Республики произошло дерзкое ограбление банка "13-е Общество межгалактического кредита", из которого было похищено несколько миллиардов буказоидов. Оказалось, что Армия Республики в данном секторе имеет ограниченные силы и не в состоянии блокировать все возможные пути бегства грабителей, поэтому встала задача о минимизации числа кордонов.

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

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

Первым числорм в потоке входных данных задается общее число N всех звездных систем в галактике (2 ≤ N ≤ 1000). Мы будем предполагать, что все звездные системы пронумерованы от 1 до N. Система, в которой произошло ограбление, имеет номер 1. Далее вводится целое число H, обозначающее количество систем, в которых грабители могут укрыться. Затем перечисляются H целых чисел si (1 ≤ i ≤ H), задающее неповторяющиеся номера звездных систем (2 ≤ si ≤ N) укрытия. После этого вводится число T транспортных коридоров в галактике. Каждый транспортный коридор j (1 ≤ j ≤ T) задается парой целых чисел fj, tj (fj ≠ tj) – номеров звёздных систем, которые он соединяет. Транспортный коридор работает только в одном направлении от системы fj к системе tj. Любая пара звёздных систем может быть соединена максимум одним транспортным коридором. Транспортная сеть такова, что от системы 1 ко всем система sj существует путь, проходящий по транспортным коридорам.

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

Напечатайте сначала целое число M – минимальное количество необходимых кордонов. Затем напечатайте M транспортных коридоров, которые должны быть заблокированы. Каждый транспортный коридор должен быть выведен как пара целых чисел fk, tk.

Примеры
Входные данные
5
1 5
6 1 2 1 3 2 3 2 4 3 4 4 5
Выходные данные
1
4 5
#111773
Военные учения
  
Темы: [Деревья]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
16 megabytes
В ходе недавних военных учений министр обороны Советской Федерации товарищ Иванов имел возможность лично убедиться в блестящей боевой готовности солдат вверенной ему Советской Армии. Но одна вещь всё же продолжала беспокоить выдающегося военачальника. Прославленный генерал понимал, что была продемонстрирована лишь физическая подготовка солдат. Теперь настало время организовать очередные учения и проверить интеллектуальные способности личного состава. Генерал Шульман, вновь назначенный ответственным за проведение учений, пожертвовал все выделенные деньги бедным и с чистой совестью лёг спать. Во сне генералу явился учебник по тактике и изложил схему, руководствуясь которой можно провести учения совершенно бесплатно.

В соответствии с этой схемой учения делятся на N раундов, в течение которых N солдат, последовательно пронумерованных от 1 до N, маршируют друг за другом по кругу, т.е. первый следует за вторым, второй за третьим, ..., (N-1)-й за N-м, а N-й за первым. В каждом раунде очередной солдат выбывает из круга и идёт чистить унитазы, а оставшиеся продолжают маршировать. В очередном раунде выбывает солдат, марширующий на K позиций впереди выбывшего на предыдущем раунде. В первом раунде выбывает солдат с номером K. Разумеется, г-н Шульман не питал никаких надежд на то, что солдаты в состоянии сами определить очерёдность выбывания из круга. «Эти неучи даже траву не могут ровно покрасить», – фыркнул он и отправился за помощью к прапорщику Шкурко.


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

Единственная строка содержит целые числа N (1 ≤ N ≤ 100000) и K (1 ≤ K ≤ N).


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

Вывести через пробел номера солдат в порядке их выбывания из круга.
Примеры
Входные данные
5 3
Выходные данные
3 1 5 2 4
#111774
Суффиксы
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Назовём строкой последовательность из маленьких букв латинского алфавита. Строкой, например, является пустая последовательность, слово «aabaf» или бесконечная последовательность букв «a».

i-ый суффикс Si строки S — это строка S, из которой вырезаны первые i букв; так, для строки S = aabaf суффиксы будут такими:

  1. S0 = aabaf
  2. S1 = abaf
  3. S2 = baf
  4. S3 = af
  5. S4 = f
  6. S5 = S6 = S7 = ... = «»

Суффиксы определены для всех i \(\ge\) 0.

Циклическое расширение S *  конечной строки S — это строка, полученная приписыванием её к самой себе бесконечное количество раз. Так,

  1. S *  = S * 0 = aabafaabafaabafaa...
  2. S * 1 = abafabafabafabaf...
  3. S * 2 = bafbafbafbafbafb...
  4. S * 3 = afafafafafafafaf...
  5. S * 4 = ffffffffffffffff...
  6. S * 5 = S * 6 = S * 7 = ... = ""

По заданной строке S выясните, сколько её суффиксов Si имеют такоей же циклическое расширениe, как и строка S, то есть количество таких i, что S *  = S * i.

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

В первой и единственной строке входного файла задана строка S, состоящая из не менее, чем одной, и не более, чем 100000 маленьких латинских букв 'a'-'z'.

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

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

Примеры
Входные данные
aa
Выходные данные
2
Входные данные
ab
Выходные данные
1
Входные данные
qqqq
Выходные данные
4
Входные данные
xyzzyxy
Выходные данные
1
Страница: << 454 455 456 457 458 459 460 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест