Раньше перед постройкой амбара я всегда задумывался – когда же его выгоднее построить: когда город только что вырос или же когда ему остаётся чуть-чуть до роста? Определить какую-нибудь зависимость у меня не получалось…

Было немного свободного времени – решил разобраться в этом вопросе. Вот что получилось


Обозначения:
Nr – количество буханок необходимых чтоб город размером r вырос на 1 население (например N4 - количество буханок необходимых, чтобы город размером 4 вырос до населения 5).
Zr - количество буханок запасённых в городе размером r на момент постройки амбара.

Рассматривал всё на городе размером 4 (на других размерах, наверное, всё аналогично… наверное ). Строил в этом городе амбар при различных Z4 и смотрел, каково будет Z5 непосредственно после роста города. Ниже приведена таблица полученных результатов. В нёй по столбцам – Z4. По строкам – количество перелива буханок при росте (то есть если до роста города осталось 2 буханок, а в городе производится лишними 5 буханок, то перелив = 3). В самой таблице – Z5 непосредственно после роста города (уже с построенным амбаром).



(естественно, что не все числа я проверял… проверил только некоторые– остальные додумывал )

Из таблицы видно, что может быть две различные ситуации.

Ситуация №1: Zr <= Nr/2 (в данной таблице этой ситуации соответствует первый столбец)

В этом случае Z(r+1) после роста = Nr/2 + перелив.
Для города размером 4: Nr = 28 и соответственно Zr = 14 + перелив.

Ситуация №2: Zr > Nr/2 (в данной таблице этой ситуации соответствуют все столбцы, начиная со второго)

В этом случае Z(r+1) после роста сложно зависит от перелива. Можно получить формулу, описывающую это зависимость, но особого смысла в этом нет. Главное другое: если посмотреть в любую строчку видно, что максимальное значение Z(r+1) равно значению Z(r+1) из первого столбца. А значения из других столбцов < или = ему. То есть Ситуация №1 во всяком случае, не хуже чем Ситуация №2.

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