Здраствуйте.
Есть вот такая вот задачка:
"Сначала есть число 5. Безконечное число раз повторяли такое действие: в конец числа копировали самого себя и в второй половине все 5 заменяли на 7, а 7 на 5. Тоисть получось такое: 5
потом 57, потом 5775 потом 57757557 и т.д..
разсотрим такю бесконечнюю последовательность цыфр слева на право
Нужно найти N цифр подряд, начиная с позицыи М
1 <= N <= 1000;
1 <= M <= 1000000000
Например
N=5
M=2
Ответ: 77575"

Понимаю что есть какая то закономерность и можно восоздать кусок строки с нужного символа.. не строя всей строки, но что-то никак сообразить не могу.
Может у кого то есть идеи?

Это сообщение отредактировал(а) Алкоголик - 11.3.2009, 22:14

Битовая задачка.


5 0
7 1
7 10 
5 11
7 100
5 101
5 110
7 111

Как говорится, найдите закономерность.

Hint - чётность количества единиц.

Можно не искать никаких закономерностей, а просто промоделируем процесс для нужного кусочка.

Пусть мы знаем номер K шага (т.е. текущая строка - эта строка, полученная из 5 применением K раз этой операции), и даётся отрезок [A;B]; нужно вернуть строку в этом отрезке. Тогда посмотрим, в какой половине лежит этот отрезок [A;B] - если в левой, то вызовем себя от (K-1, A, B), если в правой, то вызовем себя от (K-1,A,B) и в возвращённой строке обменяем символы 5 и 7 (как описано в условии), если же [A;B] попадает и туда, и туда (т.е. есть непустые отрезки [A;2^(K-1)] и [2^(K-1)+1;B]), то отдельно обрабатываем каждый из них, как описано в предыдущих пунктах, и склеиваем результаты. Особый случай (завершение рекурсии) - если K=1, то просто возвращаем '5'.

Понятно, что чтобы найти ответ на задачу, надо вызвать эту функцию с аргументами (K,M,M+N-1), где K - это такое число, что 2^K>=M+N-1.

Оценка асимптотики (грубая) - O(N^2 log(N+M)), что при данных ограничениях вполне укладывается. Откуда она берётся - всего есть K уровней рекурсии, причём K = O(log(N+M)). На каждом уровне рекурсии, утверждается, функция работала не более N раз. Наконец, один вызов рекурсии (не считая нижележащих уровней) работает за O(N) - затраты на склеивание двух строк и исправление пятёрок и семёрок. В итоге действительно log(N+M) * N * N.

Реализация получится очень простой, намного короче, чем её описание 

Добавлено через 8 минут и 13 секунд
Akina
Красивое решение, но не зная наперёд, что оно возможно, как-то трудно до него догадаться 

Это сообщение отредактировал(а) maxdiver - 11.3.2009, 23:49

Заняв какое-то место, цифра более не меняется, независимо от количества шагов. Значит, надо посчитать количество инверсий до текущего места.

Впервые увидел эту задачу. Решение родилось через 3 минуты.

Akina,  большое спасибо за ваше решение, с помощью его и реализовал...очень красиво...
maxdiver, Вам тоже спасибо, вот ваше решение и вертелось в голове, но никак не мог полностью оформить его в мысль))