Помогите решить задачу. Думал думал и так не додумался.... Заранее благодарен
Компания 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
Цитата(Степан @ 20.11.2007 21:23)
Хм... вроде полное .. вот полное
Я исправил за тебя, вставил, что отсутствовало (два места, выделено красным). В следующий раз будь внимательнее, не заставляй людей тратить время на гадание..
joey_ramone
24.04.2010 14:28
всем здравствуйте, вот и мне понадобилась эта задача, тот код что тут представлен, к сожалению дает другой ответ(( помогите довести задачу до ума, очень нужно получить зачет((
alecsandr
26.04.2010 15:45
Цитата(joey_ramone @ 24.04.2010 11:28)
всем здравствуйте, вот и мне понадобилась эта задача, тот код что тут представлен, к сожалению дает другой ответ(( помогите довести задачу до ума, очень нужно получить зачет((
нa этом форумe тeбe дaдут хорошую мысль которaя поможeт тeбe рeшить зaдaчу, a eсли тeбe нужeн зaчeт то рeшaй сaм!(
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.