Разбор задач контеста 16.11

Разбор задач контеста 16.11

03. Декодирование по алгоритму Хаффмана.

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

var ch:array[1..100] of char;

kod: array[1..100] of string;

s, ans:string;

i, n:Integer;

a:char;

begin

readln(n);

for i:=1 to n do begin read(ch[i]);read(a); readln(kod[i]);end;

readln(s);

ans:='';

while length(s)<>0 do

for i:=1 to n do

if pos(kod[i],s)=1 then begin

ans:=ans+ch[i];

delete(s,1,length(kod[i]));

end;

write(ans);

end.

04. Железная дорога.

Для начала заметим, что мы всегда можем считать, что Андрей находится на станции ровно M минут. Тогда задачу можно сформулировать так: каждый поезд представляет из себя отрезок (по времени) своего пребывания на станции. Нам надо разместить отрезок длины M (отрезок времени, в который он будет на станции) так, чтобы он пересекался (имел общие точки) с максимальным количеством отрезков.

Решение за N*100000: переберем все возможные t - моменты прихода Андрея на станцию. Найдем количество пересечений отрезка [t,t+M] с отрезками пребывания поездов. Выберем максимум.

maxCnt := 0; best := 0;

for t := 0 to 100000 do begin

cnt := 0;

for i := 1 to n do

if (l[i] <= t + M) and (t <= r[i]) then inc(cnt);

if cnt > maxCnt then begin

maxCnt := cnt;

best := t;

end;

end;

writeln(best);

Ускорение решения: достаточно рассматривать не все возможные времена прихода Андрея, а только те, при которых либо время прихода Андрея, либо время его ухода совпадает со временем прибытия/отбытия какого-либо поезда. А таких моментов не более 4N. Получаем решение за O(N^2).

05. Печатный пиар.

Интуитивно достаточно понятно, что листовки с бОльшим L[i] нужно печатать пораньше. Оказывается, это и есть решение. Более строгие рассуждения: рассмотрим ту листовку, которую мы распечатаем последней. Время, в которое она будет напечатана, это константа, равна сумме T[i] по всем листовкам. Тогда очевидно, что время, когда эта листовка будет доставлена, будет минимально тогда, когда в последнюю очередь мы напечатаем листовку с наименьшим временем доставки.

Решение: сортируем по убыванию L[i], вычисляем ответ.

06. Идентификация символов.

Пусть мы выбрали какое-то множество пикселей P. Тогда назовем два рисунка неотличимыми (или эквивалентными) относительно P, если пиксели из P в обоих рисунках совпадают. Группы неотличимых рисунков называются классами эквивалентности. Нам надо найти наименьшее по размеру множество пикселей, чтобы все рисунки стали попарно отличимыми, т. е. размер каждого класса эквивалентности был равным 1.

Пусть мы добавляем пиксели в P по одному. Изначально имеется один класс эквивалентности, в который попадают все рисунки. При добавлении пикселя класс может либо сохраниться (все рисунки имеют одинаковые значения в этих пикселях), либо распасться на два (с 0 и 1). При добавлении следующего пикселя с каждым из имеющихся классов опять произойдет то же самое: либо сохранится, либо распадется на два. Мы должны прийти к ситуации, когда все классы размера 1. Очевидно, что не имеет смысла добавлять пиксели, от добавления которых ни один класс не распадается. Поэтому минимальное количество добавляемых пикселей не больше 5.

Неполное решение: перебор. Количество способов выбрать не более 5-ти пикселей из 100 – около 10^8. Можно пытаться брать сначала по 1, затем по 2 пикселя, по 3, 4, и только затем – по 5. Как проверять, подходит ли набор пикселей, понятно: надо понять, что нету пары рисунков, полностью совпадающих в этих пикселях.

Переход к полному решению. Заметим, что количество разбиений множества из 6 элементов (рисунков) на группы невелико (несколько сотен). Поэтому можно делать динамическое программирование, в котором состоянием является следующий набор параметров – (i, j, S), где i – это сколько первых пикселей рассмотрели, j – сколько из них взяли в набор, S – это разбиение множества рисунков на классы эквивалентности в соответствии с выбранным набором пикселей.

Разбор задач контеста 23.11

03. Конфеты.

Будем перебирать все пары людей (i, j), и для каждой пары понимать, сколько человек с номером i должен отдать человеку j.

readln(n, k);

s:=0;

for i:=1 to n do

begin

read(A[i]);

if A[i]>k then inc(s, A[i]-k);

end;

writeln(s);

for i:=1 to n do

for j:=1 to n do

if i<>j then

begin

if (A[i]<k) and (A[j]>k) then

begin

c:=Min(A[j]-k, k-A[i]);

for t:=1 to c do writeln(j,' ',i);

inc(A[i],c); dec(A[j],c);

end

end;

04. Расшифровка.

Пусть есть m простых чисел, не превосходящих длины строки. Тогда, чтобы откатить назад одну фазу шифрования, нужно взять первые m символов строки S и поставить их на позиции с простыми номерами (в новой строке). Затем поставить все остальные символы строки S на оставшиеся места. Откат фазы повторить K раз.

var s : string;

q : array[1..300] of char;

k, i, m, len, t : integer;

a : array[1..300] of integer;

function prime(n : integer) : boolean;

var u: integer;

begin

u := 2;

while u * u <= n do

begin

if n mod u = 0 then begin prime := false; exit; end;

inc(u);

end;

prime := true;

end;

procedure encrypt;

var i : integer;

begin

fillchar(q, sizeof(q), '?');

for i := 1 to m do q[a[i]] := s[i];

i := m + 1;

while i <= len do

begin

for t := 1 to len do

if q[t] = '?' then begin q[t]:=s[i]; inc(i); end;

end;

for i := 1 to len do s[i]:=q[i];

end;

Begin

m := 0;

for i := 2 to 300 do if prime(i) then begin

inc(m);

a[m] := i;

end;

readln(k);

readln(s);

m := 1;

len := length(s);

while a[m] <= len do inc(m);

dec(m);

for i := 1 to k do encrypt;

writeln(s);

End.

05. Функция.

Найдем функцию, которая не вызывает других функций, опишем ее выше всех. Если такой нет, то ответа не существует. Далее каждый раз будем выбирать такую функцию, что все функции, которые она вызывает, уже описаны. Легко показать, что, если такой функции не нашлось, то имеется циклическая последовательность вызовов функций, поэтому ответа не существует. См. алгоритм топологической сортировки ориентированного графа.

06. Зигзаги

Одно из возможных решений – динамическое программирование. Пусть D1[i] – наименьшее количество чисел, которые нужно удалить слева от A[i] так, что A[i] оказалось последним элементом в зигзаге, причем знак в зигзаге перед A[i] – это знак “<” (т. е. A[i] больше предпоследнего элемента в этом зигзаге). D2[i] – то же самое, только знак должен быть “>”. Тогда примерные формулы для переходов: D1[i] = min (по j < i, a[j] < a[i]) D2[j] + i – j – 1 (удаляем все между A[j] и A[i]). Для D2 все симметрично.