Темы --> Информатика
    Язык программирования(952 задач)
    Алгоритмы(1657 задач)
    Структуры данных(279 задач)
    Интерактивные задачи(17 задач)
    Другое(54 задач)
---> 2656 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 508 509 510 511 512 513 514 >> Отображать по:
#113596
LCA
  
ограничение по времени на тест
2.5 second;
ограничение по памяти на тест
256 megabytes

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

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

В первой строке входного файла содержатся целые числа 1 ≤ N ≤ 10 4 , 0 ≤ M ≤ 10 4 — количество вершин и рёбер в графе. Далее следуют M строк по два числа от 1 до N . Пара чисел ( a , b ) означает, что из вершины a есть ребро в вершину b .

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

Выведите одно целое число — количество пар.

Примеры
Входные данные
2 1
1 2
Выходные данные
4
Входные данные
3 2
2 1
3 1
Выходные данные
7
#113597
Тяжелые палиндромы
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
512 megabytes

Палиндром - это слово, которое читается справа налево также, как слева направо. Например, "a", "abba", "anavolimilovana" - палиндромы.

Весом строки, состоящей из строчных латинских символов будем называть количество ее подстрок (слов), являющихся палиндромами (при этом каждое вхождение подстроки считается отдельно). Формально, пусть W - строка длины N . Слово w a , b - подстрока W , состоящая из символов на позициях с индексами с a по b включительно. Вес строки W - это количество пар целых чисел a , b ( 1 ≤ a , b ≤ N ) таких, что w a , b является палиндромом.

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

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

Первая строка содержит одну строку W ( 1 ≤ | W | ≤ 100000 ), состоящую из строчных латинских символов.

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

Выведите одно целое число - максимально возможный вес.

Примечание

Решения, работающие при | W | ≤ 100 , будут оцениваться в 17 баллов.
Решения, работающие при | W | ≤ 5000 , будут оцениваться еще в 37 баллов.

Примеры
Входные данные
aaaa
Выходные данные
10
Входные данные
baccb
Выходные данные
9
Входные данные
slavko
Выходные данные
7
#113598
Сдвигай, считай, и снова
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Пусть дан строчный латинский символ c . Тогда операция shift ( c ) превращает c в следующий по порядку символ в алфавите. Например, shift (a) = b, shift (e) = f, shift (z) = a.

Дана строка S , состоящая из N строчных латинских символов (индексация с 0). Необходимо обработать Q запросов 2 типов:

"1 i j t": ко всем элементам строки с индексами в отрезке [i:j] применить t раз операцию shift .

"2 i j": найдите количество непустых подмножеств символов строки { c 1 , c 2 , ... , c k }, где i ≤ index c 1 < index c 2 < ... < index c k ≤ j , таких что символы подмножества, переставленные в некотором порядке, образуют палиндромом. Так как число может быть очень большим, выведите его по модулю 10 9 + 7 .

Два подмножества символов строки называются различными, если множества индексов их элементов различаются.

Строка называется палиндромом, если читается слева направо также, как справа налево.

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

Первая строка содержит два целых числа N и Q ( 1 ≤ N , Q ≤ 10 5 ) - длину строки и количество запросов соответственно. Вторая строка содержит одну строку S длины N , состоящую из строчных латинских символов. Каждая из последующих Q строк содержит запрос в формате, описанном в условии.

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

Для каждого запроса второго типа выведите одно целое число - ответ на данный запрос.

Примечание

Решения, работающие при N ≤ 500 и Q ≤ 500 , будут оцениваться в 20 баллов.

Решения, работающие при условии, что все запросы являются запросами второго типа, оцениваются еще в 30 баллов.

Примеры
Входные данные
3 5
aba
2 0 2
2 0 0
2 1 2
1 0 1 1
2 0 2
Выходные данные
5
1
2
3
Входные данные
5 7
acdec
2 0 3
1 3 4 36
1 2 3 81
1 1 4 11
2 3 3
2 2 3
2 1 2
Выходные данные
4
1
2
2
#113652
Получить из 1 число N
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Определить можно ли с использованием только операций «прибавить 3» и «прибавить 5» получить из числа \(1\) число \(N\) (\(N\) - натуральное, не превышает 200. Разумеется, само число \(1\) получить можно, просто не применяя никаких операций.

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

Вводится число \(N\).

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

Выведите слово YES, если число \(N\) можно получить из числа \(1\), или NO - в противном случае.

Примеры
Входные данные
1
Выходные данные
YES
Входные данные
3
Выходные данные
NO
#113653
Наибольшая цифра
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Дана строка, содержащая только десятичные цифры. Найти и вывести наибольшую цифру.

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

Вводится строка ненулевой длины. Известно также, что длина строки не превышает 1000 знаков и строка содержит только десятичные цифры.

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

Выведите максимальную цифру, которая встречается во введенной строке.

Примеры
Входные данные
11111111
Выходные данные
1
Страница: << 508 509 510 511 512 513 514 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест