Babylon Tower — достижение взято
Вчера после долгих поисков нашел на CodinGame задачу, которую легко можно было решить с помощью bash-скрипта. Все-таки сколько я, оказывается, о bash не знаю! В частности, не знал, что там можно использовать массивы, правда, с крайне неудобным синтаксисом. Потом тут же решил легкую задачку на C++ (заодно понял, что ощутим его подзабыл, в отличие от чистого C, на котором хотя бы иногда что-то пишу). В результате до достижения Babylon Tower, которое дают за решение задач на 15 разных языках программирования, осталось использовать всего один язык программирования. Им, как и планировалось, стал Kotlin, изучением которого я хотел заняться уже давно, но, как всегда, бессознательное протестовало против планов, поэтому вместо него стал писать на Lua и Ruby.
Требовалось решить задачу, которая сначала казалась предельно простой: найти минимальное N при котором a^N оказывается меньше N!. Казалось бы, достаточно пройтись циклом, и решение будет найдено. Но я не учел одного: того, что тесты для решения содержали весьма большие числа (такие,что N уходил за тысячу). И для подсчета «в лоб» попросту не хватало разрядности чисел (тем более в Kotlin, как и в Java, максимальная разрядность для чисел с плавающей точкой — 64 бита, а не 80).
Пришлось включать мозг и искать обходное решение. Оно нашлось довольно быстро. Сначала я решил попытаться получить результат через аппроксимацию факториала. Но увы, аппроксимация есть аппроксимация: N находилось с точностью до нескольких соседних чисел. По сути дела, ее можно было использовать как верхнюю оценку N, и дальше уменьшать его, проверяя выполнение неравенства на каждом шаге. Но как проверить неравенство, если и справа и слева значение вылезает за пределы допустимого? Поломав голову, вспомнил совет, когда-то давно виденный на Хабре: работать не с самими числами, а с их логарифмами. Тут я сообразил, что нужно взять логарифм от факториала можно посчитать как сумму логарифмов отдельных множителей. А с другой частью — все и того проще: N*ln(A).
Как только я это реализовал, программа тут же заработала как надо, и я получил долгожданное достижение Babylon Tower (впервые о нем я начал думать еще с лета, если не раньше).
Требовалось решить задачу, которая сначала казалась предельно простой: найти минимальное N при котором a^N оказывается меньше N!. Казалось бы, достаточно пройтись циклом, и решение будет найдено. Но я не учел одного: того, что тесты для решения содержали весьма большие числа (такие,что N уходил за тысячу). И для подсчета «в лоб» попросту не хватало разрядности чисел (тем более в Kotlin, как и в Java, максимальная разрядность для чисел с плавающей точкой — 64 бита, а не 80).
Пришлось включать мозг и искать обходное решение. Оно нашлось довольно быстро. Сначала я решил попытаться получить результат через аппроксимацию факториала. Но увы, аппроксимация есть аппроксимация: N находилось с точностью до нескольких соседних чисел. По сути дела, ее можно было использовать как верхнюю оценку N, и дальше уменьшать его, проверяя выполнение неравенства на каждом шаге. Но как проверить неравенство, если и справа и слева значение вылезает за пределы допустимого? Поломав голову, вспомнил совет, когда-то давно виденный на Хабре: работать не с самими числами, а с их логарифмами. Тут я сообразил, что нужно взять логарифм от факториала можно посчитать как сумму логарифмов отдельных множителей. А с другой частью — все и того проще: N*ln(A).
Как только я это реализовал, программа тут же заработала как надо, и я получил долгожданное достижение Babylon Tower (впервые о нем я начал думать еще с лета, если не раньше).
