1517. Свобода выбора
Ограничение времени: 2.0 секунды Ограничение памяти: 64 МБ
Вступление
Не успели жители Албании привыкнуть к свободе слова (более подробно эта история описана в задаче «Свобода слова»), как им на голову свалилась ещё и свобода выбора. В самом ближайшем будущем населению предстоит пережить первые в истории страны демократические президентские выборы.
О намерении бороться за высокий пост уже объявили два самых ярких албанских политика последних лет – либерал Мухаммед Тахир-оглы и его извечный оппонент консерватор Ахмед Касым-бей.
Задача
Следуя демократическим традициям, перед выборами оба кандидата развлекаются тем, что выливают друг другу на головы тонны грязи под одобрительные возгласы избирателей. Каждый кандидат при любом удобном случае произносит предвыборную речь, в которой обвиняет своего политического оппонента в коррупции, неуважении к старшим, пособничестве террористам и вообще всячески демонстрирует своё уважение к противнику. В результате выступления Мухаммеда и Ахмеда стали похожи друг на друга до такой степени, что избирателям теперь вообще до лампочки, за кого голосовать.
Этим хочет воспользоваться третий кандидат в президенты – председатель социалистической партии Албании товарищ Ктулху. Он поленился написать себе предвыборную речь, но между тем заметил, что некоторые фрагменты выступлений г-на Тахир-оглы и г-на Касым-бея полностью совпадают. Тогда тов. Ктулху решил взять самый длинный совпадающий фрагмент и сделать его своей предвыборной речью.
Исходные данные
Первая строка содержит целое число N (1 ≤ N ≤ 100000). Вторая строка содержит речь г-на Тахир-оглы. Третья строка содержит речь г-на Касым-бея. Каждая речь состоит из N заглавных латинских букв.
Результат
Вывести речь тов. Ктулху. Если задача имеет несколько решений, то вывести любое из них.
Пример
исходные данные |
результат |
28 VOTEFORTHEGREATALBANIAFORYOU CHOOSETHEGREATALBANIANFUTURE |
THEGREATALBANIA |
Автор задачи: Илья Гребнов, Никита Рыбак, Дмитрий Ковалёв Источник задачи: Timus Top Coders: Third Challenge
Метки: строковые алгоритмы (
Начало формы
скрыть метки для нерешенных задач
Конец формы
)
Сложность: 389
1490. Огненный круг
Ограничение времени: 1.0 секунды Ограничение памяти: 64 МБ
Лич Сандро проводит свои научные исследования в магии огня. Сандро стоит в центре огромного квадратного зала площадью миллион квадратных километров, сплошь замощённого квадратными каменными плитами со стороной один метр. По взмаху посоха вокруг Сандро возникает огненный круг радиуса R метров. Центр круга совпадает с центром зала и находится в месте соприкосновения четырёх плит. Сандро хочет посчитать, сколько плит будет испорчено огнем. Считается, что плита испорчена, если она имеет хотя бы две общие точки с кругом. На рисунке в качестве примера изображены плиты, испорченные огненным кругом радиуса 4:
Исходные данные
В единственной строке записано целое число R > 0 — радиус огненного круга. R не превосходит 105.
Результат
Выведите целое число — количество испорченных плит.
Примеры
исходные данные |
результат |
2 |
16 |
4 |
60 |
Автор задачи: Александр Ипатов Источник задачи: XIII командный чемпионат школьников Свердловской области по программированию (14 октября 2006 года)
Метки: нет (
Начало формы
скрыть метки для нерешенных задач
Конец формы
)
Сложность: 229
1732. Министерство правды
Ограничение времени: 1.0 секунды Ограничение памяти: 64 МБ
Бело-чёрным по чёрно-белому написано изречение, подвергшееся цензуре со стороны Министерства правды. Автор его уже исчез вместе с историей о нём, и, пока Большой Брат наблюдает за кем-то другим, вам, как рядовому сотруднику миниправа, поручено стереть из изречения часть букв так, чтобы получилось другое, одобренное министерством, изречение.
Министерство правды называет словом непустую последовательность латинских букв, а изречением — последовательность из одного или более слов, разделённых одним или несколькими пробелами. Пробелы также могут стоять перед первым и за последним словом изречения. Для сравнения двух изречений нужно сначала удалить все начальные и конечные пробелы, затем все блоки подряд идущих пробелов заменить на один пробел. Изречения считаются одинаковыми, если получившиеся строки совпадут. Когда сотрудник стирает букву в изречении, она заменяется на пробел.