Последовательность N-битных чисел.

[VladKB1]

Всем доброго времени суток!

Решаю задачу и нет вообще никаких идей для решения, буду очень благодарен за намёки на правильную идею. Ниже сама задача:

Задана отсортированная последовательность всех N-битных чисел, в которой были удалены все числа, имеющие в своей двоичной записи более, чем L единиц. Вам необходимо найти I тый элемент этой последовательности. Нумерация элементов начинается с единицы.

Ограничения по времени 1 секунда.


Формат ввода:
N L I (1 ≤ N ≤ 31, 1 ≤ L ≤ N)

Формат вывода:
I-й элемент последовательности

Пример ввода:
3 1 3

Пример вывода:
010

Всем заранее спасибо за помощь!

[Plague]

Перебором не пробовали решить для начала?
Язык какой?

[VladKB1]

Сообщение от Plague

Перебором не пробовали решить для начала?
Язык какой?

N <= 31 . Перебор будет работать очень долго. Ограничения по времени 1 секунда. Язык pascal. Мне нужна просто идея, объяснения как решать, либо что-то частичное что наводит на правильную мысль.

[FPaul]

А почему будет долго?
Есть обзорная статья на хабре об алгоритмах подсчёта количества единиц - https://habrahabr.ru/post/276957/
Ещё описания http://myworkonly.blogspot.ru/2012/01/blog-post_05.html
Т.е. в цикле от 0 до ((2^N)-1) перебираете числа и находите I.
Причём, можно ускорить поиск, начиная не от 0, а от ((2^L)-1).

[ura_111]

Попробуй решить сначала последовательно:
1) По данным N=4 заполнить массив всех возможных комбинаций:

0000
0001
0010
......
......

2) В этом массиве найти все единицы длиной L=3 и их удалить. Например:

.......
0111  - удалить число (или число, или только единицы - делай число, потом уточним)
......
1110 - удалить число (или число, или только единицы - делай число, потом уточним)
......

3) В этом массиве найти десятое число I=10 (число состоит из 4-х бит). Нумерация чисел начинается с единицы... По поводу последнего предложения не совсем понимаю,... наверно надо не массив, а строку символов и в ней уже искать десятое число (каждое число имеет форму 4-х битную, а первое начинается с единицы).

0001010001000110010011100
означает 0001 0100 0100 0110 0100 111 00...

Но ты делай пока с массивами, а не строками (потом, если понадобится, перейдёшь на строку)

Ну ты понял последнюю мою мысль, да?

последовательность (в которой уже удалены тройки единиц L=3) ->   000101000100011001001100

это последовательность начинается с нулей (000....), но числа, по условию задачи, должны начинаются с 1-цы, т.е. нули надо отбросить -> 101000100011001001100 ...

и начинаем искать десятое число (I=10) ->  1010  0010  0011  0010  0110  0 ...

Но ты делай пока не со строкой, а с массивом чисел (в принципе задание в общем понятно, но некоторые моменты нет)... Не переживай, когда начнёшь решать (думать) над задачей - решение само определится со временем.

[Dekay]

Сообщение от FPaul

А почему будет долго?

2^31 эта два миллиарда


А по теме. Есть задача насчитать сколько существует N-битный чисел, в которых нет более K нулей подряд.
Заменяем 1 на 0.
А потом.. Стоит мы сейчас в i-ой позиции. Значит остается N-i (с точность до 1, не хочу думать) разрядов. Давайте поставим 0(или 1, не хочу думать) и посчитаем сколько попадает ли мы туда? В зависимости от этого ставим 1 или 0 и идем дальше.

Если что - вот пример
3 1 3
010

мы на первой позиции. Нужно понять что ставить. Если поставим 0 - останется две позиции. И варианты 00 01 10 - всего 3. 3<=3. Да. Идем. Первая цифра 0
На втором бите стоим. Есть поставить 0. Останется одна позиция 0 или 1. Давайте 0 поставим. Получится одно место. А там 0 или 1. 2 варианта. 3 <= 2? Нет. Значит ставим 1. Дальше снова пляшем.

[VladKB1]

Сообщение от Dekay

2^31 эта два миллиарда


А по теме. Есть задача насчитать сколько существует N-битный чисел, в которых нет более K нулей подряд.
Заменяем 1 на 0.
А потом.. Стоит мы сейчас в i-ой позиции. Значит остается N-i (с точность до 1, не хочу думать) разрядов. Давайте поставим 0(или 1, не хочу думать) и посчитаем сколько попадает ли мы туда? В зависимости от этого ставим 1 или 0 и идем дальше.

Если что - вот пример
3 1 3
010

мы на первой позиции. Нужно понять что ставить. Если поставим 0 - останется две позиции. И варианты 00 01 10 - всего 3. 3<=3. Да. Идем. Первая цифра 0
На втором бите стоим. Есть поставить 0. Останется одна позиция 0 или 1. Давайте 0 поставим. Получится одно место. А там 0 или 1. 2 варианта. 3 <= 2? Нет. Значит ставим 1. Дальше снова пляшем.

Типо углубляемся рекурсией и ставим либо 1, либо 0? А как это делать чтобы генерировать отсортированную. Вообщем можно поподробней?

[Plague]

Какое у вас ограничение на I ?

[VladKB1]

Сообщение от Plague

Какое у вас ограничение на I ?

Ну логичо если его не пишут в условии, то значит оно может быть последним числом в последовательности, а если n = 31, l = 31, то i <= 2^31. Это будут все числа от 0 до 2^31.

[FPaul]

Пробовал простой перебор.
Потом лёгкую оптимизацию на случай, если I меньше первого числа с L+1 единицей.
Потом сделал начало перебора не от 0, а от 1<<(L+1).
Далее сделал пропуск всех чисел, в которых старшие разряды содержат L+1 единицу - прыжок на число вида 1<<t большее, чем текущее значение.

program test;

{$R-}
{$Q-}
const
  g31 = $49249249;
  g32 = $381c0e07;

  procedure ShowBin(X, N: dword);
  var
    mask: dword;
  begin
    mask := 1 shl (N - 1);
    while mask <> 0 do
    begin
      if mask and X = 0 then
        Write('0')
      else
        Write('1');
      mask := mask shr 1;
    end;
    writeln;
  end;

var
  N, L, I: dword;
  Count: dword;
  BitCount, X, Xstart, Xfinish, Xjump: dword;
begin
  readln(N, L, I);

  Xstart  := (((1 shl L) - 1) shl 1) + 1;
  Xfinish := (1 shl N) - 1;
  if Xstart > I then
    X := I - 1
  else
  begin
    Xjump := Xstart shl 1;
    Count := Xstart;
    X := Xstart + 1;
    Xstart := Xstart + 1;
    while (X <= Xfinish) do
    begin
      if X = Xjump then
      begin
        Xjump := Xjump shl 1;
        Xstart := Xstart shl 1;
        X := Xstart;
      end;
      BitCount := X;
      BitCount := (BitCount and g31) + ((BitCount shr 1) and g31) +
        ((BitCount shr 2) and g31);
      BitCount := ((BitCount + (BitCount shr 3)) and g32) + ((BitCount shr 6) and g32);
      BitCount := (BitCount + (BitCount shr 9) + (BitCount shr 18) +
        (BitCount shr 27)) and $3F;
      if BitCount <= L then
      begin
        Inc(Count);
        if Count = I then
          break;
      end;
      Inc(X);
    end;
  end;
  ShowBin(X, N);
end.

Прихожу к выводу, что здесь перебор нужен лишь на заключительном этапе.
Т.е. в начальный момент имеется диапазон без удалённых чисел
Xstart=0 и Xfinish=(1<<(L+1))-1 - или для исключения переполнения Xfinish=(((1<<L)-1)<<1)+1
В этом диапазоне Xfinish-Xstart подходящих чисел. Их можно не перебирать, если их количество меньше I.
Далее, найдём следующий диапазон. Он будет
Xstart:=Xfinish+1 и Xfinish:=следующее сочетание из N по L
Опять, количество подходящих чисел можно вычислить Xfinish-Xstart. И теперь всего Count:=Count+(Xfinish-Xstart) подходящих чисел в диапазоне от 0 до Xfinish.

Продолжая так, в какой-то момент получим Count>=I. Тогда и завершить перебором от Xstart до Xfinish. Хотя и это не нужно - ведь этот диапазон - непрерывный.

Получение очередного Xfinish не очень сложно. Видимо понадобится массив для заполнения разрядов. Или можно воспользоваться битовыми полями прямо в Xfinish (в FreePascal - они быстро работают).