Всем привет!
Праздники кончились, и наступила сессия. На голову студентов сразу обрушилось множество проблем. Долги растут, а времени их сдать - все меньше и меньше. Думаю, всем вам знакома эта ситуация. Осознавать ее и бездействовать - просто невыносимо, и недавно я понял, что больше так не могу. Выход был один - перебороть лень, собрать всю волю в кулак и начать наконец писать... январский 10-дневный контест на codechef.com :)
Мне кажется, это было правильное решение. Голова прояснилась, и несколько дней пролетели незаметно. План-минимум гласил - нужно попасть в Top-10 Global, чтобы получить... а что получить? Несколько раз, краем уха я слышал про прикольные призы, высылаемые лидерам контестов. Начиная от футболок, и заканчивая наклейками и деньгами. Подробностей я не уточнял. Мне почему-то казалось, что попадание в десятку лучших на контесте профильного формата - это хорошо, и должно обязательно повлечь за собой приятные сувениры. Но контест шел, времени было мало, а смысла думать о призах - еще меньше...
даютдавали за попадение в десятку. Правда, они в последнее время почему-то перестали их присылать.Блин... задачу http://www.codechef.com/JAN12/problems/MISINT2 свёл к нахождению n-го члена последовательности https://oeis.org/A081844 , но как за разумное время его найти так и не придумал. Почитал разбор - не осилил, забил, ибо там начались жуткие вещи :)
По теме: за октябрьский лонг отозвались и спросили только 9-го декабря куда высылать футболку ... ну и соответственно щас ещё ничего не приходило...
мне нравится разбор MISINT2: докажем формулу
интересно, как прикажете ее выводить когда ее не знаешь?
Я просто посчитал для n до 100, а там понятно, что при (2*n) надо действовать также как и при (2*n+1), так как символ на месте (2*n+1) встанет на это же место. Поэтому я вбил в oeis те числа, которые стоят на нечётных местах. Вылезла эта последовательность :)
Очень крутая задача...
Я шел другим путем. Есть такая известная перестановка - Perfect shuffle (Faro shuffle) - есественно возникает при тасовке игральных карт слиянием. Она же используется в нетривиальных алгоритмах inplace_merge, обеспечивая логарифмическую (или даже константную, не помню) дополнительную память. Так вот, она в некотором роде эквивалентна перестановке из нашей задачи. В том числе, и по количеству циклов. Почитав статьи с анализом этих алгоритмов, можно натолкнуться на вышеприведенную формулу. Далее - дело техники. Но я бы сказал, магии :) Разбор еще не читал, но в моем случае было достаточно сложно уложить программу в местный ТЛ. Машины там слабоваты... :( Ну, еще - немного теории чисел.
P.S.: по теме треда - сегодня пришло уведомление от индусов, с просьбой _подтвердить_ данные и адрес. Те, что взяты с сайта. Судя по всему, к словам Egor они все-таки прислушались.
P.P.S.: да, я тоже использовал OEIS :)