Олимпиадная информатика - 2010

Задача «Ладьи»

INPUT.TXT

3 3

OUTPUT.TXT

2

program aa;
 var z,d,k,b,i,j,n,m,c,x,y:longint;
begin
 assign(input,'input.txt');reset(input);
 assign(output,'output.txt');rewrite(output);
  read(m,n); 					{ВВод размеров доски}
  if m>n then begin b:=m;m:=n;n:=b;end;{Обмен значений размеров доски, 
  так чтобы меньшим было число М}
  b:=m*n;{Первоначвльное значение наибольшего количества вариантов}
  c:=1;	{Значение К, при котром достигнуто набольшее значение числа вариантов,
   первоначально это 1}
  for i:=2 to m do	{Перебор возможных значений К}
  begin
   k:=1;{Т.к. идёт накопление произведения, первоначальное значение количества вариантов берем 1}
   x:=m;{х - число способов поставить ладью в текущей строке}
   for j:=1 to i do
   begin
    k:=k*x;	{Новое значение числа вариантов}
    dec(x);	{Новое число способов поставить ладью в текущей строке на 1 меньше предыдущего}
   end;
   y:=1;{у - число 2 в степени N, сначала это 1 - 2 в нулевой}
   for j:=1 to n do y:=y*2;			{вычисление N-ой степени двоки}
   d:=0;					{количество способо распожить пустые строки}
   x:=1;					{х - ПРОВЕРЯЕМОе ЧИСЛО ОТ 1 ДО у}
   while y>x do
   begin
    j:=x;
    z:=0;
    while j>0 do				{подсчёт числа единиц вочередном числе}
     begin
      z:=z+j mod 2;
      j:=j div 2;
     end;
   if z=i then inc(d);	{число единиц совпало с текущим значением К - количество авриантов 
   увеличиваем на 1}
   inc(x);					{переход к ледующему значению х}
   end;
   k:=k*d;					{текущее значение количества вариантов}
   if k>b then begin b:=k;c:=i;end;{новые значения количества вариантов и соответствующего 
   значения К}
  end;


   write(c) 					{ВЫВОД РЕЗУЛЬТАТА};
 close(input);close(output);
 end.


close
 

Разбор задачи №4 "Ладьи"

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

Ясно, что одну ладью можно поставить на любую клетку, при этом она никакой фигуре не угрожает, т.е. количество способов в этом случае совпадает с числом клеток и равно Nх М. Если количество фигур К более одной, то рассмотрим сначала доску размером NхК. Подобные задачи по комбинаторике встречаются в современных учебниках математики, начиная с 5 класса. Ясно, что в каждом из К строк должна стоять единственная ладья.

В первую строку ладью можно поставить N способами. Для каждого варианта один столбец под боем, и поставить ладью во вторую строку можно поставить только N-1 способом. Всего вариантов для расстановки 2 ладей в 2 рядах будет N(N-1). Для третьей строки остается N-2 вариантов, число способов N(N-1)(N-2) и т.д. Всего вариантов будет N(N-1)…(N-К+1). Найдём это число в цикле для от 1 до К.

В этом случае какие-то строки останутся пустыми. Для каждого варианта нужно будет учесть все возможные сочетания занятых и свободных строк, т.е. найденное нами число способов расстановки на доске NхК надо умножить на количество вариантов расположения на доске из M строк К занятых и M – К незанятых строк. Оно равно количеству чисел из отрезка [0; 2M -1] в двоичной записи которых содержится ровно К единиц. (Это К-значные двоичные числа с учётом лидирующих нулей, единица соответствует занятой строке, 0 –пустой).

Какие же значения может принимать К? Ясно, что оно не может быть больше меньшего из размеров доски. В противном случае по принципу Дирихле найдётся ряд, в котором расположены не менее 2 ладей, и они бьют друг друга.

Теперь ясно, каков будет алгоритм для решения всей задачи. Запросив размеры доски выберем из них меньший. За первоначальное значение способов расстановки возьмём число MxN – случай для одной ладьи. Затем в цикле для каждого значения от 2 до меньшего из размеров доски найдём число вариантов расстановки и сравним с хранимым эталоном. Если найденное значение больше – запоминаем новые значения числа способов и значение К.