--->
35 задач
<---
Источники
Компания "Макрохард" заказала у одного известного психолога полное психологическое обследование всех работников компании. Психолог, привлеченный для проведения обследования, известен своим инновационным методом, позволяющим составить полную психологическую картину сотрудника по наиболее часто используемому им в программах идентификатору. Однако, к сожалению, программа, используемая в анализе, оказалась неожиданно испорчена вирусом, поэтому требуется срочно написать новую. Помогите известному психологу. Напишите программу, которая по приведенной программе выяснит наиболее часто используемый в ней идентификатор.
Поскольку разные сотрудники компании пишут программы на разных языках программирования, ваша программа должна уметь работать с произвольным языком. Поскольку в разных языках используются различные ключевые слова, то список ключевых слов в анализируемом языке предоставляется на вход программе. Все последовательности из латинских букв, цифр и знаков подчеркивания, которые не являются ключевыми словами и содержат хотя бы один символ, не являющийся цифрой, могут быть идентификаторами. При этом в некоторых языках идентификаторы могут начинаться с цифры, а в некоторых - нет. Если идентификатор не может начинаться с цифры, то последовательность, начинающаяся с цифры, идентификатором не является. Кроме этого, задано, является ли язык чувствительным к регистру символов, используемых в идентификаторах и ключевых словах.
В первой строке вводятся число n - количество ключевых слов в языке (0 <= n <= 50) и два слова C и D, каждое из которых равно либо "yes", либо "no". Слово C равно "yes", если идентификаторы и ключевые слова в языке чувствительны к регистру символов, и "no", если нет. Слово D равно "yes", если идентификаторы в языке могут начинаться с цифры, и "no", если нет.
Следующие n строк содержат по одному слову, состоящему из букв латинского алфавита и символов подчеркивания - ключевые слова. Все ключевые слова непусты, различны, при этом, если язык не чувствителен к регистру, то различны и без учета регистра. Длина каждого ключевого слова не превышает 50 символов.
Далее до конца входных данных идет текст программы. Он содержит только символы с ASCII-кодами от 32 до 126 и переводы строки.
Размер входных данных не превышает 10 килобайт. В программе есть хотя бы один идентификатор.
Выведите идентификатор, встречающийся в программе максимальное число раз. Если таких идентификаторов несколько, следует вывести тот, который встречается в первый раз раньше. Если язык во входных данных не чувствителен к регистру, то можно выводить идентификатор в любом регистре.
0 yes no
int main() {
int a;
int b;
scanf("%d%d", &a, &b);
printf("%d", a + b);
}
int
0 yes no
#define INT int
int main() {
INT a, b;
scanf("%d%d", &a, &b);
printf("%d %d", a + b, 0);
}
d
6 no no program var begin end while for program sum; var A, B: integer; begin read(A, b); writeln(a + b); end.
a
1 yes yes _ a = 0h b = 0h c = 0h
0h
Будем называть цепочкой слов длины n последовательность слов \(w_1\), \(w_2\), …, \(w_n\), такую, что для всех \(i\) от 1 до \(n\) – 1 слово \(w_i\) является собственным префиксом слова \(w_i\)+1.
Слово \(u\) длины \(k\) называется собственным префиксом слова \(v\) длины \(l\), если \(l\) > \(k\) и первые \(k\) букв слова \(v\) совпадают со словом \(u\). Например, «program» является собственным префиксом слова «programmer».
Задано множество слов \(S\) = {\(s_1\), \(s_2\), …, \(s_m\)} и последовательность чисел \(x\)[1], \(x\)[2], …, \(x\)[\(k\)]. Требуется найти такие числа \(l\) и \(r\) (\(l\) ≤ \(r\)), что \(s_x\)[\(l\)], \(s_x\)[\(l\) + 1], …, \(s_x\)[\(r\) – 1], \(s_x\)[\(r\)] является цепочкой слов, и количество слов в цепочке (число \(r\) – \(l\) + 1) максимально.
Первая строка входного файла содержит целое число \(m\) (1 ≤ \(m\) ≤ 250 000). Каждая из следующих \(m\) строк содержит по одному слову из множества \(S\).
Все слова не пусты, имеют длину, не превосходящую 250 000 символов, и состоят только из строчных букв латинского алфавита. Суммарная длина всех слов не превосходит 250 000.
Следующая строка содержит число \(k\) (1 ≤ \(k\) ≤ 250 000). Последняя строка входного файла содержит \(k\) чисел — последовательность чисел \(x\)[1], \(x\)[2], …, \(x\)[\(k\)] (для всех \(i\) выполнено 1 ≤ \(x\)[\(i\)] ≤ \(m\)).
Выведите в первой строке выходного файла два числа: \(l\) и \(r\). Если оптимальных ответов несколько, выведите любой из них. Разделяйте числа пробелом.
3 zngs rjzr zng 3 3 1 1
1 2
6 gjnuitvaowpy gjnuitvaowpym gjnuitvaowp rjzrociinzeco tgbotnzepnvm aigqbzpnerv 9 2 3 1 2 3 1 2 3 1
2 4
Реализуйте структуру данных типа “множество строк”. Хранимые строки – непустые последовательности длиной не более 10 символов, состоящие из строчных латинских букв. Структура данных должна поддерживать операции добавления строки в множество, удаления строки из множества и проверки принадлежности данной строки множеству. Максимальное количество элементов в хранимом множестве не превосходит 106.
Каждая строка входных данных задает одну операцию над множеством. Запись операции состоит из типа операции и следующей за ним через пробел строки, над которой проводится операция. Тип операции – один из трех символов: + означает добавление данной строки в множество; - означает удаление строки из множества; ? означает проверку принадлежности данной строки множеству. Общее количество операций во входном файле не превосходит 106. Список операций завершается строкой, в которой записан один символ # – признак конца входных данных. При добавлении элемента в множество НЕ ГАРАНТИРУЕТСЯ, что он отсутствует в этом множестве. При удалении элемента из множества НЕ ГАРАНТИРУЕТСЯ, что он присутствует в этом множестве.
Программа должна вывести для каждой операции типа ? одну из двух строк YES или NO, в зависимости от того, встречается ли данное слово в нашем множестве.
+ hello + bye ? bye - bye ? bye ? hello #
YES NO YES
Знаменитый художник Вася только что закончил работу над своим новым шедевром и хочет знать, сколько он сможет получить за свой труд.
Картина представляет собой прямоугольник N на M сантиметров, разделенный на маленькие квадратики 1 на 1 сантиметр со сторонами, параллельными сторонам картины. Для достижения гармонии каждый из этих квадратиков Вася покрасил одним из 26 особых цветов, обозначаемых маленькими латинскими буквами.
Стоимость картины в точности равна количеству «симпатичных» частей в ней. Частью картины называется любой прямоугольник, который может быть вырезан из нее по границам квадратиков. Часть называется «симпатичной», если при выполнении симметрии относительно ее центра получается прямоугольник, раскрашенный также, как и исходная часть. Например, в картине, раскрашенной так:
abc
acb
симпатичными являются все части, состоящие из одного квадратика (их 6), а также части
bc и a
cb и a
Напишите программу, которая по информации о шедевре Васи определит его стоимость.
В первой строке содержатся два числа N и M (1 ≤ N, M ≤ 100). В следующих N строках идут строки, состоящие из M маленьких латинских символов. Символ в i-й строке j-м столбце определяет цвет соответствующего квадратика картины.
Выведите стоимость шедевра — количество частей, симметричных относительно своего центра.
Комментарии к примерам тестов
Этот пример разобран в условии
Симпатичными являются шесть частей 1x1, одна часть 1x2 и сама картина.
Частичные ограничения
Первая группа состоит из тестов, в которых N, M ≤ 15. Данная группа оценивается в 30 баллов.
Вторая группа состоит из тестов, в которых N, M ≤ 50. Данная группа оценивается в 30 баллов.
2 3 abc acb
8
3 2 ab cc ba
8
Строка называется палиндромом, если она читается одинаково как слева направо, так и справа налево. Например, строки abba, ata являются палиндромами.
Дана строчка. Ее подстрокой называется некоторая непустая последовательность подряд идущих символов. Напишите программу, которая определит, сколько подстрок данной строки является палиндромами.
Вводится одна строка, состоящая из маленьких латинских букв. Длина строки не превышает 100000 символов.
Выведите одно число — количество подстрок данной строки, являющихся палиндромами
aaa
6
aba
4