Источник заданий

Список заданий

1. Дан неориентированный граф. Определить минимальное количество ребер, после добавления которых граф станет связным. Вывести -1 если ответа не существует.
2. Дана последовательность целых чисел. Найти максимальное число, которое может быть получено путем перемножения двух любых чисел последовательности.
3. Дана последовательность N целых чисел (1 ≤ N ≤ 105, |Ai| ≤ 2 ⋅ 109) и число K (1 ≤ K ≤ N). Найти K чисел последовательности, произведение которых максимально.
4. Размеры прямоугольной размеченной квадратами доски n × m. В нижнем левом квадрате доски (1,1) находится шахматный конь. Конь может ходить только согласно шахматным правилам – движение может быть двумя квадратами горизонтально и затем одним вертикально, или двумя квадратами вертикально и одним горизонтально. Например, если n=4 и m=3, и конь находится в квадрате (2,1), то следующим может быть ход (1,3) или (3,3) или (4,2). Для заданных положительных целых значений n, m, i и j требуется определить минимальное необходимое количество ходов коня для перемещения из начальной позиции (1,1) в квадрат (i,j).
5. Задан связный неориентированный взвешенный граф G. В графе возможно наличие нескольких ребер между одной и той же парой вершин. Найдите вес кратчайшего пути между двумя заданными вершинами A и B.
6. Дано поле N × M. На нем расположены две ладьи, координаты каждой (X1, Y1) и (X2, Y2) соответственно. Ладья ходит по классическим правилам шахмат: за один ход может переместиться в любую клетку, расположенную на одной вертикали либо горизонтали. Одна ладья может сбить другую, если та находится с ней на одной горизонтали либо вертикали. Основное отличие от классических правил: ладья не может переместиться в клетку, если во время передвижения к ней она станет на клетку, которая находится под боем другой ладьи. У первого игрока в распоряжении первая ладья, а у второго —вторая. Игроки ходят по очереди, ход пропускать нельзя. Первым ходит первый игрок. Проигрывает тот, кому некуда ходить (куда бы ни пошел — собьют). Определите кто победит при оптимальной игре обоих.
7. В заданной строке S найти максимальную по длине подстроку, которая не является палиндромом.
8. Дана строка S и Q запросов. Запрос представляет собой пару чисел L и R — промежуток строки S, на котором нужно инвертировать регистр символов. Требутеся найти строку S после выполнения всех запросов.
9. Известный фокусник Донни разбогател на очень простой игре. Он играл в нее на деньги с самыми богатыми и знаменитыми личностями, но никто ни разу не смог его обхитрить. И тут очередь дошла до вас. Вы белорусский бизнесмен и хотите удвоить свое состояние. Обыграйте Донни и сорвите куш! Так же вы можете отказаться от игры, если, при виде начальной позиции, на вас нападет плохое предчувствие. Правила игры следующие: Изначально дано число X. За один ход разрешается отнять от числа X любую цифру, кроме 0, которая входит в число X. Проигрывает тот, кто не может ходить, то есть когда будет получено число 0.
10. Дан неориентированный граф. Определить минимальное количество ребер, после удаления которых между каждой парой вершин будет существовать только один маршрут (без повторений в нем ребер). Вывести -1, если ответа не существует.
11. Дан неориентированный граф. Определить количество маршрутов (по ребрам можно перемещаться несколько раз) длиной L между вершинами U и V.
12. Дана последовательность Ai, состоящая из N целых чисел. За одно действие можно зафиксировать произвольный промежуток одинаковых элементов последовательности и увеличить все элементы этого промежутка на 1. Необходимо за минимальное количество действий уравнять все элементы.
13. Дано число X. Надо найти наименьшее число большее, чем X, которое может быть получено из X перестановкой цифр.
14. Дана последовательность из N целых положительных чисел. Требуется определить можно ли путем перемножения некоторых чисел последовательности получить число 1087388483.
15. Дана последовательность Ai, состоящая из N целых чисел. За одно действие можно зафиксировать произвольный промежуток одинаковых элементов последовательности и увеличить все элементы этого промежутка на 1. Необходимо за минимальное количество действий уравнять все элементы.
16. Перестановкой чисел назовем такую последовательность А длины N, что 1 ≤ Ai ≤ N, и все числа последовательности различны. Инверсией в пeрестановке A размера N называется всякая пара индексов (i, j) такая, что i < j и Ai > Aj. В данной задаче необходимо найти число инверсий в заданной перестановке.
17. Дана последовательность из N целых положительных чисел. Требуется определить можно ли путем перемножения некоторых чисел последовательности получить число 1087388483.
18. Високосный год — год в юлианском и григорианском календарях, продолжительность которого равна 366 дням — на одни сутки больше продолжительности обычного, невисокосного года. В юлианском календаре високосным годом является каждый четвёртый год, в григорианском календаре из этого правила есть исключения. Год в григорианском календаре является високосным, если он кратен 4 и при этом не кратен 100, либо кратен 400. Определите, является ли заданный год високосным в григорианском календаре.
19. Перестановкой чисел 1,2,3...N назовем такую последовательность А длины N, что 1 ≤ Ai ≤ N, и все числа последовательности различны. Инверсией в пeрестановке A размера N называется всякая пара индексов (i, j) такая, что i < j и Ai > Aj. В данной задаче необходимо найти число инверсий в заданной перестановке.
20. Дана рельефная местность. Местность разделена на N × M квадратов и описывается двумерной матрицей A, где Aij высота в квадрате (i,j). Определить максимальный объем воды, который может остаться после дождя. Вода распространяется на небОльшую по высоте местность в четырех направлениях (по вертикали и горизонтали). Считается, что за край местности может утечь сколь угодно много воды.
21. Дерево — это связный ациклический граф. Паросочетанием в графе называется множество ребер, попарно не имеющих общих вершин. Требуется найти максимальное по размеру паросочетание в дереве.
22. Определить количеcтво строк длины M из строчных букв латинского алфавита, в которых не содержится ни одна из заданной строки Wi.