Начало
Соревнования
Разбор задачи 4. Двоичные числа (9-11 класс)
Тема: слияние возрастающих последовательностейСложность: выше среднего
Последовательность чисел можно задать рекуррентно через слияние последовательностей, получаемых при умножении этой же последовательности на двоичные числа 2, 22, 222, …, 222222222222222222.
Первый элемент последовательности равен 1. Каждая вспомогательная сливаемая последовательность определяется номером элемента основной последовательности, использованным для получения очередного элемента вспомогательной последовательности (первоначально все индексы установлены на 1) и значением текущего элемента. При слиянии последовательностей нужно найти минимальное значение из текущих элементов вспомогательных последовательностей — это и станет очередным элементом основной последовательности. Затем нужно сместить индексы и пересчитать текущие элементы в тех вспомогательных последовательностях, текущие элементы которых совпадают с использованным минимальным значением (таких последовательностей может быть несколько).
Для умножения нужно определить функцию, которая будет возвращать очень большое число (например, 222222222222222222) в случае переполнения. Также для вычислений нужно использовать тип int64. Пример реализации:
var x,y:int64;
d:array[1..18]of int64; { двоичные числа }
e:array[1..18]of int64; { текущие элементы }
si:array[1..18]of int64; { индексы }
s:array[1..10000]of int64; { результирующая последовательность }
i,k,m:integer;
function mul(a,b:int64):int64; { умножение с проверкой на переполнение }
var r:int64;
begin
r:=a*b;
if r div b<>a then r:=d[18];
mul:=r;
end;
begin
read(x);
{ инициализация }
d[1]:=2;
for i:=2 to 18 do
d[i]:=d[i-1]*10+2;
s[1]:=1;
for i:=1 to 18 do
begin
si[i]:=1;
e[i]:=d[i];
end;
k:=1;
{ слияние }
while s[k]<x do
begin
m:=1;
for i:=2 to 18 do { поиск минимума }
if e[m]>e[i] then
m:=i;
y:=e[m];
inc(k);
s[k]:=y;
for i:=1 to 18 do
if e[i]=y then { смещение индексов и пересчет текущих элементов }
begin
inc(si[i]);
e[i]:=mul(s[si[i]],d[i]);
end;
end;
writeln(s[k]);
end.
