Блог пользователя Artemx

Автор Artemx, 6 лет назад, По-русски

Все задачи находятся в последнем соревновании группы

А  -  Добро пожаловать в бан

Автор: 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). Существуют формулы:







Решение (Pascal)
Решение (С++)
Решение с формулой (С++)

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.

Решение (С++)
Решение 2 (С++)
Решение 3 (С++)

G  -  MusicSearch.com

Автор: fivut

Нас просят отсортировать массив и удалить повторяющиеся в нём числа. Отсортируем массив. Уникальными будут те числа в массиве, которые не равны предыдущему. Асимптотика O(N2) или O(N·logN) в зависимости от типа сортировки (пузырьком или быстрой).

Также можно было отсортировать массив и использовать встроенную в С++ функцию unique. O(N·logN).

Ещё можно использовать set в C++. Просто добавим весь наш массив в set и выведем это множество. O(N·logN).

Решение (C++)
Решение с unique (C++)
Решение с set (C++)

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).

Решение (Pascal)
Решение (C++)

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. Левая и правая граница суммарно передвинутся не более 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:  Попробуйте найти прямоугольник с максимальной площадь в матрице.

Решение (С++)

Полный текст и комментарии »

  • Проголосовать: нравится
  • +39
  • Проголосовать: не нравится