Форум программистов, компьютерный форум, киберфорум
Наши страницы
Pascal (Паскаль)
Войти
Регистрация
Восстановить пароль
 
Новичок
Модератор
1490 / 964 / 459
Регистрация: 17.07.2012
Сообщений: 4,918
Завершенные тесты: 3
#1

Рекурсия или ДП?

17.12.2015, 18:01. Просмотров 203. Ответов 0
Метки нет (Все метки)

Всем привет. Есть одна задача, наверно классическая , но я не знаю как ее решать.
Задача 7. Укладка плитки
Имя входного файла:
tiling.in
Имя выходного файла:
tiling.out
Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт
В процессе ремонта в Лаборатории Информационных Технологий строителям необходимо заменить поврежденные напольные плитки в коридоре лаборатории, который имеет размер 2×n метров. В распоряжении строителей есть неограниченный запас плиток двух размеров: 1×2 метра и 1×1 метр. При этом плитки размером 1×2 метра перед укладкой разрешается поворачивать на 90 градусов и размещать как вдоль, так и поперек коридора.
Строители уже начали ремонт и уложили в некоторых местах пола коридора k плиток размером 1×1. Для завершения ремонта прорабу необходимо подготовить план дальнейших работ. Для этого ему надо решить, каким образом уложить плитки на места, где они еще не уложены. Это можно сделать различными способами и прораб хочет перебрать все варианты и выбрать самый удачный. Перед тем как это сделать, прораб хочет знать, какое количество вариантов ему придется рассмотреть. Это число требуется найти по модулю 109+7.
Требуется написать программу, которая по заданной длине коридора n и расположению плиток, которые уже уложены, определяет количество способов укладки плиток на оставшиеся места. Ответ необходимо вывести по модулю 109+7.
Формат входного файла
Первая строка входного файла содержит два целых числа: n—длину коридора и
k—количество уже уложенных единичных плиток (1≤n≤100000, 0≤k<2n).
Последующие k строк содержат по два целых числа xi и yi, которые задают позиции уже уложенных единичных плиток, i-я плитка уложена на xi-м метре коридора в yi-м ряду (1≤xi≤n, 1≤yi≤2).
Формат выходного файла
Выходной файл должен содержать одно целое число — количество способов укладки плиток в коридоре, взятое по модулю 109+7.
римеры входных и выходных файлов
tiling.intiling.out
2 0 7
3 0 22
3 1 8
Мне приходит в голову только один путь решения - рекурсией как-то перебирать все варианты. Но мне кажется, что слишком это долго будет работать и не пройдет ограничения по времени. Может тут ДП какое-то? Подскажите алгоритм, код я не прошу, только алгоритм, а точнее идею решения задачи. Спасибо.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.12.2015, 18:01
Ответы с готовыми решениями:

Перевод кода с Pascal на С++ или Си (рекурсия)
Здравствуйте, помогите, пожалуйста, перевести код с Pascal на С++, либо на Си....

Огонь на Pascale (или ABC, или Free, или Turbo)
Пожалуйста, обрадуйте кто нибудь, кодом Движения Огня на Pascale.

Рекурсия: найти сумму тех членов ряда, модуль которых больше или равен заданному эпсилон
2. Решить задачу с помощью рекурсивной функции или процедуры. Дан числовой ряд...

Перебор или рекурсия...
Есть некий массив. Нужно по первому столбику узнать сколько минимально строк...

Свёртка или рекурсия
М. Липовача в своей книге рекомендует использовать свёртки, вместо комбинации...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.12.2015, 18:01

Рекурсия на базе for или while
Нужно реализовать бесконечную рекурсию с помощь цикла for или while:...

Рекурсия-Советы или Трюки
привет у меня скоро экзамен я хотел спросить как лучше всего отслеживать...

Восходящая или нисходящая рекурсия?
Здравствуйте, подскажите пожалуйста это восходящая или нисходящая рекурсия и...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru