Задачка от Т-Банка, тоже с собеседования - по сравнению с предыдущей что я показывал, от Яндекса, эта кажется ещё менее актуальной для рекрутинга в энтерпрайз - но я просто порадовался что смог её решить в live-coding режиме. Судите сами - хотели бы вы подобное встретить на собесе или нет :)))

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

• разовый билет стоит 5 копеек

• безлимитный проездной на 2 дня - 18 копеек

• проездной на 3 дня с лимитом 6 поездок - 22 копейки

Входные данные - массив - сколько поездок пришлось на каждый день в месяце, например:

2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 3 4

(здесь ответ 51)

Как это решается? Если вы знаете про "динамическое программирование" (ДП) то наверное уже поняли что задача об этом - поэтому я и удивился встретив такую задачу на собесе - скорее всего нам это не понадобится в энтерпрайзе (хотя в олимпиадных задачках популярно). Если не знаете про ДП, представьте рекурсию - вы пробуете в цикле каждый из трёх типов билетов, ездите сколько он позволяет - и дальше снова вызываете эту функцию для оставшихся поездок. Просто с рекурсией вы не дождётесь окончания работы, но с "мемоизацией" получите то же ДП "навывоворот". Я возился минут 30, но повтороив задачу у себя на сайте увидел что друзья решают аж в 3-4 строчки (ну, на питоне с @cache).