Версия для печати темы

Автор: Степан 18.11.2007 19:20

Помогите решить задачу. Думал думал и так не додумался.... Заранее благодарен

Компания BrokenTiles планирует заняться выкладыванием во дворах у состоятельных клиентов узор из черных и белых плиток, каждая из которых имеет размер метр. Известно, что дворы всех состоятельных людей имеют наиболее модную на сегодня форму прямоугольника MxN метров.
Однако при составлении финансового плана у директора этой организации появилось целых две серьезных проблемы: во-первых, каждый новый клиент, очевидно, захочет, чтобы узор, выложенный у него во дворе, отличался от узоров всех остальных клиентов этой фирмы, а во-вторых, этот узор должен быть симпатичным.
Как показало исследование, узор является симпатичным, если в нем нигде не встречается квадрата 2x2 метра, полностью покрытого плитками одного цвета.

Для составления финансового плана директору необходимо узнать, сколько клиентов он сможет обслужить, прежде чем симпатичные узоры данного размера закончатся.
На вход программы подаются числа M и N. Программа должна выводить число равное количеству симпатичных узоров заданного размера.

Автор: Lapp 18.11.2007 19:57

В условии чего-то явно не хватает.. Уточнишь?

Автор: Степан 21.11.2007 1:23

Хм... вроде полное

Добавлено через 1 мин.
acm.dvpion.ru/?main=task&id_task=83
вот полное

Автор: -maksay- 21.11.2007 1:39

Эта задача предлагалась на украинских отборочно-тренировочных сборах на международную олимпиаду с немного другими ограничениями...M<=5, N<=10^100; Насколько я слышал, задача решается так...Для куска длины х, который начинается на полоску (длины 1-5), раскрашенную таким образом и заканчивается на полоску, раскрашенную какимто другим образом - узнаем количество ответов. Например ч=2, для всех вариантов 2 полосок, стоящих рядом - узнаем количество складывающихся из них симпатичных узоров....А дальше делим наш длинный N пополам, опять и.т.д в рекурсии - пока не достигнем отрезков длины х. Умножаем ответы для всех отрезков длины х - и получаем ответ..
ЗЫ Я рассказал немного сумбурно)), времени мало. Если надо, потом расскажу познее более полно..

Автор: Степан 21.11.2007 2:14

М

Используй теги klem4

Приведем функцию, которая проверяет, что два профиля совместимы:

function ok(y, z: byte): boolean;
var
  x: byte;
  i: integer;
begin
  x := y xor z;
  { Развернем двоичное число в массив }
  for i := 1 to m do
  begin
    b[i] := x and 1;
    x := x shr 1;
  end;

  { Проверим, что нет двух нулей подряд }
  for i := 2 to m do
    if (b[i] = 0) and (b[i-1] = 0) then
    begin
      ok := false;
      exit;
    end;
  ok := true;
end;

Теперь ядро программы – заполнение динамически массива A:

  { Находим максимальное значение профиля } 
  p := 1 shl m - 1;

  fillchar(a, sizeof(a), 0);
  { Начальные значения }
  for i := 0 to p do
    a[1][i] := 1;

  { Заполнение }
  for i := 2 to n do
  begin
    for j := 0 to p do
      for k := 0 to p do
      begin
        if ok(j, k) then
          a[i][k] := a[i-1][j] + a[i][k];
      end;
  end;

  { Подсчет и вывод ответа }
  r := 0;
  for i := 0 to p do
    r := r + a[n][i];
  writeln®;

Вот написано типа решение задачи.... Можете её доделать так чтобы просто скопировать в Pas файл и она заработала?

Автор: Lapp 21.11.2007 3:36

Я исправил за тебя, вставил, что отсутствовало (два места, выделено красным). В следующий раз будь внимательнее, не заставляй людей тратить время на гадание..

Автор: joey_ramone 24.04.2010 14:28

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

Автор: alecsandr 26.04.2010 15:45

нa этом форумe тeбe дaдут хорошую мысль которaя поможeт тeбe рeшить зaдaчу, a eсли тeбe нужeн зaчeт то рeшaй сaм!(