Puzzle #79. Жадный банкомат
UniLecsРазбор
Итак, чтобы при заданных ограничениях получить максимально возможную сумму, нужно 100 раз запросить 50 рублей (или 100 раз 51 рубль).
Теперь докажем, что невозможно гарантировать большую сумму. Представим себе, что рядом с вами стоит банкир, который знает номиналы карточек. Вы называет сумму, а банкир выбирает одну из карточек и вставляет ее в банкомат. Тогда достаточно найти стратегию для банкира, при которой вы не можете получить более 2550 рублей.
Стратегия банкира: когда вы называете сумму, он вставляет произвольную карточку с номиналом, меньшим названной суммы, если таковая имеется, и карточку с максимальным номиналом из имеющихся на руках в противном случае.
- в 1м случае карточка после использования называется выкинутой;
- во 2м – реализованной. Очевидно, что вы получаете деньги только с реализованных карточек, причем карточки реализуются в порядке убывания номиналов.
Пусть наибольший платеж составляет N рублей и этот платеж реализует карточку с номиналом M рублей, M >= N.
Заметим, что
- К моменту этого платежа карточки с номиналом, меньшим N рублей, уже съедены.
- Все эти карточки выкинуты. Действительно, карточка с номиналом K рублей при K < N не могла быть реализована раньше карточки с номиналом M рублей, поскольку K < M.
Таким образом, общее число реализованных карточек не превосходит (100 − N + 1). С каждой реализованной карточки вы получаете не более N рублей, поэтому общая сумма не превосходит N×(100 − N + 1), а максимум достигается при N = 50 и N = 51.