Пропоную проаналізувати і розв’язати задачу «Садівник-художник»
https://www.eolymp.com/uk/problems/17
Умова:
Після посадки дерев садівнику потрібно їх пофарбувати. У його розпорядженні є фарба трьох кольорів: біла, синя і помаранчева. Скількома способами він може пофарбувати N дерев, якщо ніякі два однакові кольори не можуть бути поруч?
Вхідні дані:
Кількість дерев N (1 ≤ N ≤ 50).
Вихідні дані:
Кількість способів фарбування.
Приклад:
Вхідні дані:
3
Вихідні дані:
12
Пропоную не звертати увагу на сам факт необхідності фарбування щойно посаджених дерев, тим більше фарбами. Давайте спробуємо розглянути не біологічну дикість, а математичну суть задачі.
У людей, що вивчають комбінаторику є відповідні формули, використання яких робить розв’язок такого роду задач ефективним і елегантним. Але можна спробувати знайти рішення «хлопським розумом», або якщо сучасною мовою, «з використанням логіки і критичного мислення».
Припустим, що у нас одне дерево. Скількома способами його можна пофарбувати? Трьома. Тобто це одне дерево можна пофарбувати білою (Б) фарбою – це один варіант. Або синьою (С) – це другий варіант. Або помаранчевою (П) – третій варіант. Отже, при N = 1 відповідь на нашу задачу – три.
Далі припустим, що у нас два дерева. Скількома способами їх можна пофарбувати так, щоб два кольори не були поряд?
Розпишемо всі варіанти для двох дерев:
БС – це дерева пофарбовані білою і сильною фарбою.
Розписуємо:
1) БС
2) БП
3) CБ
4) СП
5) ПБ
6) ПС
Звернемо увагу, що варіанти БС і СБ ми зараховуємо як різні способи. І у нас виходить шість способів.
Для трьох дерев відповідь є в тестовому прикладі задачі.
Можна спробувати спіймати формулу залежності результату від початкового N:
1 >> 3
2 >> 6
3 >> 12
Бачимо очевидне подвоєння попереднього значення результату. Для олімпіадного програмування, коли на вивід формул часу небагато, багато хто просто скористається циклом, що певну кількість разів подвоїть попереднє значення змінною, наприклад, так:
n = int(input())
s = 3
for _ in range(1, n):
s *= 2
print(s)
До речі, цей код здає задачу на 100%, але для допитливого «хлопського розуму», незважаючи на стать його носія, було б класно вивести формулу, яка б розв'язала дану задачу не циклом, що довго і негарно, а за один раз – елегантно і «вау!». Ну, повинен же бути такий спосіб? Повинен і є.
Ще раз відношення вхідних і вихідних даних:
1 >> 3
2 >> 6
3 >> 12
Спробуйте зловити формулу. Вивести, написати, підібрати. Як вийде. Нехай на це піде година. Або день чи тиждень. Але спробуйте. Покрутіть. І не читайте обговорення цієї задачі на сайті eolymp.com – там один учасник цю формулу відкрито написав. Не підглядайте туди.
Для перевірки вашої формули можна просто здати задачу на сайті eolymp.com
Формулою - швидко і гарно, можна увесь розв’язок умістити в один рядок.
Виведіть формулу, здайте задачу, ну і вже потім, з задоволенням від себе, перегляньте цю саму формулу на екциклопедії цілочислових послідовностей, ось тут:
Успіхів!
