Насіння

На ринку є ряд із $N$ місць, де продається насіння соняшника. Потенційні покупці проходять уздовж цього ряду, зрештою зупиняючись, щоб купити насіння. Якість насіння на всіх місцях однакова, тому різниця лише у ціні та розташуванні місця.

Перш ніж вийти на ринок новим продавцем насіння, ви провели дослідження, щоб зрозуміти, як кількість покупців залежить від цих двох факторів. Дослідження показало, що більшість покупців дотримуються подібного алгоритму: проходячи повз кілька місць, вони запам'ятовують ціни, а після того, як пройдуть $K$ місць, повертаються до місця з найнижчою ціною серед побачених і купують там. Якщо таких місць декілька, покупець вибирає те, яке знаходиться до нього ближче.

Наприклад, є п'ять місць із цінами $37$, $34$, $34$, $35$, $33$. Якщо покупець із K=4 рухається зліва направо, він переглядає ціни $37$, $34$, $34$, $35$. У цей момент він вирішує, що побачив достатньо, повертається до третього місця та купує там. Хоча друге місце має таку ж ціну, воно для даного покупця далі. Якщо той самий покупець заходить справа, то він бачить ціни $33$, $35$, $34$, $34$ і повертається до п’ятого місця.

Кількість місць, які проходить покупець, перш ніж прийняти рішення ($K$), залежить від жадібності та терплячості кожного і є різною для різних покупців. Дослідження дає середній відсоток B_K покупців для кожного $K$ (1 \leq K \leq N,\ 0 \leq B_K \leq 99), причому сума всіх B_K дорівнює $100$.

Вам потрібно визначити оптимальну стратегію на цьому ринку (тобто ціну та розміщення нового місця для максимізації очікуваного середнього доходу), враховуючи, що половина покупців рухається від першого місця до $N$-го, а інша половина — від $N$-го до першого, причому всі вони дотримуються описаного алгоритму.