--->
121 задач
<---
Источники
В этой задаче Вам требуется найти максимальную по длине подстроку данной строки, такую что каждый символ встречается в ней не более k раз.
В первой строке даны два целых числа n и k (1 ≤ n ≤ 100000, 1 ≤ k ≤ n ) , где n – количество символов в строке. Во второй строке n символов – данная строка, состоящая только из строчных латинских букв.
В выходной файл выведите два числа – длину искомой подстроки и номер её первого символа. Если решений несколько, выведите любое.
3 1 abb
2 1
5 2 ababa
4 1
Летом Максим съездил в Летнюю Какую-то Школу, где, помимо учёбы, ему очень запомнилась игра «Шляпа», в которую он вместе с друзьями играл всю смену. Опишем правила игры, которых они придерживались. Обратите внимание: эти правила немного отличаются от общепринятых.
Изначально в шляпу помещают некоторое количество бумажек с написанными на них словами. После этого команды из двух человек по очереди и в случайном порядке начинают отгадывать слова - один член команды объясняет другому написанное на бумажке слово, не используя однокоренные. Если партнёр отгадывает его, то команде засчитывается одно очко, слово выкидывается, а команда достаёт из шляпы новое, если у неё ещё осталось время в этом раунде. Если команда не успевает отгадать очередное слово, то бумажка на которой оно написано, возвращается в шляпу, и ход передаётся какой-то случайной команде, возможно, той же самой. Игра продолжается, пока все слова из шляпы не будут отгаданы.
Теперь Максим провёл турнир для N команд из своей школы и должен определить победителя. Он неаккуратно вёл записи игры и не отмечал, сколько слов отгадала каждая из команд, зато он записывал в хронологическом порядке каждый раз, когда какая-либо команда доставала какую-либо бумажку из шляпы. Всего таких записей M, и они следуют в хронологическом порядке. Помогите Максиму восстановить по сделанным записям, сколько слов отгадала каждая из команд.
В первой строке дано количество команд N и количество попыток отгадать слова M (1 ≤ N ≤ 100 000, 1 ≤ M ≤ 100 000). В следующих M строках сначала указывается номер ni команды, пытавшейся отгадать слово, а через пробел дано слово wi, написанное на бумажке. Номера команд лежат в диапазоне от 1 до N. Все слова wi состоят из строчных латинских букв и имеют ненулевую длину, не превосходящую 10 букв.
Выведите в одну строку N чисел, i-ое число должно равняться количеству слов, отгаданному i-ой командой.
2 3
1 hat
1 shirt
2 hat
1 1
3 2
1 mom
3 dad
1 0 1
В первом примере первая команда отгадала слово shirt, а вторая слово hat.
Каждый тест в данной задаче оценивается отдельно. Решение тестируется на основном наборе тестов только при прохождении всех тестов из условия. При этом тесты из условия не оцениваются.
Подзадача 1. 1 ≤ N ≤ 2000, 1 ≤ M ≤ 2000. Каждое слово встречается только один раз. Оценивается из 20 баллов.
Подзадача 2. 1 ≤ N ≤ 2000, 1 ≤ M ≤ 2000. Оценивается из 30 баллов.
Подзадача 3. 1 ≤ N ≤ 100 000, 1 ≤ M ≤ 100 000. Оценивается из 50 баллов.
Даны три строки, состоящие из строчных латинских букв. С этими строками можно производить следующие операции: либо заменить один символ строки на два таких же символа (например, заменить символ «a» на «aa»), либо, наоборот, заменить два подряд идущих одинаковых символа на один такой же символ.
Необходимо при помощи этих операций сделать все три строки равными какой-то другой общей строке S либо определить, что это сделать невозможно. При этом нужно минимизировать общее количество операций.
Программа получает на вход три строки, состоящие из строчных букв латинского алфавита. Длина каждой строки не превышает 100 символов.
Если при помощи указанных операций возможно сделать все три строки равными, выведите такую строку S , что суммарное число операций, необходимых для преобразования всех трёх данных строк к строке S , будет минимальным. Если этого сделать нельзя, программа должна вывести одно слово IMPOSSIBLE (заглавными буквами).
Решение, которое выводит правильный ответ только на тестах из условия и тех тестах, на которых ответом является слово IMPOSSIBLE, будет оцениваться в 0 баллов.
aaaza aazzaa azzza
aazza
xy xxyy yx
IMPOSSIBLE
Как известно, в шахматах горизонтальные строки обозначаются цифрами от 1 до 8, считая от расположения белых фигур, стоящих внизу доски, а вертикальные столбцы – буквами латинского алфавита: A, B, C, D, E, F, G, H.
На шахматной доске в клетке с заданными координатами находиться конь. Для клетки А1 после первого хода возможно перемещение коня на клетку С2 или В3.
Требуется написать программу, которая определяет координаты всех клеток, куда можно пойти конём первым ходом.
В единственной входной строке записано обозначение исходной позиции коня на шахматной доске.
В единственной строке должны быть записаны через пробел обозначения всех клеток, в которые может переместиться конь после первого хода. Клетки выводятся в следующем порядке: вначале клетки первого ряда слева – направо, далее клетки второго ряда и т.д.
A1
C2 B3
Как известно, в шахматах горизонтальные строки обозначаются цифрами от 1 до 8, считая от расположения белых фигур, стоящих внизу доски, а вертикальные столбцы – буквами латинского алфавита: A, B, C, D, E, F, G, H.
На шахматной доске в клетке с заданными координатами находиться конь. Сначала делается первый ход конём, а затем – второй ход. Например, для клетки А1 после первого хода возможно перемещение коня на клетку С2 или В3, а после второго хода – на клетки А1, Е1, А3, Е3, В4, D4.
Требуется написать программу, которая определяет координаты всех клеток, куда можно прийти конём за два хода.
В единственной входной строке записано обозначение исходной позиции коня на шахматной доске.
В единственной строке должны быть записаны через пробел обозначения всех клеток, в которые может переместиться конь после второго хода. Клетки выводятся в следующем порядке: вначале клетки первого ряда слева – направо, далее клетки второго ряда и т.д.
A1
A1 C1 E1 D2 A3 E3 B4 D4 A5 C5