Дан неориентированный граф. Определить минимальное количество ребер, после добавления которых граф станет связным. Вывести -1 если ответа не существует.
В первой строке два числа N (1 ≤ N ≤ 10^4) и M (0 ≤ M ≤ 10^5) — количество вершин и ребер соответственно. Следующие M описывают ребра: пара чисел U, V (1 ≤ U, V ≤ N) — номера вершин, соединенных ребром.
Вывести ответ на задачу. Если ответа не существует, то вывести -1.
Дана последовательность целых чисел. Найти максимальное число, которое может быть получено путем перемножения двух любых чисел последовательности.
В первой строке содержится число N — количество чисел в последовательности (2 ≤ N ≤ 10^5). Во второй строке содержатся числа A1 A2 AN — элементы последовательности, разделенные пробелом (|Ai| ≤ 10^9).
Выведите максимальное число, которое может быть получено путем перемножения двух любых чисел последовательности.
Дана последовательность N целых чисел (1 ≤ N ≤ 10^5, |Ai| ≤ 2 ⋅ 10^9) и число K (1 ≤ K ≤ N). Найти K чисел последовательности, произведение которых максимально.
В первой строке содержатся два целых числа N и K. Во второй строке через пробел перечислены N элементов последовательности A.
Выведите максимальное произведение. Так как ответ может быть достаточно большим, выведите его по модулю 10^9+7.
Размеры прямоугольной размеченной квадратами доски n × m. В нижнем левом квадрате доски (1,1) находится шахматный конь. Конь может ходить только согласно шахматным правилам – движение может быть двумя квадратами горизонтально и затем одним вертикально, или двумя квадратами вертикально и одним горизонтально. Например, если n=4 и m=3, и конь находится в квадрате (2,1), то следующим может быть ход (1,3) или (3,3) или (4,2). Для заданных положительных целых значений n, m, i и j требуется определить минимальное необходимое количество ходов коня для перемещения из начальной позиции (1,1) в квадрат (i,j).
В единственной строке заданы четыре целых числа n m i j — размеры доски и координаты конечного квадрата (1 ≤ n, m ≤ 100, 1 ≤ i ≤ n, 1 ≤ j ≤ m).
В единственной строке выведите минимальное количество ходов для перемещения или "NEVAR" если это невозможно.
Задан связный неориентированный взвешенный граф G. В графе возможно наличие нескольких ребер между одной и той же парой вершин. Найдите вес кратчайшего пути между двумя заданными вершинами A и B.
Первая строка содержит целое число N (1 ≤ N ≤ 10^5) — количество вершин графа. Вторая строка содержит целое число M (1 ≤ M ≤ 10^6) — количество ребер графа. В каждой из следующих M строк содержатся ровно три числа A, B, C (1 ≤ A, B ≤ N, 1 ≤ C ≤ 10^6). Эти числа описывают ребро, соединяющее вершины с номерами A и B и имеющее вес C. Последние две строки содержат целые числа A и B (1 ≤ A, B ≤ N) - начальную и конечную вершины пути. Вершины нумеруются последовательными натуральными числами от 1 до N.
Единственная строка выходного файла должна содержать одно целое число, равное весу кратчайшего пути между вершинами A и B в графе G.
Дано поле N × M. На нем расположены две ладьи, координаты каждой (X1, Y1) и (X2, Y2) соответственно. Ладья ходит по классическим правилам шахмат: за один ход может переместиться в любую клетку, расположенную на одной вертикали либо горизонтали. Одна ладья может сбить другую, если та находится с ней на одной горизонтали либо вертикали. Основное отличие от классических правил: ладья не может переместиться в клетку, если во время передвижения к ней она станет на клетку, которая находится под боем другой ладьи. У первого игрока в распоряжении первая ладья, а у второго —вторая. Игроки ходят по очереди, ход пропускать нельзя. Первым ходит первый игрок. Проигрывает тот, кому некуда ходить (куда бы ни пошел — собьют). Определите кто победит при оптимальной игре обоих.
В первой строке через пробел вводятся 6 целых чисел N M X1 Y1 X2 Y2 (2 ≤ N, M ≤ 50, 1 ≤ X1, X2 ≤ N, 1 ≤ Y1, Y2 ≤ M, X1 ≠ X2 или Y1 ≠ Y2).
Выведите YES, если победит первой игрок, иначе NO.
В заданной строке S найти максимальную по длине подстроку, которая не является палиндромом.
На вход задается строка S, состоящая из строчных букв латинского алфавита (1 ≤ |S| ≤ 10^5).
Выведите одно целое число — длина максимального непалиндрома. Если такой подстроки не существует, то выведите -1.
Дана строка S и Q запросов. Запрос представляет собой пару чисел L и R — промежуток строки S, на котором нужно инвертировать регистр символов. Требутеся найти строку S после выполнения всех запросов.
В первой строке задается строка S, состоящая из строчных и прописных букв латинского алфавита (1 ≤ |S| ≤ 10^5). Во второй строке задается число Q — количество запросов (0 ≤ Q ≤ 10^6). В следующих Q строках задаются запросы парой целых чисел Li Ri (1 ≤ Li, Ri ≤ N).
Выведите строку S после выполнения всех запросов.
Для заданной строки S требуется найти количество различных подстрок в ней.
В единственной строке находится данная строка S, которая состоит только из маленьких латинских букв (1 ≤ |S| ≤ 10^5).
Выведите одно число — искомую сумму.
Известный фокусник Донни разбогател на очень простой игре. Он играл в нее на деньги с самыми богатыми и знаменитыми личностями, но никто ни разу не смог его обхитрить. И тут очередь дошла до вас. Вы белорусский бизнесмен и хотите удвоить свое состояние. Обыграйте Донни и сорвите куш! Так же вы можете отказаться от игры, если, при виде начальной позиции, на вас нападет плохое предчувствие. Правила игры следующие: Изначально дано число X. За один ход разрешается отнять от числа X любую цифру, кроме 0, которая входит в число X. Проигрывает тот, кто не может ходить, то есть когда будет получено число 0.
В первой строке задается число X — начальное число для игры (0 ≤ X ≤ 10^10).
Выведите цифру первого хода, которая приведет вас к победе, иначе выведите NO, если хотите отказаться от игры.
Дан неориентированный граф. Определить минимальное количество ребер, после удаления которых между каждой парой вершин будет существовать только один маршрут (без повторений в нем ребер). Вывести -1, если ответа не существует.
В первой строке два числа N (1 ≤ N ≤ 10^4) и M (1 ≤ M ≤ 10^5) — количество вершин и ребер соответственно. Следующие M описывают ребра: пара чисел U, V — номера вершин, соединенных ребром.
Вывести ответ на задачу. Если ответа не существует, то вывести -1.
Дан неориентированный граф. Определить количество маршрутов (по ребрам можно перемещаться несколько раз) длиной L между вершинами U и V.
В первой строке два числа N (1 ≤ N ≤ 100) и M (1 ≤ M ≤ 10^5) — количество вершин и ребер соответственно. Во второй строке вводятся U V L (1 ≤ U, V ≤ N, 0 ≤ L ≤ 10^9). Следующие M строк описывают ребра: пара чисел A, B — номера вершин, соединенных ребром.
Вывести ответ на задачу по модулю 10^9+7.
Дана последовательность Ai, состоящая из N целых чисел. За одно действие можно зафиксировать произвольный промежуток одинаковых элементов последовательности и увеличить все элементы этого промежутка на 1. Необходимо за минимальное количество действий уравнять все элементы.
В первой строке вводится число N (1 ≤ N ≤ 10^5). Во второй строке вводятся элементы последовательности Ai (0 ≤ Ai ≤ 10^9).
В единственной строке выведите одно число — минимальное количество действий, которое необходимо выполнить для того, чтобы уравнять все элементы последовательности.
Дано число X. Надо найти наименьшее число большее, чем X, которое может быть получено из X перестановкой цифр.
В первой строке задается целое число X (1 ≤ X < 10^6).
Если ответ не существует, то выведите -1, иначе искомое число.
Дана последовательность из N целых положительных чисел. Требуется определить можно ли путем перемножения некоторых чисел последовательности получить число 1087388483.
В первой строке содержится число N (1 ≤ N ≤ 10^5). В следующих N строках содержатся Ai — элементы последовательности (0 ≤ Ai ≤ 2 × 10^9).
Если можно получить данное число, тогда выведите YES, иначе NO.
Високосный год — год в юлианском и григорианском календарях, продолжительность которого равна 366 дням — на одни сутки больше продолжительности обычного, невисокосного года. В юлианском календаре високосным годом является каждый четвёртый год, в григорианском календаре из этого правила есть исключения. Год в григорианском календаре является високосным, если он кратен 4 и при этом не кратен 100, либо кратен 400. Определите, является ли заданный год високосным в григорианском календаре.
В первой и единственной строке задается целое число Y — год, который нужно проверить (2000 ≤ Y ≤ 9999).
Если заданный год високосный, то выведите YES, иначе — NO.