Колонизация Марса

Такая вот задача, на одном из сайтов ее предагают решить перебором через рекурсию, как реализовать я вообще не представляю, поясните пожалуйста
Имя входного файла: стандартный ввод или in.txt
Имя выходного файла: стандартный вывод или out.txt
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 Мб
Ученым удалось отправить на планету Марс мини-фабрику, которая может за одни
сутки произвести мини-фабрику или дрона для сбора воды (мини-фабрика или дрон для сбора воды могут начать работу только со следующих суток). Дрон собирает одну единицу воды за одни сутки.
Определите, за какое минимальное количество суток удастся собрать не менее N единиц воды.
Формат входных данных
Задается одно число N (1 меньше или равно N меньше или равно 10^9) – необходимое количество воды.
Формат выходных данных
Одно целое число M – минимально необходимое количество суток.
Примеры:
стандартный ввод стандартный вывод
2 3
Замечание
Одна из правильных последовательностей действий выглядит так:
 В первые сутки мини-фабрика производит дрона для сбора воды;
 За вторые сутки мини-фабрика производит еще одного дрона, а первый дрон
собирает одну единицу воды;
 За третьи сутки мини-фабрика может произвести еще одного дрона или мини-
фабрику, при этом первый дрон собирает еще одну единицу воды (итого он собрал
2 единицы воды), а второй дрон собирает единицу воды. Таким образом, накоплено
3 единицы воды за трое суток.
Другая последовательность действий состоит в том, чтобы за первые сутки построить еще
одну мини-фабрику, а за вторые сутки произвести двух дронов, которые на третьи сутки
соберут 2 единицы воды.

0

Я её никогда не решал до сдачи, т.к. она была олимпийской задачей. Только на другом форуме обсуждал варианты решения.
Т.к. давать ссылки на другие форумы запрещено, приведу обсуждение. До кода тогда не дошло, т.к. рассуждали мы не торопясь, а олимпиада топикстартера завершилась.
Надеюсь - это поможет.

FPaul: Я сначала думал, что можно методом половинного деления. Ведь по одной из стратегий - сначала накапливаются фабрики, потом они выпускают водосборщиков и на следующий день есть N воды. По такой стратегии требуется (log2 N)+2 = (log2 10^9)+2=30+2=32 дня. Потом можно было бы придумать критерий - искать день, начиная с которого выпускаются только водовозы или искать соотношение между фабриками и водовозами в ежедневном выпуске. А с другой стороны - почему бы и не полный перебор - ограничения 2 секунды, и глубина погружения не более 32. Или комбинация перебора с двоичным поиском на каждых сутках.

FPaul: ...при накоплении фабрик их количество удваивается каждый день. 1 день 1 действующая фабрика (ДФ) производит 1 новую фабрику (НФ) 2 день 2 ДФ производят 2 НФ 3 день 4 ДФ производят 4 НФ ......................... 30 день 2^29 ДФ производят 2^29 НФ 31 день 2^30 = 1'073'741'824 ~ 10^9 ДФ производят 2^30 водовозов 32 день фабрики безразличны, а 10^9 водовозов добывают 10^9 воды.

Аатар: Для такой стратегии и итераций не нужно, просто найти минимальную степень двойки не меньшую N. Для малых N возможны нюансы. Насчет оптимальности вопрос

FPaul: Да, поэтому и предлагаю или полный перебор, ограниченный 32 днями. Или рекурсивный спуск с поиском соотношения производства в данный день для достижения минимума (улучшенный перебор). Почему-то ощущение, что будет один "горб=яма" в целевой функции на каждых сутках.

Так что рекурсия вполне применима. На каждом уровне погружения устраиваете цикл от 0 до Nфабрик - столько фабрик будет произведено и передаёте это на следующий уровень. Ограничиваете глубину - 32. После принципиальной работы программы - улучшайте путём сокращения вариантов.

0

Вот именно, я это и читал но все-равно не понял, можете написать тело функции чтобы до меня хоть что-то дошло, рекурсия оч сложно дается

0

Нет.
1. Это олимпиада, а не школьное задание.
2. У меня нет возможности проверить.

0