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

[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 17:22

[volvo]

Да. Не совсем так... Правда. Нужно кое-что добавить:

  // после строки:
  if negate then res := inverted[res];
  // вот это надо добавить:
  if(power(k) - 1) div 2 = n then res := inverted[res];

Тогда для любого N > 1 (особый случай N = 1 обрабатывается отдельно, в ветке else основного if-а, который с циклом repeat/until), от 2 до 21 миллиона (больше не проверял, ждать генерации последовательности для сравнения приходится очень долго) программа выдает одинаковый результат при вычислении значения заданного бита и при его извлечении из последовательности. Это достаточный критерий правильности программы?

Если указанное изменение не вносить, то при значениях N, являющихся членами вот этой последовательности результат получается некорректным.

Update
Если имеется в виду, что я не прав в том, что я сначала подставляю нулевой, потом - первый, и так далее члены MW Sequence, а надо сначала сгенерировать i-тый член подходящей длины, и только в нем искать N-ый бит (не обращая внимание на предыдущие i-1 членов последовательности), так еще проще: экономим одно действие, bit_in_seq вычислять не надо, можно просто брать N и работать с ним... Результат еще быстрее вычислится.