IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Симпатичные узоры
сообщение
Сообщение #1


Гость






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

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

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

Сообщение отредактировано: Lapp -
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3





Группа: Пользователи
Сообщений: 2
Пол: Мужской

Репутация: -  0  +


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

Добавлено через 1 мин.
acm.dvpion.ru/?main=task&id_task=83
вот полное
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Гость






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





Группа: Пользователи
Сообщений: 2
Пол: Мужской

Репутация: -  0  +


М
Используй теги
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 файл и она заработала?

Сообщение отредактировано: klem4 -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(Степан @ 20.11.2007 21:23) *

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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7





Группа: Пользователи
Сообщений: 3
Пол: Мужской
Реальное имя: Дмитрий

Репутация: -  0  +


всем здравствуйте, вот и мне понадобилась эта задача, тот код что тут представлен, к сожалению дает другой ответ(( помогите довести задачу до ума, очень нужно получить зачет((
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Пионер
**

Группа: Пользователи
Сообщений: 61
Пол: Мужской
Реальное имя: Alexander

Репутация: -  0  +


Цитата(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м!(
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 17:07
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name