Укладка плитки

@motakuji2 · Регистрация: 18.10.2020

Студворк — интернет-сервис помощи студентам

На планете, где живет инопланетянин Лучик, есть всего одна дорога, которая имеет форму прямоугольника размером 2 × N. Пришло время ее ремонта, и премьер-министр планеты решил замостить ее новой плиткой. Завод, изготавливающий плитку, производит плитку только в форме тримино (это многоугольник, полученным путѐм объединения трех равных квадратов, соединѐнных сторонами). Известно, что существует всего 2 вида тримино (они приведены на рисунке). Также известно, что при укладке запрещено резать плитку.
Премьер-министру стало интересно, сколькими различными способами можно выложить плитку при ремонте дороги. Например, все варианты укладки для N=3 приведены на рисунке. Так как это непростой вопрос, он обратился с ним к Главному Вычислителю, которым по интересной случайности являлся Лучик. Помогите Лучику с решением этой задачи.

Формат ввода
В единственной строке записано число N (1 ≤ N ≤ 10¹² ) – длина дороги.

Формат вывода
Выведите одно число - количество способов, которыми можно замостить дорогу по модулю 10⁹ + 7.

Рыжий Лис · 19.11.2020, 12:05

Python
1
2
3
if n % 3 != 0:
    return 0
return 3 ** (n // 3)

Добавлено через 2 минуты
Хотя, например, при n=6 решений уже будет больше чем $https://www.cyberforum.ru/cgi-bin/latex.cgi?3^2$ . +ещё 2 варианта

Добавлено через 1 минуту

Python
1
2
3
4
5
if n % 3 != 0:
    return 0
if n == 3:
    return 3 ** (n // 3)
return 3 ** (n // 3) + 2

@u235 · 19.11.2020, 12:49

Рыжий Лис, какие еще два варианта?

Рыжий Лис · 19.11.2020, 13:45

Такой и зеркальный

Новые блоги и статьи Все статьи Все блоги /
Перемещение выделенных строк ТЧ из одного документа в другой Maks 30.03.2026 Реализация из решения ниже выполнена на примере нетипового документа "ВыдачаОборудованияНаСпецтехнику" с единственной табличной частью "ОборудованиеИКомплектующие" разработанного в конфигурации КА2. . . .	Functional First Web Framework Suave DevAlt 30.03.2026 Sauve. IO Апнулись до NET10. Из зависимостей один пакет, работает одинаково хорошо как в режиме проекта так и в интерактивном режиме. из сложностей - чисто функциональный подход. Решил. . .	Автоматическое создание документа при проведении другого документа Maks 29.03.2026 Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2. Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники". В. . .	Настройка движения справочника по регистру сведений Maks 29.03.2026 Решение ниже реализовано на примере нетипового справочника "ТарифыМобильнойСвязи" разработанного в конфигурации КА2, с целью учета корпоративной мобильной связи в коммерческом предприятии. . . .
Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .	Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .	Автозаполнение реквизитов при создании документа Maks 26.03.2026 Программный код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита,. . .	Команды формы и диалоговое окно Maks 26.03.2026 1. Команда формы "ЗаполнитьЗапчасти". Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. В качестве источника данных. . .

@motakuji2 0 / 0 / 0 Регистрация: 18.10.2020 Сообщений: 5

	Укладка плитки 19.11.2020, 11:08. Показов 4144. Ответов 3 Метки нет (Все метки) На планете, где живет инопланетянин Лучик, есть всего одна дорога, которая имеет форму прямоугольника размером 2 × N. Пришло время ее ремонта, и премьер-министр планеты решил замостить ее новой плиткой. Завод, изготавливающий плитку, производит плитку только в форме тримино (это многоугольник, полученным путѐм объединения трех равных квадратов, соединѐнных сторонами). Известно, что существует всего 2 вида тримино (они приведены на рисунке). Также известно, что при укладке запрещено резать плитку. Премьер-министру стало интересно, сколькими различными способами можно выложить плитку при ремонте дороги. Например, все варианты укладки для N=3 приведены на рисунке. Так как это непростой вопрос, он обратился с ним к Главному Вычислителю, которым по интересной случайности являлся Лучик. Помогите Лучику с решением этой задачи. Формат ввода В единственной строке записано число N (1 ≤ N ≤ 10¹² ) – длина дороги. Формат вывода Выведите одно число - количество способов, которыми можно замостить дорогу по модулю 10⁹ + 7. Миниатюры 0

@u235 5516 / 2869 / 571 Регистрация: 07.11.2019 Сообщений: 4,760
	19.11.2020, 12:49
	Рыжий Лис, какие еще два варианта? 0

Рыжий Лис Просто Лис 5973 / 3735 / 1099 Регистрация: 17.05.2012 Сообщений: 10,791 Записей в блоге: 9
	19.11.2020, 13:45
	Такой и зеркальный Изображения 1