Привет! Подошел к концу двенадцатый набор в Школу Программистов hh.ru. Самое время рассказать, как Петр Васильевич раздавал премии менеджерам, кто вышел победителем из "Релиза до выходных" благодаря ролевому помощнику, и как впервые в истории Школы нам пришлось облегчить условия вступительного задания прямо во время набора. 

В этой статье будет подробный разбор заданий свежего набора в Школу Программистов hh.ru.

Прежде чем перейти к сути, немного общей информации о наборе и Школе в целом.

Как мы выбираем задачи

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

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

Стараемся выбирать задачи, которые требуют не только знания определенного алгоритма, но заставляют подумать и внимательно отнестись к условию. Решения для таких задач тоже пишем мы, подключая добровольцев из коллег. Затем проводим кросс-тестирование и создаем набор тестов на крайние случаи. Чтобы исключить возможность решения перебором, после всех маленьких тестов создаем парочку больших, призванных вылезать за ограничения по времени или памяти на совсем уж не оптимальных алгоритмах.

Потом задачи адаптируются, появляется небольшой сюжет и аранжировка для колорита и уникальности.

Процесс

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

Всего, в этом наборе поучаствовало 3400 человек. Одно задание решили 384 участника, а с обеими задачами справились 190. В этом году мы приняли в Школу 50 человек, и это самое большое число участников за всю историю.

Задач, как обычно, было две — одна попроще, другая посложнее.

Задача 1. Премия

Петр Васильевич, директор ОАО "Рога и рога", собирается раздать премию всем менеджерам компании, он добрый и честный человек, поэтому хочет соблюсти следующие условия:

• премия должна быть равной для всех менеджеров

• должна быть максимально возможной и целой

• должна быть выдана одной транзакцией с одного счета для каждого менеджера, без использования нескольких счетов для отправки одной премии

У Петра Васильевича открыто N корпоративных счетов, на которых лежат разные суммы денег Cn, а в компании работает M менеджеров. Необходимо выяснить максимальный размер премии, которую можно отправить с учетом условий. Если денег на счетах компании не хватит на то, чтобы выдать премию хотя бы по 1 у.е. - значит премии не будет, и нужно вывести 0.

Условие этой задачи довольно простое, казалось бы, давайте просто сложим все Cn и поделим сумму на количество менеджеров, однако, если подумать, то станет понятно, что при этом в большинстве случаев невозможно будет соблюсти третье условие. Хотя бы для одной премии придется перекидывать деньги со счета на счет, или выдавать ее несколькими транзакциями.

Для такого примера:

4 6
199
453
220
601

Правильным ответом будет 200, в нем 2 премии по 200 у.е. мы выдаем со второго счета, 1 с третьего счета, и 3 с четвертого. И выдать 201 уже не получится, как раз из-за третьего условия, потому как денег на четвертом счете не хватит.

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

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

Решение на Python:

N, M = [int(x) for x in input().split()]  # Читаем N и M в первой строке
C = [int(input()) for _ in range(N)]  # Читаем Cn в последующих строках

def get_max_bonus(managers_count, accounts):
    max_amount = sum(accounts) // managers_count  # максимум - средняя сумма на менеджера
    # // - оператор деления с округлением в меньшую сторону до целого
    if max_amount == 0:  # если она равна 0 – можно выйти сразу
        return 0

    rounded_middle = 1
    min_amount = 1  # начинаем с 1, потому что 0 уже не может быть
    transactions = managers_count

    # Бинарный поиск, второе условие компенсирует перебор
    while max_amount - min_amount >= 0.5 or transactions < managers_count:
        # пробуем сумму между максимальным и минимальным
        middle = (min_amount + max_amount) / 2
        rounded_middle = round(middle)

        # вычисляем количество транзакций (целых премий) с такой суммой
        transactions = sum([x // rounded_middle for x in accounts if x >= rounded_middle])
        if transactions < managers_count:
            max_amount = middle  # сужаем сверху при недоборе
        else:
            min_amount = middle  # сужаем снизу при переборе

    return rounded_middle

print(get_max_bonus(M, C))

Задача 2. Ролевой помощник

По пятницам мы часто играем в популярную ролевую игру "Релиз до выходных" с коллегами. Правила этой игры довольно сложны и предполагают хорошую стратегию и планирование. Чтобы иметь представление о последствиях тех или иных ходов, часто хочется понимать, насколько вероятен тот или иной исход ситуации, с учетом разных вариантов выпадения игральных костей.

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

Выражение на входе может содержать скобки, и следующие операторы в порядке уменьшения их приоритета:

• * – умножение

• + и - – сложение и вычитание

• > - левый операнд больше, чем правый. Результат равен 1, если истинно, и 0 - если ложно

Операторы равного приоритета выполняются слева направо.

В качестве операндов могут выступать:

• n - целые положительные числа, либо 0 (0≤n≤100 000)

• dn - результат броска игральной кости, где n целое положительное число, количество граней (1≤n≤100). Результатом будет равномерное распределение вероятностей между всеми гранями (от 1 до n). Каждый такой операнд в выражении – это результат отдельного броска (например, d4+d4 – это сумма результатов двух разных бросков четырехгранной кости).

Например, для входной строки d4+(d6>2) правильным ответом будет:

1 8.33
2 25.00
3 25.00
4 25.00
5 16.67

Задание непростое, решение для него нетривиальное. Настолько непростое, что за первые 4 дня с ним справился всего один участник. Это было неожиданно, но причина крылась не в алгоритме, а в количестве вариантов на выходе. Об этом расскажу ниже.

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

О чем вообще речь

Давайте начнем с указанного примера и дойдем до решения руками, сперва расшифруем в нем броски костей, получится примерно следующее: [1,2,3,4]+([1,2,3,4,5,6]>2).

Далее, применим оператор > в скобках. В связи с тем, что левым оператором является бросок кости – на выходе могут быть разные результаты, поэтому, применяем оператор ко всем вариантам выпадения, получится [1,2,3,4]+([0,0,1,1,1,1]).

Последнее, что необходимо сделать – это сложить каждый из левых операндов, с каждым из правых, получится набор из 24 чисел, среди которых будут повторения, итоговый набор [2x1, 6x2, 6x3, 6x4, 4x5]. Если поделить количество повторов на общее количество вариантов, как раз получим вероятности, и они будут совпадать с ответом.

Решение руками довольно простое для маленьких выражений, но как научить такому алгоритм? Лучше разделить решение на 2 последовательные части: расшифровка и вычисление. То есть сначала необходимо расположить операторы в правильном порядке выполнения, а затем просто посчитать результат.

Расшифровка

Для примера выше, глаз сам выделяет то, что должно быть сделано в первую очередь, а вот для такого уже будет немного сложнее: 2*(1+2>3+4*5+10-100*2). Если думать об универсальном решении, есть несколько существующих алгоритмов разбора строк такого вида, и самый известный из них – алгоритм сортировочной станции (shunting-yard). О нем можно почитать отдельно, смысл сводится к последовательному чтению символов строки и выстраиванию стека операндов и операций в нужном порядке.

Из особенностей и сложностей можно отметить необычное поведение оператора >, он не является ассоциативным (результат зависит от порядка операндов), поэтому для него нужно было реализовать отдельную логику, заставляющую алгоритм вычислять такие операторы слева направо. По этой же причине, обычный eval без доработок в js и python выдавал неправильные результаты, он вычисляет такие операторы справа налево.

В целом, многие участники реализовали именно его, однако, с большим разнообразием вариантов реализации и серьезными различиями в логике.

Вычисление

Помимо правильного порядка вычислений было необходимо сделать подсчет с учетом игральных костей, которые, по сути, являются целым массивом операндов, а не одним. В этой части алгоритма сложностью была не логика, а ограничения памяти, потому что количество результатов резко может вырасти многократно.

Для ограничения количества и снижения нагрузки на память, нужно оптимизировать хранение результатов. Например, используя объекты с результатами и количеством таких результатов в общем пуле.

Как раз из-за этой неочевидной оптимизации, которая приводила к множеству превышений лимитов, мы упростили тесты, убрав два, и ограничив максимальное число граней:

d10+d10+d10+d10+d10+d10+d10+d10+d10+d10>55
0 52.16
1 47.84

d100000>10000
0 10.00
1 90.00

Можете попробовать на них свое решение, если оно успевает по времени (1 секунда) и памяти (64 МБ) – вы справились на отлично!

Репозиторий, в котором можно на всё это посмотреть, и даже потестировать свои решения: https://github.com/hhru/school-tasks-tester

До встречи

Всем принимавшим участие в наборе большое спасибо! Надеемся, вам понравились задачки. И еще раз поздравляем всех поступивших в Школу.

Тем, у кого в этом году не получилось, предлагаем не расстраиваться, а прокачаться и попробовать себя в следующем году. 

Как говорят на Руси, stay tuned!