Два миллионера играют в следующую игру. На столе вначале игры лежит 1000 кучек по одной спичке в каждой. Игрок может за один ход сложить любые две кучки спичек вместе, при этом противник дает ему столько рублей, сколько было спичек в большей кучке. — задача №700733

Дано

• Исходное состояние: $N = 1000$ кучек по $1$ спичке в каждой.
• Правило хода: игрок объединяет две кучки размерами $a$ и $b$ (где $a \ge b$).
• Выигрыш за ход: игрок получает $a$ рублей.
• Цель: получить максимальную прибыль к моменту, когда все спички окажутся в одной кучке.

Решение

1. Анализ процесса объединения Пусть в какой-то момент у нас есть кучки размеров $x_1, x_2, \dots, x_k$. Когда мы объединяем две кучки $a$ и $b$ ($a \ge b$), мы получаем новую кучку размером $a+b$, а наш капитал увеличивается на $a$. Заметим, что общее количество спичек всегда равно $1000$. Что...