Два игрока играют в следующую игру. Перед ними лежит куча из 7 камней. Игроки берут камни по очереди. За один ход можно взять 1, 2 или 3 камня. Проигрывает тот, кто берет последний камень. Кто выиграет при безошибочной игре обоих игроков – игрок, делающий первый ход, или игрок, делающий второй ход? В ответе укажите номер игрока (1 или 2) и последовательно, количество камней (наименьшее возможное значение), которое находилось в куче после каждого хода. Например

Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова. Коды, удовлетворяющие условию Фано, допускают однозначное декодирование.

Решение.

Для нахождения кодовых слов будем использовать двоичное дерево, в котором от каждого узла отходит две ветви, соответствующие выбору следующей цифры кода. Буквы будем размещать на конечных узлах дерева — листьях. Условие Фано выполняется, поскольку при проходе от корня дерева к букве в середине пути не встречается других букв.

Пример дерева, обеспечивающего минимальную сумму длин всех шести кодов изображено на рисунке.

 

 

Суммарная длина такого кода 1 + 2 + 3 + 4 + 5 + 5 = 20.

 

ответ: 20.

Объяснение:

Procedure Four(n:integer; var a:a_type); 
{Процедура построения квадрата при n двойной четности: n=4,8,12,16...} 
PascalВыделить код1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 Var i,j,k:integer; p,l:integer; i1,j1,x,y:integer; Begin l:=1; p:=n*n; for i:=1 to n do for j:=1 to n do begin a[i,j]:=l; inc(l) {l:=l+1} end; i:=2; while i<=n-2 do begin if i mod 4=0 then j:=4 else j:=2; while j<=n-2 do begin for i1:=0 to 1 do for j1:=0 to 1 do begin y:=i+i1; x:=j+j1; a[y,x]:=p-a[y,x]+1; end; j:=j+4; end; i:=i+2 end; k:=4; while k<=n-4 do begin a[1,k]:=p-a[1,k]+1; a[1,k+1]:=p-a[1,k+1]+1; a[n,k]:=p-a[n,k]+1; a[n,k+1]:=p-a[n,k+1]+1; a[k,1]:=p-a[k,1]+1; a[k+1,1]:=p-a[k+1,1]+1; a[k,n]:=p-a[k,n]+1; a[k+1,n]:=p-a[k+1,n]+1; k:=k+4 end; a[1,1]:=p-a[1,1]+1; a[n,n]:=p-a[n,n]+1; a[1,n]:=p-a[1,n]+1; a[n,1]:=p-a[n,1]+1; end;