Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 
[Положение] [Расписание] [Архив] [Содержание] [Задачи] [Рейтинг]

Задачи олимпиады "Девятая личная олимпиада"

Задача A. Криптограмма

(Время: 1 сек. Память: 16 Мб Баллы: 100)

На одной из лекций по информатике студент Петя узнал про новый шифр - простой замены. Он и на самом деле прост: в тексте каждая буква алфавита заменяется некоторой другой буквой того же алфавита (может быть, той же самой).

Петя написал письмо своему другу Васе. Письмо - это текст из нескольких строк, написанный на английском языке, с использованием только строчных английских букв и пробелов. В произвольное место, отдельной строкой Петя вставил ключевую фразу: "the quick brown fox jumps over the lazy dog", о которой они с Васей договорились заранее. После чего зашифровал письмо. Известно, что пробелы в письме не шифруются. Получив такое письмо, Вася сумеет его расшифровать и прочесть. Иногда Петя ошибается, и забывает вставить ключевую фразу. Увы, в этом случае прочесть письмо невозможно.

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

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

Первая строка входного файла INPUT.TXT содержит целое число N – количество строк в письме (1 ≤ N ≤ 200). Далее идет N строк письма (пустые строки отсутствуют, в каждой строке не более 80 символов).

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

В выходной файл OUTPUT.TXT в случае присутствия в тексте ключевой фразы выведите N строк расшифрованного сообщения. Если ключевой фразы нет, следует вывести «No solution» (без кавычек).

Примеры

INPUT.TXTOUTPUT.TXT
1 3
vtz ud xnm xugm itr pyy jttk gmv xt otgm xt xnm puk ti xnm fprxq
xnm ceuob lrtzv ita hegfd tsmr xnm ypwq ktj
frtjrpgguvj otvxmdxd prm iev prmvx xnmq
now is the time for all good men to come to the aid of the party
the quick brown fox jumps over the lazy dog
programming contests are fun arent they
2 3
vtz ud xnm xugm itr pyy jttk gmv xt otgm xt xnm puk ti xnm fprxq
xnm fffff lrtzv iia wwwfd tsmr xnm ypwq ktj
frtjrpgguvj otvxmdxd prm iev prmvx xnmq
No solution

Задача B. Удаление

(Время: 1 сек. Память: 64 Мб Баллы: 100)

Вася уже долго занимается k-расширениями. Недавно ему это надоело, и он стал изучать следующую операцию на строках: сначала удаляется каждый k-ый символ строки с начала и до конца (т. е. сначала k-й, потом 2k-й, и т. д., пока число ik не превосходит длины строки). Потом эта операция повторяется, и так далее, пока в строке есть хотя бы k символов.

Например, если дана строка длины 10, и K = 2, то сначала будут удалены 2, 4, 6, 8 и 10 символы. Затем будут удалены 2 и 4 символы новой строки, которые соответствуют 3 и 7 символам старой. Затем будет удален 2 символ получившейся строки - 5 символ старой. Последним будет удален 9 символ старой строки.

Собственно, задумал он это все для того, чтобы узнать, какой и когда символ исчезнет. Но когда ему надоело вручную удалять символы, он решил поручить это Вам. А именно, Вам придется отвечать на его вопросы: "А на какой секунде был удален i-ый символ строки?" На удаление каждого символа тратится одна секунда.

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

В первой строке входного файла INPUT.TXT находятся три числа: 1 ≤ n ≤ 5•106 - количество символов, которые написал Вася, число 1 ≤ k ≤ n, и 1 ≤ l ≤ 10 000 - количество вопросов, которые задает Вася. В последующих l строках указаны номера символов, для которых Вася хочет узнать, когда они были удалены. Все номера лежат в пределах от 1 до n и могут повторяться.

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

В выходной файл OUTPUT.TXT выведите l строк с ответами на вопросы в том порядке, в каком они были во входном файле. Если окажется, что символ из строки не будет удален никогда, выведите 0.

Пример

INPUT.TXTOUTPUT.TXT
110 2 6
1
2
3
5
10
5
0
1
6
8
5
8

Задача C. Заклинание Ауэрса

(Время: 1 сек. Память: 16 Мб Баллы: 100)

Заклинание Ауэрса представляет собой набор звуков, записываемых малыми буквами английского алфавита без пробелов. Сам по себе этот набор не обладает ни секретностью, ни магической силой и приведен во всех учебниках по белой магии в соответствующем разделе. Там же указан способ его применения:

а) разбить набор букв на палиндромы, то есть непустые слова, которые читаются одинаково как справа налево, так и слева направо;

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

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

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

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

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

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

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

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

Примеры

INPUT.TXTOUTPUT.TXT
1baobab4
b
a
o
bab
2aaaaa1
aaaaa
3rarabar3
rar
aba
r

Задача D. Фруктовый сок

(Время: 1 сек. Память: 32 Мб Баллы: 100)

Женя недавно купил себе новую соковыжималку. Теперь по утрам он и его братья и сестры пьют свежевыжатый фруктовый сок. А это, между прочим, очень полезно! Недавно они поняли, что можно пить сок, выжатый не только из одного вида фруктов, как, например, апельсиновый, но и различные смеси, например, виноградно-яблочный.

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

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

Основная проблема состоит в том, что эту емкость иногда приходится мыть. Например, если после приготовления апельсинового сока, необходимо приготовить яблочный, то емкость надо мыть, иначе получится апельсиново-яблочный сок. Более формально, пусть сок A состоит из компонентов a1, ... , an, а сок B - из компонентов b1, ... , bm. Сок B можно готовить после сока A, если любой из компонентов сока A является компонентом сока B. В противном случае емкость для сока надо помыть.

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

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

Первая строка входного файла INPUT.TXT содержит натуральное число N – количество различных соков, которые требуется приготовить (N ≤ 300). Каждая из последующих N строк описывает один из соков. Описание сока состоит из числа k его компонентов (1 ≤ k ≤ 300) и списка этих компонентов. Каждый из компонентов сока описывается словом длиной до 30 символов из строчных и прописных букв английского алфавита. Прописные и строчные буквы различаются. Различные компоненты имеют различные названия.

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

В выходной файл OUTPUT.TXT выведите минимальное количество раз, которое Жене придется помыть емкость для сока. Учитывайте при этом, что емкость для сока надо помыть и после приготовления последней порции сока.

Примеры

INPUT.TXTOUTPUT.TXT
14
1 Apple
2 Apple Orange
1 Orange
2 Orange Pineapple
2
23
1 Apple
1 Orange
1 Mango
3


Красноярский краевой Дворец пионеров, (c)2006 - 2018, ICQ: 151483, E-mail: admin@acmp.ru