Последовательность Кеане Опции

[Unconnected]

Привет всем

Пробую решить олимпиадную задачку (конечно, с уже давно окончившейся олимпиады )), про последовательность (битов) Кеане - кто этот Кеане, я не знаю, и Вики с гуглом тоже. Формулировка такая:

Последовательность Кеане
(Время: 1 сек. Память: 16 Мб Сложность: 57%)

Бесконечная последовательность битов, предложенная Кеане, равна 001001110001001110110110001… и формируется следующим алгоритмом: вначале записывается 0, потом 001, далее 001001110, то есть, для получения следующего члена, предыдущий записывается дважды, а справа приписывается его отрицание. Элементы этого ряда являются начальными подпоследовательностями Кеане.

Требуется написать программу, которая по заданному n определит N-й бит этой последовательности.
Входные данные

Входной файл INPUT.TXT содержит число N (N <= 10²⁰⁰).
Выходные данные

В выходной файл OUTPUT.TXT должен содержать найденный бит.

Просто генерировать последовательность у меня получается, вот так:

{$APPTYPE CONSOLE}

var n:int64;
    s:string;

function invers(s:string):string;
var i:integer;
begin
  for i:=1 to length(s) do if s[i]='0' then result:=result+'1' else result:=result+'0';
end;

begin
  assign(input,'input.txt');
  readln(n);
  s:='0';
  while (length(s)<=n) do s:=s+s+invers(s);
  assign(output,'output.txt');
  writeln(s[n]);
end.

(хотя, у меня такое ощущение, что она как-то неправильно генерирует)

Проблема в очень большом максимально возможном N. Здесь, видимо нужно использовать длинную арифметику, но я вот не понимаю, в каком месте её использовать. Ну допустим есть строка-последовательность, есть N в виде строки, и что с чем складывать? Кажется, даже строку с последовательностью такой длины получить не получится, и тем более length() от неё. Может, формулу можно вывести для нахождения бита по позиции?

Сообщение отредактировано: Unconnected - 5.06.2010 21:22

[Unconnected]

Сейчас дорассмотрел наконец код volvo (лето, напряжёнка ) ), для небольших чисел это наверное и будет самый оптимальный вариант (погонял, кстати - string- и calceulated-результаты соответствуют), а вот если взять n=10²⁰⁰ - то я, например, даже не представляю, как находить для него логарифм и т.п. с помощью длинной арифметики. (благодарю за код, познавательно!)

Последовательность состоит из элементарных 001 и 110 (при n>=3). Может, обозначать их нулём и единицей, к примеру? Тогда генерировать меньше будет, и находить быстрее.

Lapp, не совсем понял насчёт этих положений. Ну и что с того, что длина выражается степенью тройки? Это как-то поможет в нахождении нужного члена?

[Lapp]

Ну и что с того, что длина выражается степенью тройки? Это как-то поможет в нахождении нужного члена?

Так volvo же это как раз и использовал! трихотомия ))