#426

Цензура

Темы: [Конечные автоматы] [Алгоритмы на строках]

Источники: [ Командные олимпиады, ВКОШП, 2004, Задача D ]

Необходимо удалить из текста строки, в которых содержатся слова, содержащие не более 3 одинаковых символов.

Максимальное время работы на одном тесте: 2 секунды

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

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

Речь политика в реальном времени оцифровывается, распознается и подается на вход программе как последовательность фраз. Каждая фраза состоит из слов, записанных в одну строку. Слово представляет собой последовательность символов, ограниченную с обеих сторон границами фразы, пробелами или знаками препинания (символами «.», «!», «?», «:», «-», «,», «;», «(» или «)»).

Слово считается подозрительным, если в него входит не более трех различных букв (любой символ, кроме пробелов и знаков препинания считается буквой, большие и маленькие буквы считаются различными). Например, слова «дом», «мама» или «шалаш» являются подозрительными, а слова «привет», «Шалаш» или «hello» – нет.

Фраза считается подозрительной, если не менее половины слов в ней подозрительны (каждое вхождение слова во фразу считается отдельно).

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

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

Вводится не более 1000 фраз, каждая из которых представляет собой строку не длиннее 250 символов. Фраза содержит только символы с ASCII кодами от 32 до 255.

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

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

Примеры

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

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

Наша система власти достаточно стабильна.
Флатландия - наша родина. Ура!
Пятая Всероссийская олимпиада школьников по информатике.
Ну вы это, того...
We are the champions!

She loves you! Yeah, Yeah, Yeah!
Хрен редьки не слаще
Спасибо за внимание.

Наша система власти достаточно стабильна.
Пятая Всероссийская олимпиада школьников по информатике.
She loves you! Yeah, Yeah, Yeah!
Хрен редьки не слаще
Спасибо за внимание.

#548

Сравнение URL

Темы: [Алгоритмы на строках]

Источники: [ Командные олимпиады, ВКОШП, 2001, Задача D ]

Необходимо проверить два URL адреса на совпадение. При этом часть адреса может опускаться и подставляться по умолчанию. Также возможны переходы /../ и /./, замена буквы 16-ричным кодом и т.д.

Для идентификации ресурсов в сети Internet используются URL (Uniform Resource Locator). URL состоит из нескольких элементов: протокол, хост, порт, путь, файл и секция. Некоторые элементы URL могут быть опущены. Рассмотрим упрощенный формат URL:

[протокол://]хост[:порт][путь/[файл[#секция]]]
Заключенные в квадратные скобки элементы могут быть опущены, т.е. например, можно не указать протокол или секцию. Но, например, если указан файл, то обязательно должен быть указан путь. Регистр букв в элементах URL не важен.

Рассмотрим кратко все элементы URL:

*Протокол - это способ доступа к файлу, URL с разными протоколами и одинаковыми остальными элементами могут указывать на различные ресурсы.
*Хост и порт - это имя некоторого сервера в сети и способ доступа к нему (порт - натуральное число, не превосходящее 65535).
*Путь представляет собой путь к файлу, содержащему запрашиваемый ресурс, от некоторого каталога на сервере, который называется корневым. При этом для разделения имен каталогов используется символ "/". Путь, если он не пуст, всегда начинается с символа "/". Специальное обозначение '.' соответствует самому каталогу, '..' - родительскому каталогу.
*Файл - это файл, содержащий запрашиваемый ресурс.
Наконец, файл может быть разбит на секции каким либо способом и можно указать, к какой именно секции вы хотите обратиться.

Различные символы в URL могут быть заменены своими шестнадцатеричными ASCII кодами с помощью символа %, например a = %41, Z = %5A. В коде всегда используется ровно две шестнадцатеричные цифры.

Некоторые символы могут встречаться в элементах URL только как шестнадцатеричные коды - все символы, кроме букв латинского алфавита, цифр и символов "." и "-", а некоторые не могут встречаться вообще: "\", "#", "*", "@", "%", "?", ":", ",", а также символы с ASCII-кодом меньше %20. Символ "/" может встречаться в элементах URL только в пути для разделения входящих в него каталогов. Имя файла не может состоять только из точек.

Рассмотрим примеры URL:

http://neerc.ifmo.ru/school
ftp://somewhere.net:1234/pub/files/coolgame.zip
nobody.nowhere.net/some%20dir/some%20file#some%20info

Ваша цель в этой задаче - помочь разработчикам web-сервера. Для web-сервера отсутствующие части URL имеют следующие значения по умолчанию:

Различные как строки URL могут указывать на один и тот же ресурс, например следующие три URL:

neerc.ifmo.ru
http://neerc.ifmo.ru:80/index.html#
Http://NEERC.IFMO.Ru/Dir/../././

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

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

Входные данные состоят из двух строк, каждая из них содержит URL. Оба URL удовлетворяют формату, приведенному в условии этой задачи. Длина каждого URL не превосходит 200 символов. Гарантируется, что ни один из промежуточных каталогов на пути к ресурсу не лежит выше корневого каталога (т.е. не может встретиться, например, URL http://somewhere.com/../dir/index.html) а также, что имена всех каталогов состоят по крайней мере из одного символа (два символа "/" не могут идти подряд в любом месте, кроме как непосредственно после двоеточия после имени протокола).

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

Выведите YES, если оба URL, приведенные во входных данных, указывают на один и тот же ресурс, и NO в противном случае.

Примеры

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

neerc.ifmo.ru
neerc.ifmo.ru:80

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

YES

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

neerc.ifmo.ru
NEERC.IFMO.RU

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

YES

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

abcdefghijklmnopqrstuvwxyz.com
ABCDEFGHIJKLMNOPQRSTUVWXYZ.COM

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

YES

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

zzz.com
zzz.net

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

NO

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

http://abcdefghijklmnopqrstuvwxyz.com
ABCDEFGHIJKLMNOPQRSTUVWXYZ.COM

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

YES

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

hello%20world.com
helloworld.com

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

NO

#870

Контрольная по ударениям

Темы: [Алгоритмы на строках]

Источники: [ Командные олимпиады, Московская командная олимпиада, 9-11 классы, 2008, Лига Б, Задача C ]

Дан словарь с расставленными в словах ударениями. Требуется определить, сколько ошибок в тексте (при этом слово, которого в словаре нет, ошибочным не считается).

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

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

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

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

Вводится сначала число N — количество слов в словаре (0≤N≤100).

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

Далее идет упражнение, выполненное Петей. Упражнение представляет собой строку текста, суммарным объемом не более 30000 символов. Строка состоит из слов, которые разделяются между собой ровно одним пробелом. Длина каждого слова не превышает 30 символов. Все слова состоят из маленьких и заглавных латинских букв (заглавными обозначены те буквы, над которыми Петя поставил ударение). Петя мог по ошибке в каком-то слове поставить более одного ударения или не поставить ударения вовсе.

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

Выведите количество ошибок в Петином тексте, которые найдет Вася.

Примеры

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

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

Комментарии

4

cAnnot

cannOt

fOund

pAge

thE pAge cAnnot be fouNd

2

В слове cannot, согласно словарю возможно два варианта расстановки ударения. Эти варианты в словаре могут быть перечислены в любом порядке (т.е. как сначала cAnnot, а потом cannOt, так и наоборот).

Две ошибки, совершенные Петей — это слова be (ударение вообще не поставлено) и fouNd (ударение поставлено неверно). Слово thE отсутствует в словаре, но поскольку в нем Петя поставил ровно одно ударение, признается верным.

4

cAnnot

cannOt

fOund

pAge

The PAGE cannot be found

4

Неверно расставлены ударения во всех словах, кроме The (оно отсутствует в словаре, в нем поставлено ровно одно ударение). В остальных словах либо ударные все буквы (в слове PAGE), либо не поставлено ни одного ударения.

#890

Интернет-банкинг

Темы: [Алгоритмы на строках]

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

Система Интернет-банкинга Bank 2.0, используемая одним Очень Крупным Банком, использует следующий способ ввода пароля. Серверной частью системы случайно генерируются \(n\) строк \(s_1, \ldots, s_n\), каждая из которых состоит из \(m\) строчных букв латинского алфавита (предполагается, что пароли состоят только из таких букв).

При вводе пароля пользователю разрешается выполнять такую операцию: выбрать из данных строк две (обозначим их как \(s_i\) и \(s_j\), \(1 \le i, j \le n\), \(i \ne j\)) и некоторую позицию \(k\) (\(1 \le k \le m\)) в них, после чего поменять местами \(k\)-е символы в \(s_i\) и \(s_j\). Например, если \(s_i=abcde\), \(s_j=vwxyz\), \(k=3\), то после выполнения этой операции будут верны следующие равенства: \(s_i=abxde\) и \(s_j=vwcyz\). Для ввода пароля пользователю необходимо за минимальное число таких операций добиться состояния, в котором хотя бы одна из строк \(s_1, \ldots, s_n\) совпадает с \(p\).

Ваша задача состоит в том, чтобы написать программу, которая по заданному набору строк \(s_1, \ldots, s_n\) и паролю пользователя \(p\) определит минимальное число операций указанного типа, которые необходимо выполнить для ввода пароля, а также найдет способ ввода пароля за такое число операций.

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

Первая строка входного файла содержит целое число \(n\) (\(2 \le n \le 100\)). Каждая из последующих \(n\) строк содержит строки \(s_1, \ldots, s_n\). Все они состоят только из строчных букв латинского алфавита и имеют одинаковую длину \(m\) (\(2 \le m \le 100\)).

Последняя строка входного файла содержит пароль пользователя \(p\). Его длина равна \(m\), и он состоит только из строчных букв латинского алфавита.

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

Первая строка выходного файла должна содержать минимальное число \(c\) операций, необходимых для ввода пароля. Если с помощью описанных в условии операций пароль ввести нельзя, то выведите в первой строке "\(-1\)".

В случае существования решения следующие \(c\) строк должны содержать описания операций. Операции должны быть перечислены в порядке их применения, каждая из строк должна содержать три целых числа: \(i\), \(j\) и \(k\) (\(1 \le i, j \le n\), \(i \ne j\), \(1 \le k \le m\)). Эти числа означают, что соответствующая операция состоит в обмене \(k\)-ых символов строк \(s_i\) и \(s_j\).

Примеры

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

3
abc
cab
bca
acb

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

2
1 3 2
1 2 3

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

3
abc
cab
bca
acd

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

-1

#998

Поле чудес

Темы: [Алгоритмы на строках]

Источники: [ Личные олимпиады, Московская олимпиада школьников, 10-11 классы, 2004, 2 день, Задача B ]

Барабан совершает несколько оборотов. Дана последовательность чисел, на которые указывает стрелка. Требуется определить сколько всего чисел на барабане (найти максимальную подпоследовательносьть, из повторов которой состоит последовательность).

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

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

После этого ведущий задал участнику вопрос: какое наименьшее число секторов может быть на барабане? Напишите программу, отвечающую на этот вопрос.

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

Во входном файле записано сначала число N — количество чисел, которое назвал ведущий (2N30000). Затем записано N чисел, на которые указывала стрелка в процессе вращения барабана. Первое число всегда совпадает с последним (в конце стрелка указывает на тот же сектор, что и в начале). Числа, записанные в секторах барабана, — натуральные, не превышающие 32000.

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

Выведите минимальное число секторов, которое может быть на барабане.

Примеры

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

13
5 3 1 3 5 2 5 3 1 3 5 2 5

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

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

4
1 1 1 1

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