--->
10 задач
<---
Источники
#426
Темы:
[Конечные автоматы]
[Алгоритмы на строках]
Необходимо удалить из текста строки, в которых содержатся слова, содержащие не более 3 одинаковых символов.
Максимальное время работы на одном тесте: 2 секунды
Телевидение Флатландии готовится показать в вечернем эфире выступление одного известного политика. Поскольку политик известен своей несдержанностью, решено было написать специальную программу, которая вырезала бы из речи политика некоторые фразы, запуская в этот момент рекламу.
Поскольку ввести все неполиткорректные слова в программу представляется довольно сложным, решено было использовать эвристический алгоритм определения адекватности фразы.
Речь политика в реальном времени оцифровывается, распознается и подается на вход программе как последовательность фраз. Каждая фраза состоит из слов, записанных в одну строку. Слово представляет собой последовательность символов, ограниченную с обеих сторон границами фразы, пробелами или знаками препинания (символами «.», «!», «?», «:», «-», «,», «;», «(» или «)»).
Слово считается подозрительным, если в него входит не более трех различных букв (любой символ, кроме пробелов и знаков препинания считается буквой, большие и маленькие буквы считаются различными). Например, слова «дом», «мама» или «шалаш» являются подозрительными, а слова «привет», «Шалаш» или «hello» – нет.
Фраза считается подозрительной, если не менее половины слов в ней подозрительны (каждое вхождение слова во фразу считается отдельно).
Напишите программу, которая процензурирует речь политика, удалив из нее все подозрительные фразы.
Формат входных данных
Вводится не более 1000 фраз, каждая из которых представляет собой строку не длиннее 250 символов. Фраза содержит только символы с ASCII кодами от 32 до 255.
Формат выходных данных
Выведите все фразы из входных данных, которые не являются подозрительными. Фразы следует выводить в том же порядке, в котором они поступали на вход программы.
Примеры
| Входные данные | Выходные данные |
Наша система власти достаточно стабильна. | Наша система власти достаточно стабильна. |
#522
Темы:
[Конечные автоматы]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Электронная таблица представляет собой прямоугольную таблицу, левая и верхняя граница которой зафиксированы, а правая и нижняя отсутствуют, таким образом, таблица бесконечна вправо и вниз. В каждой ячейке таблицы может быть записано какое-либо значение. Значение ячейки – это произвольная последовательность символов с кодами от 32 до 126.
При сохранении таблицы в файл она записывается в специальном формате. Ячейки перечисляются в файле, начиная с левой верхней, по строкам сверху вниз, внутри строки слева направо. В каждой строке перечисляется несколько подряд идущих ячеек, начиная с первой, при этом заведомо перечисляются все непустые ячейки данной строки. Всего в файл выводится несколько подряд идущих строк, начиная с первой, при этом выводятся, как минимум, все строки, в которых содержится хотя бы одна непустая ячейка.
Значения соседних ячеек при записи в файл разделяются между собой символом ","(запятая), строки таблицы отделяются друг от друга символом ";" (точка с запятой). После последней клетки идет символ "." (точка). За каждым из этих символов может немедленно следовать один перевод строки, который должен игнорироваться. Другие переводы строки во файле не встречаются.
Если в значении ячейки встречается один из символов ",", ";", ".'"или "\", то в файл записывается два символа – сначала "\", а затем данный символ. Соответственно, запятая, точка с запятой и точка, которые идут непосредственно после "\", не являются разделителями значений ячеек. В частности, после них не может следовать перевода строки.
Каждая ячейка относится к одному из трех типов: числовая, строковая, пустая. Пустая ячейка – это ячейка, значение которой является пустой строкой. Числовая ячейка содержит целое число из диапазона от -32768 до 32767 включительно. Число должно быть записано без ведущих нулей и лишних знаков "+" или "-" (знак "-'" должен быть только у отрицательных чисел, причем ровно один). Любая другая ячейка относится к строковому типу. Так, например, к строковому типу относятся ячейки, содержащие следующие значения: 01 (включает ведущий нуль), 55000 (не входит в указанный диапазон), а также ячейка, содержащая один символ "пробел".
Столбец таблицы называется пустым, если все ячейки, которые он содержит – пустые. Столбец таблицы называется числовым, если он содержит только числовые и пустые ячейки. В противном случае столбец называется строковым. Требуется для каждого столбца таблицы, начиная с первого, и до последнего непустого, определить, к какому типу он относится.
Входные данные
На вход программы поступает электронная таблица, размер входных данных не превышает 32767 байт.
Выходные данные
Для всех столбцов, начиная с первого, и до последнего непустого столбца, выведите их тип, разделив значения запятыми, и в конце поставьте точку. В качестве типа столбца выведите одно из следующих значений: "EMPTY'', если столбец является пустым, "NUMBER'', если столбец является числовым, "STRING'', если столбец является строковым.
Пояснение к первому примеру
Таблица для первого примера приведена ниже. Символ "пробел" обозначен как □
Примеры
Входные данные
;,12;,, ; ;,17,2,,-1\.0.
Выходные данные
EMPTY,NUMBER,STRING,EMPTY,STRING.
Входные данные
.
Выходные данные
.
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Напишите программу, моделирующую работу детерминированного конечного автомата (ДКА). Описание автомата и входная строка вводятся на стандартном потоке ввода. Результат работы автомата над данной строкой выводится на стандартный поток вывода.
Входные данные
Описание автомата задаётся в следующей форме. Сначала задаётся функция перехода автомата. Функция перехода задаётся в виде троек CUR CHAR NEW, где CUR — идентификатор исходного состояния — произвольная символьная строка, не содержащая пробельные символы. CHAR — символьная строка длиной ровно 1 символ. NEW — идентификатор целевого состояния — произвольная символьная строка, не содержащая пробельные символы. Элементы описания перехода могут отделятся друг от друга произвольным количеством пробельных символов. Описание функции перехода завершается строкой "END" в качестве идентификатора исходного состояния. Элементы CHAR и NEW отсутсвуют.
Далее перечисляются заключительные состояния автомата. Каждое состояние — это символьная строка. Список состояний завершается символьной строкой "END". Далее задаётся начальное состояние автомата — символьная строка. Затем задаётся проверяемое слово — символьная строка. Все элементы входного файла могут отделяться друг от друга произвольным количеством пробельных символов. Можете предполагать, что входные данные корректны, то есть удовлетворяют спецификации и действительно задают детерминированный конечный автомат.
Выходные данные
Результат работы автомата должен быть напечатан в следующем виде. Сначала напечатайте число 1, если данный автомат допускает данную цепочку, и 0 в противном случае. Затем напечатайте количество символов, прочитанных во входной цепочке к моменту принятия автоматом решения. Наконец, напечатайте идентификатор состояния, в котором в данный момент находился автомат.
Примеры
Входные данные
S a S END S END S aaaa
Выходные данные
1 4 S
Входные данные
S a S END S END S aaaba
Выходные данные
0 3 S
#1127
Темы:
[Конечные автоматы]
Источники:
[
Командные олимпиады,
Командные чемпионаты школьников Санкт-Петербурга по программированию,
1999,
Задача E
]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Компания MacroHard разработала новый язык программирования PASCAL++. В этом языке имеется оператор вывода PrintLn, с помощью которого можно выводить строки любой длины. По стандарту языка, разработанному специалистами компании, некоторые комбинации символов в строке должны при выводе играть особую роль:
| Комбинация | Значение |
| \n | Переход на новую строку |
| \t | Вывод K пробелов (\(1\leq K \leq 7\))), после чего курсор оказывается на позиции, имеющей номер вида \(7N+1\) (первая позиция каждой строки имеет номер 1). |
| \\ | Вывод символа "\". |
| \XY где X и Y – шестнадцатеричные цифры (0..9, A..F или a..f), причем XY20 | Вывод символа, имеющего ASCII код XY |
Например, строка "New line\ntab\tslash\\\nA char \41, rus Б \81" должна была быть напечатана в следующем виде :
-
Напечатано
Здесь пробелы для наглядности обозначены символами
New line
tab slash\
A char A, rus Б Б
Newline
tabslash\
AcharA,rusББ
К сожалению, главный программист забыл добавить в компилятор правильную процедуру форматирования. Поэтому строки выводятся прямо так, как они были записаны. Ваша задача состоит в том, чтобы преобразовать файл, полученный в результате выполнения одного или нескольких операторов PrintLn к форме, которая была задумана.
Входные данные
Входной файл содержит одну или несколько строк, каждая из которых является результатом работы неправильного оператора PrintLn. Размер файла не превышает 100000 байт.
(Все символы "\", встречающиеся во входном файле участвуют в создании какой-либо ключевой комбинации, т.е. сразу после любой последовательности, состоящей из нечетного количества подряд идущих символов "\", следует символ из набора {"n", "t", "\", "0".."9", "A".."F", "a".."f" }, причем в случае символа из множества {"0".."9", A".."F", "a".."f"}, затем следует еще один символ из этого множества.)
Выходные данные
Выведите в выходной файл, как выглядел бы данный текст, если бы он был перобразован по соответствующим правилам языка PASCAL++.
Примеры
| Входные данные | Выходные данные |
| New line\ntab\tslash\\ A char \41, rus Б \81 | New line tab slash\ A char A, rus Б Б |
#1202
Темы:
[Конечные автоматы]
[НОД и алгоритм Евклида]
Источники:
[
Личные олимпиады,
Всероссийская олимпиада школьников,
Окружная олимпиада,
2006,
2 тур,
Задача A
]
Выбрано
:
|