Упакованная запись числа

24 Август 2016

admin

Задача из олимпиады «Ломоносов-2105» по информатике. Рассмотрим способ упакованной записи чисел в p-ичной системе. Идея способа состоит в том, чтобы одинаковые подряд идущие цифры, например 111111111, заменять на следующую конструкцию.
Сначала идет повторяемая цифра (в примере – 1), затем открывающаяся скобка перед числом повторений [, затем упакованная записи числа повторений в p-ичной системе и, наконец, закрывающаяся скобка ]. Так число 111111111000 в упакованной записи в двоичной системе может быть записано следующим образом: 1[10[10]1]0[11].

Ниже приведена программа на языке Pascal, которая реализует упаковку строки в двоичной системе.

Обратите внимание на то, что если 1 или 0 повторяются 5 и менее раз подряд, то смысла выполнять упаковку нет. Так как получится также 5 символов, с учетом скобок. Поэтому RepeatCol = 6;

const
RepeatCol = 6;

function NtoBIN(n:integer):string;
var i,c,nt:integer;
s:string;
a: array[1..100] of byte;
begin
nt:=n;
c:= 0;
repeat
c:= c + 1;
a[c]:= nt mod 2;
nt:= nt div 2;
until nt = 0;

s:=»;
for i:= c downto 1 do
s:=s+a[i];

NtoBIN:=s;
end;

function PackBIN(s:string):string;
var
st,ResultS:string;
c:char;
n,i:integer;
begin
writeln(‘Пакуем строку: ‘+s);

//c:=’-'; // любой символ, отличный от 0 и 1
st:=»; // кусок строки с цифропеременным составом (где повторение цифры < RepeatCol)
ResultS:=''; // Упакованная строка
n:=1; // Счётчик повторений одной цифры подряд

for i:=1 to length(s) do
begin
//writeln('i='+i);

//writeln('st='+st);

if (c=s[i])
then
begin
n:=n+1;
st:=st+s[i];
end;
if (c<>s[i]) or (i=length(s)) then
begin
if n>=RepeatCol then
begin
writeln(‘Можно запаковать строку: ‘+st);
ResultS:=ResultS + c + ‘[' + PackBIN(NtoBIN(n)) + ']‘;
end
else
begin
ResultS:=ResultS+st;
end;

n:=1;
st:=s[i];
end;

c:=s[i];
end;

//ResultS:=ResultS+st;

writeln(‘Результат упаковки: ‘+ResultS);

PackBIN:=ResultS;
end;

var
s:string;
begin
readln(s);

write(PackBIN(s));

writeln();
end.