Problem 327: Rooms of Doom
Ряд из трех комнат соединены друг с другом автоматическими дверями.
Каждая дверь управляется картой безопасности. Когда вы входите в комнату, дверь автоматически закрывается и эта карта безопасности не может быть использована снова. Машина с самого начала будет раздавать неограниченное количество карт, но каждая комната (включая стартовую) содержит сканеры, и если они обнаруживают, что у вас есть более трех карт безопасности или если они обнаруживают на полу автоматическую карту безопасности, все двери будут постоянно заперты. Тем не менее, каждая комната содержит коробку, в которой вы можете безопасно хранить любое количество карт безопасности для использования на более позднем этапе.
Если вы просто попытались проехать по комнатам по одному, а затем, когда вы вошли в комнату 3, вы бы использовали все три карты и были бы в ловушке в этой комнате навсегда!
Тем не менее, если вы используете ящики для хранения, то возможен выход. Например, вы можете войти в комнату 1 с помощью своей первой карты, поместить одну карту в ящик для хранения и использовать свою третью карту, чтобы выйти из комнаты до начала. Затем, собрав еще три карты из раздаточной машины, вы можете использовать ее для входа в комнату 1 и собрать карту, которую вы разместили в коробке минуту назад. Теперь у вас есть еще три карты и вы сможете проехать через оставшиеся три двери. Этот метод позволяет путешествовать по всем трем комнатам, используя в общей сложности шесть карт безопасности.
Можно путешествовать по шести комнатам, используя в общей сложности 123 карты безопасности, имея максимум 3 карты.
Пусть C - максимальное количество карточек, которые можно переносить в любое время. Пусть R - количество комнат для проезда. Пусть M (C, R) - минимальное количество карточек, требуемых от раздаточной машины, для перемещения по номерам R, несущим до максимума карты C в любое время.
Например, M (3,6) = 123 и M (4,6) = 23.And, ΣM (C, 6) = 146 для 3 ≤ C ≤ 4.
Вам дается, что ΣM (C, 10) = 10382 для 3 ≤ C ≤ 10.
Найти ΣM (C, 30) для 3 ≤ C ≤ 40.