Задача

Отравленный пирог
PIE

Условие Комментарии Решение Тестовые файлы Оглавление

Описание
Для игры "Отравленный пирог" используется прямоугольный пирог, разделенный на M "строк" горизонтальными разрезами и на N "столбцов" - вертикальными. Таким образом, пирог должен быть разбит на M×N клеток, правая нижняя из которых "отравлена". Играют двое игроков, ходы делаются по очереди. Каждый ход заключается в том, что игрок выбирает одну из еще не съеденных клеток пирога и съедает все клетки, расположенные левее и выше выбранной (в том числе и выбранную). Проигрывает тот, кто съедает отравленную клетку

Задание
Требуется написать программу, которая по заданной игровой позиции определяет все возможные выигрышные ходы для начинающего в этой позиции

Входные данные
Данные во входном файле расположены в следующем порядке: M,N (1≤M,N≤9), x₁,...,x_M. Здесь x_i - число оставшихся клеток в i-м снизу горизонтальном ряду. Все числа во входном файле разделяются пробелами и/или символами перевода строки

Выходные данные
В первую строку выходного файла необходимо вывести количество различных выигрышных ходов К, а в последующие K строк - сами выигрышные ходы. Каждый ход задается парой чисел (i,j), где i – номер (снизу) горизонтального ряда, а j - номер (справа) вертикального ряда, которому принадлежит выбранная клетка (1≤i≤M, 1≤j≤N)

Например:

PIE.IN
3 5
5 4 3

PIE.OUT
1
3 1

Идеи
Нумерация позиций, построение перечислителя, динамическое программирование

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

Основная проблема в этой задаче - нужно так пронумеровать состояния игры, чтобы по состоянию можно было эффективно вычислить его номер, а по номеру - легко восстановить состояние

Решение

{$A+,B-,E-,F-,G-,N+,O-,P-,Q-,T-,V+,X+}
{$M 65520,0,655360}

program pie;
const
infile = 'pie.in';
outfile = 'pie.out';
MaxN = 9;
MaxP = 48620;
type
diagr = array [1..MaxN] of byte;
var
N, M : integer;
X : diagr;
VXD : Word;
C : array [0..MaxN, -1..MaxN] of word;
W : array [0..MaxP-1] of boolean;

procedure calcA;
var k, l, i : integer;
begin
for l:=0 to MaxN do C[0,l] := 1;
for k:=1 to MaxN do
    begin
      C[k,-1] := 0;
      C[k,0] := 1;
      for l:=0 to MaxN do C[k,l] := C[k,l-1] + C[k-1,l]
    end
end;

procedure num2pos (N : word; var P : diagr);
var i, j : integer;
begin
for i:=1 to M do
    begin
      j := 0;
      while (j<=MaxN) and (N>=C[M-i+1,j]) do inc(j);
      P[i] := j;
      N := N - C[M-i+1, j-1]
    end
end;

function pos2num (var P : diagr) : word;
var N : Word; i, j : integer;
begin
N := 0;
for i:=1 to M do
    N := N + C[M-i+1, P[i]-1];
pos2num := N;
end;

var
TP, NP : diagr;
PP : word;

function calcW (P : word) : boolean;
var
i, j, k : integer;
begin
num2pos (P, TP);
calcW := true;
for i:=1 to M do
    for j:=0 to TP[i]-1 do
      begin
        NP := TP;
        for k:=i to M do if NP[k]>j then NP[k]:=j;
        if not W[pos2num(NP)] then exit
      end;
calcW := false
end;

procedure writeanswer;
var
i, j, k, l : integer;
res : array[1..81,1..2] of byte;
begin
num2pos (VXD, TP);
l := 0;
for i:=1 to M do
    for j:=0 to TP[i]-1 do
      begin
        NP := TP;
        for k:=i to M do if NP[k]>j then NP[k]:=j;
        if not W[pos2num(NP)] then
          begin inc(l); res[l,1]:=i; res[l,2]:=j+1 end
      end;
writeln (l);
for i:=1 to l do writeln(res[i,1],' ',res[i,2])
end;

var i : word;
begin
assign (input, 'pie.in'); reset (input);
read (M, N);
for i:=1 to M do read(X[i]);
calcA;
VXD := pos2num (X);
W[0] := true;
for i:=1 to VXD do W[i] := calcW (i);
assign (output, 'pie.out'); rewrite(output);
writeanswer;
close(input); close (output)
end.