Comments 6
Тут можно попробовать решить с ограничением до 10^18. Сам я её решал, найдя какие-то закономерности в максимумах (их было легко найти, выписав первые несколько из них), потом сгенерировал все числа, которые удовлетворяют полученным условиям (их оказалось не очень много - порядка пары десятков тысяч, если мне память не изменяет), а дальше просто отфильтровал сгенерированные, оставив те, которые реально являются максимумами.
Уверен, что упомянутый вами способ имеется. Я потратил много времени пытаясь пройти вашим путем решения задачи. Из-за этого даже завидую вам. Возможно и я бы на него наткнулся, если бы не начал анализировать бинарное представление промежутков между рекордсменами. В итоге у меня максимально высокая производительность программы и скорее я упрусь в переполнение числовых типов данных, чем в то, что превышу данное время на исполнение в 1 секунду при увеличении зоны поиска.
Примечательно, что в вашей задаче дается всего 64MB ОЗУ при еще большем диапазоне поиска максимума. Такие ограничения выглядят еще более суровыми. Каким языком программирования вы воспользовались?
Pascal. Кстати, даже интересно, каким методом я решу эту задачу сейчас с учётом того, что олимпиадного опыта у меня сейчас заметно больше, чем тогда. Сейчас тот метод мне кажется каким-то диким шаманством :)
Большим опытом в олимпиадном программировании похвастаться не могу, но в энтерпрайз проектах я уже скоро пятнадцатилетие отмечу. На этом фоне могу сказать, что навыки из олимпиадного программирования важны и в реальных проектах.
Все пригодилось:
анализ сложности алгоритма - как не удивительно, но часто помогает уменьшить когнитивную нагрузку, которой нагружает код своего читателя
понимание комбинаторики - пригождается при анализе сложности интерфейса микросервиса/модуля/библиотеки
понимание теории вероятностей - часто пригождается при проверке на нарушение SRP из SOLID (выявление вероятности изменения части кода, которая может подвергнуться изменениям при изменении требований к проекту) и при организации работы с брокером сообщений
...
Конечно, применяются эти навыки не так как при решении олимпиадных задач. Тут больше работает понимание принципов. Но один раз был случай и прямого применения, когда нужно было сопоставить две масштабные базы данных продуктов из разных магазинов с разными структурами определяющими свойства продуктов и объединить в единую систему категоризации с единой структурой свойств - чем не олимпиадное программирование?
Просто хотел сказать, что с ростом навыков можно не только олимпиадные задачи пересмотреть, но и боевые проекты.
Да, я бы тоже сгенерировал словарь координат максимумов, и дальше его использовал. Не всегда в реальных проектах есть формулы для точного вычисления. Но автору, безусловно, респект
Спасибо! В реальных проектах почти не встречаются значения 
. На Земле вообще нет ничего, что можно было бы измерять такими числами при автоматизации бизнеса, кроме Big Data. Такие числа встречаются в астрономии, но астрономам, предполагаю, нет дела до fusc последовательности и ее рекордсменов. Думаю, единственное их место применения - теория чисел и комбинаторика. Причем прикладной смысл будут иметь только производные формулы и числовые последовательности. Так что полностью согласен с вашими словами.
Рекордсмены в Fusc последовательности