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

[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