Самая длинная цепочка Коллатца
Возьмите натуральное число. Если оно чётное — разделите пополам, если нечётное — умножьте на три и прибавьте один. Повторяйте, пока не получится 1. Гипотеза Коллатца утверждает, что единица получается всегда, с какого числа ни начни; её проверили на компьютерах для всех чисел меньше 2⁶⁸, но доказать до сих пор не смогли.
Из 27 до единицы — 111 шагов, и по дороге число поднимается до 9232. Для каждого n найдите число от 1 до n, с которого путь до единицы самый длинный, и длину этого пути в шагах. Если таких чисел несколько, выведите наименьшее.
Вход
В первой строке q (1 ≤ q ≤ 100), дальше q чисел n (1 ≤ n ≤ 2·10⁶).
Выход
Для каждого n — начальное число и число шагов.
Примеры
Пример 1
5 1 2 3 10 27
1 0 2 1 3 7 9 19 27 111
Ограничения
- Время · Python
- 6000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 6 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Путь из 6 проходит через 3, путь из 7 — через 11, 17, 13, 10, 5… Сколько раз разные начальные числа пересчитывают один и тот же хвост?
2Идея
Запоминаем длину пути steps[k] для каждого k. Идём по k по возрастанию: путь из k шагаем, пока число не опустится ниже k — длина пути оттуда уже известна. Обычно это случается через несколько шагов: у чётного k — сразу.
3Разбор
Числа на пути поднимаются выше n — до 157 миллиардов для стартов до двух миллионов, — поэтому запоминать всё подряд в массиве нельзя. Здесь и не нужно: запоминаем только числа до n, а выше идём шагами. Можно запоминать и большие значения в словаре, но выигрыш невелик, а памяти уходит много.
Ответы для всех запросов дают одни и те же steps, поэтому таблицу строим один раз до наибольшего n, а для ответа храним «лучший старт не больше k» — это массив, который тянется за максимумом.
В Go значения на пути не помещаются в 32 бита: для стартов до двух миллионов они доходят до 1,6·10¹¹, нужен int64.
3+Решение
4Сложность
В среднем несколько шагов на каждое k до спуска ниже k — около O(n) на всю таблицу, плюс O(1) на запрос. Без памяти — около ста шагов на каждое из n чисел, да ещё для каждого запроса заново.
5Типичные ошибки
- Без памяти. Верно, но четвёртый тест — два миллиона путей целиком, а потом ещё миллион.
- 32-битные значения. Уже на пути из 113 383 число поднимается до 2 482 111 348 — выше 2³¹.
- Не наименьший старт. При равной длине ответ — меньшее число.