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

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


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

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


Например:

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.


 


© Особенности национальных задач по информатике