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

[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

[Cheburashka]

Генерация может быть и правильная, но проблема не в этом!
ты берешь тип инт64, который сам по себе не может включать 10^200, у него всего 10^18 (может больше, может меньше. Не помню я ).
Вот и реализовывай длинную арифметику для числа N.
Думаю, что с тем, чтобы считать длинное число с файла, проблем не возникнет. Но надо подумать как найти элемент строки с этим номером!

Сообщение отредактировано: Сергей Меркурьев - 5.06.2010 17:54

[volvo]

Unconnected, вот смотри, какой путь я бы избрал (показываю с применением обычной арифметики, с небольшими значениями). Идея - такая.

1. определяем, в каком члене последовательности находится искомый бит. То есть, допустим, надо найти значение бита под номером 20. Вот так выглядит последовательность, сформированная по приведенному тобой правилу:
   0_001_001001110_001001110001001110110110001 (40 бит). Она состоит, как видим, из 4-х членов (я разделил их символами подчеркивания). Нужный нам бит находится в третьем члене, начиная с 0-го;
2. находим номер нужного бита, начиная с начала того члена, в котором он находится;
3. последовательно делим текущий член на 3 части, и определяем, в какой части находится нужный бит (в зависимости от этого принимаем решение о необходимости инвертирования);
4. продолжаем эти действия до тех пор, пока не дойдем до 3-х битных кусочков. Тут уже можно с легкостью определить, какой бит чему равен.

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

const
  inverted: array['0' .. '1'] of char = ('1', '0');

function log3(n: integer): real;
begin
  result := ln(n) / ln(3);
end;
function power(n: integer): longint;
var
  i: integer;
begin
  result := 1;
  for i := 1 to n do result := result * 3;
end;

function generate(len: longint): string;

  function invert(s: string): string;
  var i: integer;
  begin
    result := '';
    for i := 1 to length(s) do result := result + inverted[s[i]];
  end;

  var s: string;

begin
  s := '0';
  result := '';
  repeat
    result := result + s;
    s := s + s + invert(s);
    writeln(s);
  until length(result) > len;
end;

var
  s: string;
  n: integer;

  k, bit_in_seq: longint;
  power_3: longint;
  negate: boolean;

  res: char;

begin
  n := 22;
  s := generate(n);

  writeln(length(s), ' -> ', s);
  writeln('from string: ', s[n]);

  k := trunc(log3(2 * n + 1));
  bit_in_seq := pred(n - ((power(k) - 1) div 2));
  negate := false;
  power_3 := power(k);

  if power_3 > 3 then
    repeat
      power_3 := power_3 div 3;
      if (bit_in_seq div power_3) = 2 then negate := not negate;
      bit_in_seq := bit_in_seq mod power_3;
    until power_3 = 3;

  case bit_in_seq of
    0, 1: res := '0';
       2: res := '1';
  end;
  if negate then res := inverted[res];

  writeln('calculated: ', res);
  readln;
end.

Что меня мучает - это уж очень маленькое время задано для таких огромных чисел, времени может не хватить, тем более в случае использования длинной арифметики. Но это пока то, что мне придумалось, может потом наступит прозрение, как решать эту задачу...

P.S. И все-таки, по поводу

кто этот Кеане, я не знаю, и Вики с гуглом тоже

- это Mephisto Waltz Sequence

[Lapp]

[indent]

Вот так выглядит последовательность, сформированная по приведенному тобой правилу:
0_001_001001110_001001110001001110110110001 (40 бит). Она состоит, как видим, из 4-х членов (я разделил их символами подчеркивания). Нужный нам бит находится в третьем члене, начиная с 0-го;

volvo, мне думается, что все не совсем так, и заодно немного проще..

Последовательность, как я ее понял, представляет собой не совокупность членов, а просто один такой член, растущий по приведенному правилу.

0
001
001001110
001001110001001110110110001

Мне кажется, что красмвее и понятнее формулировать так: последовательность получается посредством приписывания САМОЙ СЕБЯ к себе слева и своего отрицания - справа.

Легко видеть, что отсюда сразу следуют два положения:

1. значение n-нного бита сохраняется;
2. длина последовательности на каждом шагу выражается степенью тройки.

Первый пункт делает вопрос задачи осмысленным. Второй, как мне кажется, дает ключ к решению. Но самого решения у меня пока нет. Сегодня пока занят другими делами, освобожусь - порешаю.

[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 и работать с ним... Результат еще быстрее вычислится.

[Unconnected]

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

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

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

[TarasBer]

> n=10^200 - то я, например, даже не представляю, как находить для него логарифм

ln(10)*200

[Lapp]

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

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