3 апреля на платформе All Cups прошло отборочное соревнование на курс «Продвинутая разработка микросервисов на Go» — это уже второй поток бесплатных курсов для разработчиков от Ozon Tech. Программа предназначена для мидлов, поэтому нужно было придумать задания и провести контест, чтобы отобрать релевантных участников.
Методисты All Cups совместно с организаторами разработали алгоритмические задачи, добавив актуального контекста. Здесь много любителей головоломок: предлагаем попробовать свои силы в задачах и сравнить с решениями.
![](https://habrastorage.org/r/w1560/getpro/habr/post_images/91d/218/328/91d2183285225edaa9b93ab1fac8dd75.png)
Никита собирается открывать свой пункт выдачи заказов (ПВЗ). Для обеспечения безопасности посетителей Никита решил обеспечить ПВЗ одноразовыми медицинскими масками, которые будут поставляться каждый месяц в количестве
штук. Местные поставщики продают маски по цене 0,55 рублей за одну штуку, но можно сэкономить, купив упаковку из 24 масок за 11 рублей или коробку из 16 упаковок за 160 рублей. Помогите Никите, определив, сколько коробок, упаковок и отдельных масок он должен купить, чтобы заплатить как можно меньше денег.
Примечание: Никита готов купить больше масок, чем ему нужно, если это позволит сэкономить.
В одной строке вводится одно целое число
.
Требуется вывести три числа в одну строку через пробел — количество отдельных масок, упаковок и коробок, которые надо купить.
Компания-застройщик занимается строительством недвижимости промышленного назначения, а именно складских помещений. Каждый квадратный метр площади стоит
рублей. Компания имеет достаточный запас оборотных средств, чтобы продавать построенные помещения не сразу после завершения строительства, а в тот момент, когда ей это выгодно. Рынок недвижимости очень динамичный, поэтому цена квадратного метра меняется каждый день. Аналитики застройщика смогли точно спрогнозировать цену на ближайшие
дней (пронумеруем дни в хронологическом порядке от
до
). Теперь требуется определить, в какие из этих дней нужно продавать, чтобы по истечении
дней заработать как можно больше денег. Известно, что стройка новых площадей происходит с равномерной скоростью
кв. метров в сутки. А к нулевому дню объем построенной площади составлял
кв. метров, при том что
.
В первой строке вводится одно целое число
— количество дней. Во второй строке вводится последовательность из
целых положительных чисел — цена квадратного метра складской площади в каждый из дней.
Вывести одно число — максимальное количество денег, которое может заработать компания-застройщик.
Максим решил заняться продажей картин на NFT-площадках, а для этого нужно придумать что-то свое и оригинальное. Максиму очень нравится, как выглядят цифры на черном фоне. Нужно написать программу, которая будет рисовать квадрат, состоящий из целых чисел и выводить информацию о его размере.
В одной строке через пробел вводится набор чисел или символов.
В первой строке выводится сообщение «Квадрат со стороной N». В следующих строках требуется вывести квадрат, сформированный из набора чисел или символов, длина стороны — длина введённого массива.
В базе данных есть таблица
![](https://habrastorage.org/r/w1560/getpro/habr/post_images/3ea/00a/ceb/3ea00aceb0c43e7409f0a94ffd01cf16.png)
Напишите запрос, который покажет общие продажи по всем странам, отсортированные в порядке возрастания. На выходе в первой колонке должно быть название страны, а во второй показатель общих продаж.
На чемпионате во фразе «отсортированные в порядке» было некорректное склонение, что заставляло пользователей думать, что сортировать необходимо по странам. Это было оперативно исправлено и сейчас формулировка корректна.
Примечание: для решения задачи используется база данных Chinook Database в формате SQLite — см. файл Chinook_Sqlite.sqlite.
Паша и Саша проживают в большом подмосковном городе, в котором
районов. Не так давно два друга решили стать тайными покупателями в Ozon. Они решили подойти к делу очень ответственно, поэтому очень хотят обойти все пункты выдачи, посовещаться и выбрать самый лучший. В каждом районе города есть только одна точка выдачи. Внимательно изучив карту города, ребята поняли, что проверить все пункты у них физически не получится, уж очень далеко им придётся ходить, поэтому они решили ограничиться количеством путешествий, равным количеству всех возможных вариантов обхода, взятому по модулю
, а также решили позвать на помощь
друзей, которые будут параллельно обходить точки. При этом каждому из друзей выделено разное подмножество пунктов выдачи:
,
, ...,
. Найдите количество вариантов обходов всех пунктов выдачи в произвольном порядке.
Примечание: Паша и Саша ходят вместе, а друзья поодиночке. Например, для
есть 6 вариантов обходов (
,
,
,
,
,
), по модулю 6 это 0. А для
— 24 варианта обходов (
,
,…,
). 24 по модулю 7 будет 3.
В первой строке вводится число
. Далее на вход поступает
строк, каждая из которых содержит два целых числа
и
(
,
).
Вывести
чисел — количество обходов для каждого участника.
Кирилл работает аналитиком в Ozon, и недавно ему в руки попал отчёт, из которого он понял, что время доставки товаров в пункты выдачи можно значительно сократить. Он заметил, что пункты выдачи в городе образуют выпуклый многоугольник с количеством вершин, равным
, и располагаются на его вершинах, где одна вершина = один пункт выдачи. Кирилл решил воспользоваться всеми прелестями современных технологий, он хочет проложить воздушные пути между пунктами выдачи, по которым будут перемещаться курьеры на грузоподъёмных реактивных ранцах.
Можно выбрать какое-то число
, при котором каждый пункт выдачи будет соединен с
соседними пунктами выдачи слева и справа. Нужно найти минимальное
, чтобы кратчайшее расстояние между любыми двумя пунктами выдачи было меньше или равно
. Расстояние между пунктами выдачи примерно одинаковое, поэтому расстояние будет измеряться в количестве переходов, которые нужно сделать, чтобы попасть из одного пункта выдачи в другой.
![](https://habrastorage.org/r/w1560/getpro/habr/post_images/586/484/b20/586484b20f727888bca22dc32c81c1d9.png)
Пояснение к примеру
В первую строку вводится одно целое число
— количество наборов входных данных. Для каждого набора входных данных в строку через пробел вводится два целых числа
и
. Ограничения:
,
.
Для каждого набора чисел выведите минимальное
, удовлетворяющее условию.
Напиши скрипт, который будет получать на вход
Две даты через пробел в формате YYYY-MM-DD.
Одно целое число — разница в днях.
В базе данных есть таблицы
![](https://habrastorage.org/r/w780q1/getpro/habr/post_images/3fe/1a6/01c/3fe1a601c533d845f5b533fed4b34ca2.jpg)
Напишите запрос, который будет искать трех продавцов на маркетплейсе, совершивших больше всего продаж, начиная с 2010 года. На выходе в первой колонке должны быть имя и фамилия продавца, а во второй количество их продаж, отсортированное в порядке убывания.
Примечание: для решения задачи используется база данных Chinook Database в формате SQLite — см. файл Chinook_Sqlite.sqlite. Также во время чемпионата у участников возникал вопрос относительно имени и фамилии в первой колонке таблицы. Поясним, что они должны быть через пробел.
В базе данных есть таблицы
![](https://habrastorage.org/r/w780q1/getpro/habr/post_images/733/fdc/9d4/733fdc9d434c3984c2b69c4fd41e39c0.jpg)
Напишите запрос, который составит рейтинг треков по их продаваемости, начиная с 2010 года. На выходе должны получиться две колонки. В первой колонке должны быть
Примечание: для решения задачи используется база данных Chinook Database в формате SQLite — см. файл Chinook_Sqlite.sqlite.
Такие задачи были в отборочном и основном раунде для поступления на курс «Продвинутая разработка микросервисов на Go». Какая задача вам показалась самой лёгкой, а какая — наиболее сложной? А если вы нашли более эффективное или элегантное решение, делитесь в комментариях :)
Методисты All Cups совместно с организаторами разработали алгоритмические задачи, добавив актуального контекста. Здесь много любителей головоломок: предлагаем попробовать свои силы в задачах и сравнить с решениями.
![](https://habrastorage.org/getpro/habr/post_images/91d/218/328/91d2183285225edaa9b93ab1fac8dd75.png)
Задача «Маски»
Никита собирается открывать свой пункт выдачи заказов (ПВЗ). Для обеспечения безопасности посетителей Никита решил обеспечить ПВЗ одноразовыми медицинскими масками, которые будут поставляться каждый месяц в количестве
Примечание: Никита готов купить больше масок, чем ему нужно, если это позволит сэкономить.
Формат входных данных
В одной строке вводится одно целое число
Формат выходных данных
Требуется вывести три числа в одну строку через пробел — количество отдельных масок, упаковок и коробок, которые надо купить.
Решение
Если нужно купить
маски, то выгоднее всего приобрести сразу коробку. А если нужно только
маски, то лучше купить упаковку, а не поштучно. Поэтому можно придерживаться такой стратегии:
Однако такой подход не всегда самый выгодный, потому что можно купить лишние маски, если это позволит сэкономить. К тому же при таком подходе количества коробок и упаковок отличаются от оптимальных максимум на единицу. Давайте теперь проверим неравенство, при котором выгоднее купить упаковку, чем докупать поштучно:
. А в каком случае выгодно купить ещё одну коробку? В случае, если
, где
и
— количества масок и упаковок соответственно, обновлённые с учётом покупки ещё одной упаковки.
Остаётся лишь представить эти формулы в коде.
- Сначала купить как можно больше коробок
.
- Затем — как можно больше упаковок
.
- И остаток M докупить поштучно.
Однако такой подход не всегда самый выгодный, потому что можно купить лишние маски, если это позволит сэкономить. К тому же при таком подходе количества коробок и упаковок отличаются от оптимальных максимум на единицу. Давайте теперь проверим неравенство, при котором выгоднее купить упаковку, чем докупать поштучно:
Остаётся лишь представить эти формулы в коде.
Задача «Склады»
Компания-застройщик занимается строительством недвижимости промышленного назначения, а именно складских помещений. Каждый квадратный метр площади стоит
Формат входных данных
В первой строке вводится одно целое число
Формат выходных данных
Вывести одно число — максимальное количество денег, которое может заработать компания-застройщик.
Решение
Применим «жадный» подход: будем продавать каждый построенный квадратный метр за максимальную цену. Пусть
— цена квадратного метра складов в
-й день. Какая будет максимальная цена продажи квадратного метра, построенного к
-му дню? Так как продать его мы можем в любой день с
-го по
-й, то и максимальная цена будет равна
. Остаётся подсчитать этот максимум для каждого дня. Проще всего сделать это за квадратичную асимптотику, просто перебрав день продажи для каждого дня постройки.
Есть и другое, более быстрое решение задачи за линейное время! Для этого пройдём по массиву
с конца, поддерживая наибольшее число среди рассмотренных элементов — это и будет искомая цена продажи!
Есть и другое, более быстрое решение задачи за линейное время! Для этого пройдём по массиву
Задача «Картины»
Максим решил заняться продажей картин на NFT-площадках, а для этого нужно придумать что-то свое и оригинальное. Максиму очень нравится, как выглядят цифры на черном фоне. Нужно написать программу, которая будет рисовать квадрат, состоящий из целых чисел и выводить информацию о его размере.
Формат входных данных
В одной строке через пробел вводится набор чисел или символов.
Формат выходных данных
В первой строке выводится сообщение «Квадрат со стороной N». В следующих строках требуется вывести квадрат, сформированный из набора чисел или символов, длина стороны — длина введённого массива.
Решение
Эта задача не вызывает трудностей у любителей программирования до тех пор, пока не выясняется, что решить её нужно с помощью скрипта на Bash. Задача чисто техническая, вот один из возможных способов решения:
- Для начала прочитаем массив из входных данных и узнаем его длину:
read line array=($line) len=${#array[@]}
- Затем выведем фразу про «квадрат»:
echo "Квадрат со стороной $len"
- И в завершение воспользуемся циклом со счётчиком и отобразим исходный массив
раз:
for (( i = 0; i < $len; i++ )) do echo $line done
Задача «Продажи»
В базе данных есть таблица
Invoice
следующего вида:![](https://habrastorage.org/getpro/habr/post_images/3ea/00a/ceb/3ea00aceb0c43e7409f0a94ffd01cf16.png)
Напишите запрос, который покажет общие продажи по всем странам, отсортированные в порядке возрастания. На выходе в первой колонке должно быть название страны, а во второй показатель общих продаж.
На чемпионате во фразе «отсортированные в порядке» было некорректное склонение, что заставляло пользователей думать, что сортировать необходимо по странам. Это было оперативно исправлено и сейчас формулировка корректна.
Примечание: для решения задачи используется база данных Chinook Database в формате SQLite — см. файл Chinook_Sqlite.sqlite.
Решение
Для решения этой задачи достаточно уметь группировать элементы таблицы по значению и сортировать их. Первое можно сделать командой
Функция
GROUP BY
, а второе — командой ORDER BY
. Тогда запрос, который покажет общие продажи по всем странам, отсортированные в порядке возрастания, может выглядеть так:SELECT
BillingCountry,
SUM(total)
FROM
Invoice
GROUP BY BillingCountry
ORDER BY SUM(total);
Функция
SUM
в рамках GROUP BY
посчитает именно то, что мы хотим — сумму всех продаж для каждой страны.Задача «Тайные покупатели»
Паша и Саша проживают в большом подмосковном городе, в котором
Примечание: Паша и Саша ходят вместе, а друзья поодиночке. Например, для
Формат входных данных
В первой строке вводится число
Участников соревнования могло ввести в заблуждение неопределенность в ограничении. Во время соревнования задание было дополнено, сейчас вам доступен финальный текст.
Формат выходных данных
Вывести
Решение
Нам нужно для
пар чисел
и
найти остаток от деления факториала
на
. При этом ограничения на
слишком велики, чтобы вычислять этот факториал за линейное время.
Занимательный факт: для любых
каждое число
делится без остатка на
. Тогда возможны два случая:
Если раньше вы не работали с факториалом по модулю, то вот пример псевдокода его подсчёта:
Занимательный факт: для любых
: ответ
.
: можно посчитать факториал по модулю за линейное время (нам это позволяет ограничение на значение
).
Если раньше вы не работали с факториалом по модулю, то вот пример псевдокода его подсчёта:
fact = 1
for i from 2 to n
fact = (fact * i) mod t
Задача «Маршруты»
Кирилл работает аналитиком в Ozon, и недавно ему в руки попал отчёт, из которого он понял, что время доставки товаров в пункты выдачи можно значительно сократить. Он заметил, что пункты выдачи в городе образуют выпуклый многоугольник с количеством вершин, равным
Можно выбрать какое-то число
![](https://habrastorage.org/getpro/habr/post_images/586/484/b20/586484b20f727888bca22dc32c81c1d9.png)
Пояснение к примеру
- Если при
выбрать
(соединив каждую вершину только с одним ближайшим соседом слева и справа), то минимальное расстояние, например от узла
до узла
будет равно 3. Но
, значит это решение не удовлетворяет условию.
- Если при
выбрать
(соединив каждую вершину с двумя ближайшими соседями с каждой стороны), то минимальное расстояние между любой парой вершин получается равным 2. Это удовлетворяет условию
, значит это верное решение.
- Для треугольника (
) все вершины являются соседними друг другу, значит единственно возможным решением является
, что удовлетворяет условию
.
Формат входных данных
В первую строку вводится одно целое число
Формат выходных данных
Для каждого набора чисел выведите минимальное
Решение
Для решения этой задачи нам нужно вывести формулу. Если
, то нам подойдёт любое
, поэтому ответ будет
.
— интересный случай. Зафиксируем некоторую точку в многоугольнике. Тогда
— расстояние до наиболее удалённой от неё точки при условии, что
. Например, для случаев
и
наиболее удалённая точка находится на расстоянии
. Как изменится количество переходов, если увеличить
? Тогда мы сможем переходить не только в соседнюю точку, но и «прыгать» через
точку. Например, если
, то при
наиболее удалённая точка будет в четырёх переходах от зафиксированной.
А что будет, если
не делится на
без остатка? В этом случае для прохождения оставшегося пути нам понадобится ещё один переход. С этого момента есть способа решения: двоичный поиск по ответу или доработка формулы для получения минимального
. Возьмём максимум полученного значения и единицы, так как нам в любом случае нужно соединять точку хотя бы с одним соседом. Тогда для формулы
мы можем получить
, например при
и
.
А что будет, если
Задача «Даты»
Напиши скрипт, который будет получать на вход
stdin
два параметра d1
и d2
в формате YYYY-MM-DD, и будет считать разницу между этими датами в днях. Скрипт проверяется на Bash 5.1.4 (запуск под Ubuntu 20.04).Формат входных данных
Две даты через пробел в формате YYYY-MM-DD.
Формат выходных данных
Одно целое число — разница в днях.
Решение
Чтобы решить задачу, необходимо уметь пользоваться функцией
Бонус: уже после написания разбора обнаружилось два забавных факта:
Таким образом, немного упрощённое решение выглядит так:
date
, которая позволяет получить из строки дату и преобразить её в формат unix time. Давайте так и поступим, затем найдём разность и переведём её в дни:- Считываем даты из входного потока:
read s1 s2 d1=`date -d "$s1" "+%Y-%m-%d"` d2=`date -d "$s2" "+%Y-%m-%d"`
- Переводим даты в unix time:
ut1=`date -d "$d1" +%s` ut2=`date -d "$d2" +%s`
- Считаем разность секунд и переводим в дни:
diff=$(($ut1 - $ut2)) diff_days=$(($diff / (60 * 60 * 24)))
- Выводим абсолютное значение разности (можно было бы написать
if
, но такой «чит» выглядит лаконичнее: он переводит значение в строку и удаляет лидирующий минус, если он есть):
echo ${diff_days#-}
Бонус: уже после написания разбора обнаружилось два забавных факта:
- Во всех тестах вторая дата идёт хронологически позже первой.
- Формат даты в условии не надо дополнительно парсить, а можно сразу переводить в unix time.
Таким образом, немного упрощённое решение выглядит так:
read d1 d2
ut1=`date -d $d1 +%s`
ut2=`date -d $d2 +%s`
diff=$(($ut2 - $ut1))
diff_days=$(($diff / (60 * 60 * 24)))
echo $diff_days
Задача «Анализ продаж»
В базе данных есть таблицы
Invoice
, Customer
, Employee
следующего вида:![](https://habrastorage.org/getpro/habr/post_images/3fe/1a6/01c/3fe1a601c533d845f5b533fed4b34ca2.jpg)
Напишите запрос, который будет искать трех продавцов на маркетплейсе, совершивших больше всего продаж, начиная с 2010 года. На выходе в первой колонке должны быть имя и фамилия продавца, а во второй количество их продаж, отсортированное в порядке убывания.
Примечание: для решения задачи используется база данных Chinook Database в формате SQLite — см. файл Chinook_Sqlite.sqlite. Также во время чемпионата у участников возникал вопрос относительно имени и фамилии в первой колонке таблицы. Поясним, что они должны быть через пробел.
Решение
Сначала нужно понять, как join-ить данные, чтобы получить таблицы продаж для каждого продавца.
Теперь отфильтруем все продажи начиная с 2010 года. Для этого можно можно преобразовать даты с помощью
Далее остается лишь соединить фамилию и имя и выполнить простейшую агрегацию. Пример финального запроса:
Invoice
и Сustomer
можно объединить по CustomerId
, а Сustomer
и Employee
по Customer.SupportRepId = Employee.EmployeeId
.Теперь отфильтруем все продажи начиная с 2010 года. Для этого можно можно преобразовать даты с помощью
CAST
и сравнить, либо воспользоваться выражением LIKE «201%»
, тестовые данные допускают оба варианта. Далее остается лишь соединить фамилию и имя и выполнить простейшую агрегацию. Пример финального запроса:
SELECT
Employee.FirstName || ' ' || Employee.LastName as Name,
COUNT(Customer.SupportRepId) AS Total
FROM
Invoice
INNER JOIN
Customer
ON
Invoice.CustomerId = Customer.CustomerId
INNER JOIN
Employee
ON
Customer.SupportRepId = Employee.EmployeeId
WHERE
Invoice.InvoiceDate LIKE "201%"
GROUP BY Name
ORDER BY Total DESC
LIMIT 3
Задача «Треки»
В базе данных есть таблицы
Invoice
, InvoiceLine
, Track
следующего вида:![](https://habrastorage.org/getpro/habr/post_images/733/fdc/9d4/733fdc9d434c3984c2b69c4fd41e39c0.jpg)
Напишите запрос, который составит рейтинг треков по их продаваемости, начиная с 2010 года. На выходе должны получиться две колонки. В первой колонке должны быть
Id
трека, отсортированные в порядке возрастания, а во второй колонке — количество проданных копий трека, отсортированных в порядке убывания.Примечание: для решения задачи используется база данных Chinook Database в формате SQLite — см. файл Chinook_Sqlite.sqlite.
Решение
Нам нужно сделать общую таблицу при помощи операции
Остаётся подсчитать сумму продаж по каждому треку: сгруппируем данные, применим функцию
INNER JOIN
. Облегчает задачу то, что у нас есть общее поле TrackId
в таблицах Track
и InvoiceLine
, а также общее поле InvoiceId
в таблицах InvoiceLine
и Invoice
. Затем отфильтруем все продажи начиная с 2010 года. Как и в предыдущей задаче, для этого есть два способа: применить к датам CAST
и сравнить, или выполнить выражение LIKE «201%»
.Остаётся подсчитать сумму продаж по каждому треку: сгруппируем данные, применим функцию
SUM
к значению InvoiceLine.Quantity
, а затем отсортируем значения в получившейся таблице. Вариант финального запроса:SELECT
Track.TrackId AS TrackId,
SUM(InvoiceLine.Quantity) AS Total
FROM
Track
INNER JOIN
InvoiceLine
ON
Track.TrackId = InvoiceLine.TrackId
INNER JOIN
Invoice
ON
InvoiceLine.InvoiceId = Invoice.InvoiceId
WHERE
Invoice.InvoiceDate LIKE '201%'
GROUP BY Track.TrackId
ORDER BY Total DESC, TrackId ASC
Такие задачи были в отборочном и основном раунде для поступления на курс «Продвинутая разработка микросервисов на Go». Какая задача вам показалась самой лёгкой, а какая — наиболее сложной? А если вы нашли более эффективное или элегантное решение, делитесь в комментариях :)
Only registered users can participate in poll. Log in, please.
Какую задачу вы считаете самой интересной?
9.52% Маски2
9.52% Склады2
0% Картины0
0% Продажи0
14.29% Тайные покупатели3
23.81% Маршруты5
0% Даты0
4.76% Анализ продаж1
4.76% Треки1
52.38% Посмотреть результаты11
21 users voted. 22 users abstained.