Игра
Игра
Джон и Джордж играют в следующую игру: Джон выбирает одно целое число x из множества An
= {1, 2, 3, ..., n}. Джордж должен угадать число x. Игроки совершают ходы последовательно = 1, 2, ... . На k-ом ходе игры Джордж выбирает подмножество Bk
из An
и Джон говорит YES, если x принадлежит Bk
или NO иначе. В случае ответа NO Джордж платит Джону a евро; в случае ответа YES Джордж платит Джону b евро. Мы хотим найти минимальную сумму в евро, которую Джордж должен заплатить, чтобы найти x, независимо от выбора Джона.
Напишите программу, которая вычислит требуемую минимальную сумму.
Входные данные
В одной строке заданы три целых числа n (1 < n < 1018
), a и b (0 < a, b < 1000).
Выходные данные
Выведите одно целое число, равное требуемой минимальной сумме в евро.
Объяснение
Джордж может найти x за 4 евро следующим образом:
Джордж выбирает множество B1
= {1, 2}.
Если ответ Джона YES, Джордж платит 2 евро и потом выбирает множество
B2
= {1}. Если следующий ответ YES, Джордж платит следующие 2 евро и игра заканчивается (задуманным было число 1), иначе он платит следующие 1 евро и игра заканчивается (задуманным было число 2).Если ответ Джона NO, Джордж платит 1 евро и потом выбирает множество
B2
= {3}. Если следующий ответ YES, Джордж платит следующие 2 евро и игра заканчивается (задуманным было число 3), иначе он платит следующие 1 евро и выбирает множествоB3
= {4}. Если последний ответ YES, Джордж платит следующие 2 евро и игра заканчивается (задуманным было число 4), иначе Джордж платит следующие 1 евро и игра заканчивается (задуманным было число 5).
5 1 2
4