Все задачи находятся в последнем соревновании группы
А - Добро пожаловать в бан
Автор: Xijiks
В этой задаче требовалось вывести "BAN".
B - ♫ Цвет настроения синий ♫
Автор: Xijiks
Нужно было найти количество чисел от 1 до N, которые при делении на 5 дают остаток 4. Это можно было сделать обычным циклом. Асимптотика такого решения O(N).
Также эту задачу можно было решать за O(1). Нужно было заметить, что ответ всегда равен .
C - Защита 10 из 10
Автор: Artemx
Даны 3 числа. Нужно было проверить, правда ли, что сумма каких-то двух из них равна третьему. Проверяем.
D - Архив смерти
Автор: fivut
Нужно было найти сумму кубов от 1 до N. Можно пройтись циклом и проссумировать. У многих была ошибка, связанная с переполнением типов данных. Многие писали что-то, похожее на это:
var
i, n : longint;
sum : int64;
begin
readln(n);
for i := 1 to n do
sum := sum + i * i * i;
write(sum);
end.
и получали неправильный ответ. Несмотря на то, что sum — переменная типа int64
(или long long
в C++), если i имеет тип int, то произойдет переполнение при умножении. Так как в паскале переменная цикла for
не может иметь тип int64, можно использовать цикл while
. Асимптотика данного решения O(N).
Также можно решить за O(1). Существуют формулы:
E - Шшшшшумы
Автор: Xijiks
Нам был дан массив, нужно в нём каждый 0 заменить на минимальное из рядом стоящих чисел, при этом гарантируется рядом с каждым 0 стоит два не нуля. Пройдемся по массиву и сделаем сделаем то, что просят. Асимптотика O(N).
F - Квадратные дата-центры
Автор: Xijiks
Дано число, найти ближайший к нему полный квадрат (модуль разности с которым минимален). С данными ограничениями можно было просто проверить все полные квадраты, которые не превосходят , и вывести тот, модуль разности с которым минимален. Асимптотика такого решения .
Можно решать за O(1). Пусть X = trunc(sqrt(N)). Тогда ответом является X либо (X + 1). Из двух вариантов выберем оптимальный.
Ещё одно O(1) решение: можно заметить, что ответ всегда равен round(sqrt(N))2.
Стоит отметить, если бы ограничения были больше, например, N ≤ 1018 функция sqrt сильно бы потеряла точность и ответ мог отличаться на 1, в этом случае для нахождения квадратного корня можно было бы использовать бинарный поиск. Можно также использовать sqrtl в C++. А можно было поступить иначе: пусть X = trunc(sqrt(N)). Проверим, что (X + 1)2 ≤ N, если это так, то увеличим X на 1.
G - MusicSearch.com
Автор: fivut
Нас просят отсортировать массив и удалить повторяющиеся в нём числа. Отсортируем массив. Уникальными будут те числа в массиве, которые не равны предыдущему. Асимптотика O(N2) или O(N·logN) в зависимости от типа сортировки (пузырьком или быстрой).
Также можно было отсортировать массив и использовать встроенную в С++ функцию unique. O(N·logN).
Ещё можно использовать set в C++. Просто добавим весь наш массив в set и выведем это множество. O(N·logN).
H - [название]
Автор: Artemx
Нам дана матрица из X и O. Нужно найти количество X, вокруг которых ещё 4 символа X. Пройдемся циклом и проверим. У некоторых была ошибка, связанная с обращением к несуществующему индексу массива. Например при проверке клетки [N][M] проверялось наличие крестика в клетке [N + 1][M + 1], в разных средах эта ошибка могла отработать с разными последствиями. Следовало сделать циклы не от 1 до N и от 1 до M, а вместо этого циклы от 2 до N - 1 и от 2 до M - 1. Итого мы 1 раз прошли матрицу, каждую клетку проверили за O(1). Итоговая асимптотика O(N·M).
I - Выбор аватарки
Автор: fivut
Нам дали 4 точки в случайном порядке, нужно проверить, являются ли они прямоугольником, параллельным осям коррдинат и имеющим ненулевую площадь. Самое простое решение: введем 4 точки в vector < pair < int, int > > в С++. Отсортируем этот вектор, и теперь уже несложно проверить, удовлетворяют ли они условию. Подробности в коде. Асимптотика O(1).
J - Страшная тайна ключей
Автор: Artemx
В задаче нам дали массив, нужно найти сумму простых чисел в нём или вывести -1, если в массиве нет простых чисел. Для решения нужно уметь проверять число на простоту за . Проверить число X на простоту можно следующим способом: если X делится без остатка хоть на одно число от 2 до , то оно составное, иначе простое. N чисел проверяем на простоту за . Итоговая асимптотика .
K - IP-адреса
Автор: Xijiks
Дана строка длиной не более 15, состоящая из цифр и точек. Необходимо было проверить, является ли она правильным IP. Правильный IP — X.X.X.X, где 0 ≤ X ≤ 255. Заметим, что если в строке не 3 точки, то ответ "NO". Иначе проверим, что никакие две точки не стоят рядом, а числа между точками не имеют лидирующих нулей и не превосходят 255. Задача на реализацию, детали смотрите в коде. Асимптотика O(length(S)).
L - GG WP, N00bs!
Автор: Artemx
Нужно было найти подмножества массива максимального размера, в котором разность между максимальным и минимальным элементом не превосходит X. Отсортируем массив и заметим, что искомым подмножеством является непрерывный отрезок массива. Переберём его правую границу R, тогда бинарным поиском найдем первое число в массиве, которое ≥ aR - X, пусть его индекс равен L. Обновим ответ длиной отрезка, равной R - L + 1. Сортируем за O(N·logN) и N раз используем бинарный поиск, работающий за O(N·logN). Итоговая асимптотика O(N·logN + N·logN) = O(N·logN).
Задачу можно было решать скользящим окном (методом двух указателей). Отсортируем массив. Будет поддерживать две переменные L и R, для каждого значения R найдем минимальное значение L при котором aR - aL ≤ X. Для каждого R найдем соответствующее L и обновим ответ величиной R - L + 1. Левая и правая граница суммарно передвинутся не более 2·N раз. Значит наше окно работает за O(N). O(N·logN) на сортировку. Получаем асимптотику O(N + N·logN) = O(N·logN).
M - Админ по имени Лёха
Автор: fivut
Нам был дан двумерный массив из 0 и 1. Требовалось найти квадрат с максимальной площадью, в котором ≤ S единиц. Для решения этой задачи требовалось за O(1) находить сумму в любом прямоугольнике матрицы. Сделать это можно с помощью префиксных сумм на матрице. Переберем верхний левый угол нашего квадрата и длину стороны квадрата. Таким образом мы переберём все квадраты в матрице. Мы можем обновить ответ текущей длиной квадрата, если в этом квадрате ≤ S единиц. Сумму в квадрате найдем с помощью префиксных сумм. Получается мы перебираем угол квадрата за O(N·M), его сторону за O(min(N, M)) и за O(1) находим в нём сумму. Асимптотика O(N·M·min(N, M)).
Бонус1: Попробуйте решить задачу за время O(N·M).
Бонус2: Попробуйте найти прямоугольник с максимальной площадь в матрице.