Как стать автором
Поиск
Написать публикацию
Обновить
248
Рейтинг
Ozon Tech
Команда разработки ведущего e‑com в России

Маски, картины, тайные покупатели и анализ продаж: разбираем решения задач для Go-разработчиков

Время на прочтение10 мин
Количество просмотров12K
Блог компании Ozon TechБлог компании VKGo*Занимательные задачкиУчебный процесс в IT
3 апреля на платформе All Cups прошло отборочное соревнование на курс «Продвинутая разработка микросервисов на Go» — это уже второй поток бесплатных курсов для разработчиков от Ozon Tech. Программа предназначена для мидлов, поэтому нужно было придумать задания и провести контест, чтобы отобрать релевантных участников.

Методисты All Cups совместно с организаторами разработали алгоритмические задачи, добавив актуального контекста. Здесь много любителей головоломок: предлагаем попробовать свои силы в задачах и сравнить с решениями.



Задача «Маски»


Никита собирается открывать свой пункт выдачи заказов (ПВЗ). Для обеспечения безопасности посетителей Никита решил обеспечить ПВЗ одноразовыми медицинскими масками, которые будут поставляться каждый месяц в количестве $N$ штук. Местные поставщики продают маски по цене 0,55 рублей за одну штуку, но можно сэкономить, купив упаковку из 24 масок за 11 рублей или коробку из 16 упаковок за 160 рублей. Помогите Никите, определив, сколько коробок, упаковок и отдельных масок он должен купить, чтобы заплатить как можно меньше денег.

Примечание: Никита готов купить больше масок, чем ему нужно, если это позволит сэкономить.

Формат входных данных


В одной строке вводится одно целое число $N (1 ≤ N ≤ 50000)$.

Формат выходных данных


Требуется вывести три числа в одну строку через пробел — количество отдельных масок, упаковок и коробок, которые надо купить.

Решение
Если нужно купить $16 \times 24 = 384$ маски, то выгоднее всего приобрести сразу коробку. А если нужно только $24$ маски, то лучше купить упаковку, а не поштучно. Поэтому можно придерживаться такой стратегии:

  1. Сначала купить как можно больше коробок $K = \lfloor \frac{N}{384} \rfloor$.
  2. Затем — как можно больше упаковок $M = \lfloor \frac{N — 384K}{24} \rfloor$.
  3. И остаток M докупить поштучно.

Однако такой подход не всегда самый выгодный, потому что можно купить лишние маски, если это позволит сэкономить. К тому же при таком подходе количества коробок и упаковок отличаются от оптимальных максимум на единицу. Давайте теперь проверим неравенство, при котором выгоднее купить упаковку, чем докупать поштучно: $M \times 0,55 > 11$. А в каком случае выгодно купить ещё одну коробку? В случае, если $M' \times 0,55 + K' \times 11 > 160$, где $M'$ и $K'$ — количества масок и упаковок соответственно, обновлённые с учётом покупки ещё одной упаковки.

Остаётся лишь представить эти формулы в коде.

Задача «Склады»


Компания-застройщик занимается строительством недвижимости промышленного назначения, а именно складских помещений. Каждый квадратный метр площади стоит $L$ рублей. Компания имеет достаточный запас оборотных средств, чтобы продавать построенные помещения не сразу после завершения строительства, а в тот момент, когда ей это выгодно. Рынок недвижимости очень динамичный, поэтому цена квадратного метра меняется каждый день. Аналитики застройщика смогли точно спрогнозировать цену на ближайшие $N$ дней (пронумеруем дни в хронологическом порядке от $0$ до $N-1$). Теперь требуется определить, в какие из этих дней нужно продавать, чтобы по истечении $N$ дней заработать как можно больше денег. Известно, что стройка новых площадей происходит с равномерной скоростью $S$ кв. метров в сутки. А к нулевому дню объем построенной площади составлял $S$ кв. метров, при том что $S = 1$.

Формат входных данных


В первой строке вводится одно целое число $N (0 < N < 10000)$ — количество дней. Во второй строке вводится последовательность из $N$ целых положительных чисел — цена квадратного метра складской площади в каждый из дней.

Формат выходных данных


Вывести одно число — максимальное количество денег, которое может заработать компания-застройщик.

Решение
Применим «жадный» подход: будем продавать каждый построенный квадратный метр за максимальную цену. Пусть $L_i$ — цена квадратного метра складов в $i$-й день. Какая будет максимальная цена продажи квадратного метра, построенного к $i$-му дню? Так как продать его мы можем в любой день с $i$-го по $(N — 1)$-й, то и максимальная цена будет равна $\max(L_i, L_{i+1} \dots L_{N-1})$. Остаётся подсчитать этот максимум для каждого дня. Проще всего сделать это за квадратичную асимптотику, просто перебрав день продажи для каждого дня постройки.

Есть и другое, более быстрое решение задачи за линейное время! Для этого пройдём по массиву $L$ с конца, поддерживая наибольшее число среди рассмотренных элементов — это и будет искомая цена продажи!

Задача «Картины»


Максим решил заняться продажей картин на NFT-площадках, а для этого нужно придумать что-то свое и оригинальное. Максиму очень нравится, как выглядят цифры на черном фоне. Нужно написать программу, которая будет рисовать квадрат, состоящий из целых чисел и выводить информацию о его размере.

Формат входных данных


В одной строке через пробел вводится набор чисел или символов.

Формат выходных данных


В первой строке выводится сообщение «Квадрат со стороной N». В следующих строках требуется вывести квадрат, сформированный из набора чисел или символов, длина стороны — длина введённого массива.

Решение
Эта задача не вызывает трудностей у любителей программирования до тех пор, пока не выясняется, что решить её нужно с помощью скрипта на Bash. Задача чисто техническая, вот один из возможных способов решения:

  1. Для начала прочитаем массив из входных данных и узнаем его длину: 
    read line
array=($line)
len=${#array[@]}
  2. Затем выведем фразу про «квадрат»:
    echo "Квадрат со стороной $len"
  3. И в завершение воспользуемся циклом со счётчиком и отобразим исходный массив $len$ раз:
    for (( i = 0; i < $len; i++ )) do
    echo $line
done


Задача «Продажи»


В базе данных есть таблица Invoice следующего вида:


Напишите запрос, который покажет общие продажи по всем странам, отсортированные в порядке возрастания. На выходе в первой колонке должно быть название страны, а во второй показатель общих продаж.

На чемпионате во фразе «отсортированные в порядке» было некорректное склонение, что заставляло пользователей думать, что сортировать необходимо по странам. Это было оперативно исправлено и сейчас формулировка корректна.

Примечание: для решения задачи используется база данных 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 посчитает именно то, что мы хотим — сумму всех продаж для каждой страны.

Задача «Тайные покупатели»


Паша и Саша проживают в большом подмосковном городе, в котором $N$ районов. Не так давно два друга решили стать тайными покупателями в Ozon. Они решили подойти к делу очень ответственно, поэтому очень хотят обойти все пункты выдачи, посовещаться и выбрать самый лучший. В каждом районе города есть только одна точка выдачи. Внимательно изучив карту города, ребята поняли, что проверить все пункты у них физически не получится, уж очень далеко им придётся ходить, поэтому они решили ограничиться количеством путешествий, равным количеству всех возможных вариантов обхода, взятому по модулю $T$, а также решили позвать на помощь $M$ друзей, которые будут параллельно обходить точки. При этом каждому из друзей выделено разное подмножество пунктов выдачи: $N_{1}$, $N_{2}$, ..., $N_{m}$. Найдите количество вариантов обходов всех пунктов выдачи в произвольном порядке.

Примечание: Паша и Саша ходят вместе, а друзья поодиночке. Например, для $N=3$ есть 6 вариантов обходов ($abc$, $acb$, $bac$, $bca$, $cba$, $cab$), по модулю 6 это 0. А для $N=4$ — 24 варианта обходов ($abcd$, $abdc$,…, $dcba$). 24 по модулю 7 будет 3.

Формат входных данных


В первой строке вводится число $М (1 ≤ М < 1000)$. Далее на вход поступает $M+1$ строк, каждая из которых содержит два целых числа $N$ и $T$ ($1 ≤ n ≤ 10^{18}$, $1 ≤ T ≤ 10 000 000$).

Участников соревнования могло ввести в заблуждение неопределенность в ограничении $N$. Во время соревнования задание было дополнено, сейчас вам доступен финальный текст.


Формат выходных данных


Вывести $М+1$ чисел — количество обходов для каждого участника.

Решение
Нам нужно для $m+1$ пар чисел $n_i$ и $t_i$ найти остаток от деления факториала $n_i$ на $t_i$. При этом ограничения на $n_i$ слишком велики, чтобы вычислять этот факториал за линейное время.

Занимательный факт: для любых $a ≤ b$ каждое число $b!$ делится без остатка на $a$. Тогда возможны два случая:

  1. $n_i \ge t_i$: ответ $0$.
  2. $n_i < t_i$: можно посчитать факториал по модулю за линейное время (нам это позволяет ограничение на значение $t_i$).

Если раньше вы не работали с факториалом по модулю, то вот пример псевдокода его подсчёта:

fact = 1
for i from 2 to n
    fact = (fact * i) mod t


Задача «Маршруты»


Кирилл работает аналитиком в Ozon, и недавно ему в руки попал отчёт, из которого он понял, что время доставки товаров в пункты выдачи можно значительно сократить. Он заметил, что пункты выдачи в городе образуют выпуклый многоугольник с количеством вершин, равным $n$, и располагаются на его вершинах, где одна вершина = один пункт выдачи. Кирилл решил воспользоваться всеми прелестями современных технологий, он хочет проложить воздушные пути между пунктами выдачи, по которым будут перемещаться курьеры на грузоподъёмных реактивных ранцах.

Можно выбрать какое-то число $k$, при котором каждый пункт выдачи будет соединен с $k$ соседними пунктами выдачи слева и справа. Нужно найти минимальное $k$, чтобы кратчайшее расстояние между любыми двумя пунктами выдачи было меньше или равно $r$. Расстояние между пунктами выдачи примерно одинаковое, поэтому расстояние будет измеряться в количестве переходов, которые нужно сделать, чтобы попасть из одного пункта выдачи в другой.


Пояснение к примеру
  1. Если при $n = 6$ выбрать $k = 1$ (соединив каждую вершину только с одним ближайшим соседом слева и справа), то минимальное расстояние, например от узла $A$ до узла $D$ будет равно 3. Но $3 > r$, значит это решение не удовлетворяет условию.
  2. Если при $n = 6$ выбрать $k = 2$ (соединив каждую вершину с двумя ближайшими соседями с каждой стороны), то минимальное расстояние между любой парой вершин получается равным 2. Это удовлетворяет условию $2 ≤ r$, значит это верное решение.
  3. Для треугольника ($n = 3$) все вершины являются соседними друг другу, значит единственно возможным решением является $k = 1$, что удовлетворяет условию $1 ≤ r$.

Формат входных данных


В первую строку вводится одно целое число $P (1 ≤ R ≤ 100)$ — количество наборов входных данных. Для каждого набора входных данных в строку через пробел вводится два целых числа $n$ и $r$. Ограничения: $2 < n < 10^{18}$, $1 ≤ r < 10^{7}$.

Формат выходных данных


Для каждого набора чисел выведите минимальное $k$, удовлетворяющее условию.

Решение
Для решения этой задачи нам нужно вывести формулу. Если $n ≤ r$, то нам подойдёт любое $k$, поэтому ответ будет $1$. $n > r$ — интересный случай. Зафиксируем некоторую точку в многоугольнике. Тогда $\lfloor \frac{N}{2} \rfloor$ — расстояние до наиболее удалённой от неё точки при условии, что $k = 1$. Например, для случаев $n = 6$ и $n = 7$ наиболее удалённая точка находится на расстоянии $3$. Как изменится количество переходов, если увеличить $k$? Тогда мы сможем переходить не только в соседнюю точку, но и «прыгать» через $k-1$ точку. Например, если $\lfloor \frac{N}{2} \rfloor = 12$, то при $k = 3$ наиболее удалённая точка будет в четырёх переходах от зафиксированной.

А что будет, если $\lfloor \frac{N}{2} \rfloor$ не делится на $k$ без остатка? В этом случае для прохождения оставшегося пути нам понадобится ещё один переход. С этого момента есть способа решения: двоичный поиск по ответу или доработка формулы для получения минимального $k_{min} =\max( \lceil \frac{\lfloor \frac{N}{2} \rfloor}{r} \rceil,1) $. Возьмём максимум полученного значения и единицы, так как нам в любом случае нужно соединять точку хотя бы с одним соседом. Тогда для формулы $\lfloor \frac{N}{2} \rfloor < r$ мы можем получить $0$, например при $n = 8$ и $k = 5$.

Задача «Даты»


Напиши скрипт, который будет получать на вход stdin два параметра d1 и d2 в формате YYYY-MM-DD, и будет считать разницу между этими датами в днях. Скрипт проверяется на Bash 5.1.4 (запуск под Ubuntu 20.04).

Формат входных данных


Две даты через пробел в формате YYYY-MM-DD.

Формат выходных данных


Одно целое число — разница в днях.

Решение
Чтобы решить задачу, необходимо уметь пользоваться функцией date, которая позволяет получить из строки дату и преобразить её в формат unix time. Давайте так и поступим, затем найдём разность и переведём её в дни:

  1. Считываем даты из входного потока:
    read s1 s2
d1=`date -d "$s1" "+%Y-%m-%d"`
d2=`date -d "$s2" "+%Y-%m-%d"`
  2. Переводим даты в unix time:
    ut1=`date -d "$d1" +%s`
ut2=`date -d "$d2" +%s`
  3. Считаем разность секунд и переводим в дни:
    diff=$(($ut1 - $ut2))
diff_days=$(($diff / (60 * 60 * 24)))
  4. Выводим абсолютное значение разности (можно было бы написать if, но такой «чит» выглядит лаконичнее: он переводит значение в строку и удаляет лидирующий минус, если он есть):
    echo ${diff_days#-}

Бонус: уже после написания разбора обнаружилось два забавных факта:

  1. Во всех тестах вторая дата идёт хронологически позже первой.
  2. Формат даты в условии не надо дополнительно парсить, а можно сразу переводить в 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 следующего вида:


Напишите запрос, который будет искать трех продавцов на маркетплейсе, совершивших больше всего продаж, начиная с 2010 года. На выходе в первой колонке должны быть имя и фамилия продавца, а во второй количество их продаж, отсортированное в порядке убывания.

Примечание: для решения задачи используется база данных Chinook Database в формате SQLite — см. файл Chinook_Sqlite.sqlite. Также во время чемпионата у участников возникал вопрос относительно имени и фамилии в первой колонке таблицы. Поясним, что они должны быть через пробел.

Решение
Сначала нужно понять, как join-ить данные, чтобы получить таблицы продаж для каждого продавца. 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 следующего вида:


Напишите запрос, который составит рейтинг треков по их продаваемости, начиная с 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». Какая задача вам показалась самой лёгкой, а какая — наиболее сложной? А если вы нашли более эффективное или элегантное решение, делитесь в комментариях :)
Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.
Какую задачу вы считаете самой интересной?
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 пользователь. Воздержались 22 пользователя.
Теги:
Хабы:
Всего голосов 16: ↑13 и ↓3+23
Комментарии25
Ozon Tech
Команда разработки ведущего e‑com в России
10
Карма
0
Рейтинг
Роман Чудин @xe1by

Product Manager All Cups

Отправить сообщение

Публикации

Информация

Сайт
ozon.tech
Дата регистрации
Дата основания
Численность
5 001–10 000 человек
Местоположение
Россия

Ваш аккаунт

Разделы

Информация

Услуги

Техническая поддержка
© 2006–2024, Habr