Пропоную проаналізувати і розв’язати задачу «Садівник-художник»
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
Формулою - швидко і гарно, можна увесь розв’язок умістити в один рядок.
Виведіть формулу, здайте задачу, ну і вже потім, з задоволенням від себе, перегляньте цю саму формулу на екциклопедії цілочислових послідовностей, ось тут:
https://oeis.org/A007283
Успіхів!
Програмісту Петрику напередодні 8 березня наснився Григорій Сковорода і сказав: «Петре, все до копійки – на троянди для дівчат!». Хлопець дуже здивувався, хоч і не зрозумів філософа. А ще більше він здивувався, коли зранку на вулиці знайшов 500 гривен. Розгорнувши знахідку, він побачив портрет того самого Сковороди і зрозумів, що треба вже купити ті троянди і роздати дівчатам, бо тут якась містика.
Петрик почав гуглити, по скільки троянд треба оптимально дарувати дівчатам. Він швидко дізнався, що за парну кількість троянд в букеті прекрасне створіння може кинути каменюкою. Бувалі програмісти радили дарувати дівчатам якомога меншу непарну кількість троянд згідно алгоритму «навіщо радувати одну дівчину трьома трояндами, якщо трьома трояндами можна порадувати цілих три дівчини». Петрик довіряв класичним прикладним алгоритмам, бо чим більше дівчат, тим краще. І невідомо, що, як і з ким складеться в майбутньому життя. А ще Петрик нагуглив, що цього року страшно модними серед дівчат є білі троянди. І що дівчина, яка отримає саме білу троянду, скоріше за все страшенно зрадіє і навіть поцілує хлопця. Петрик з піднесеним настроєм і знайденими гривнями підійшов до великого магазину квітів і побачив цінник:
Троянди. Ціна за 1 шт.: Червоні — 39 грн. Білі — 45 грн. Жовті — 59 грн.
Як казав Петрику Григорій Сковорода, треба купити троянди на всі 500 гривень, без решти. Шановні дорослі програмісти, допоможіть, будь-ласка, Петрику. Підкажіть, скільки йому яких троянд купити, щоб і дівчат порадувати і, головне, побільше націлуватися…
(c) Анатолій Анатолійович
Цікаві білети. Задача для програмістів, що цікавляться гарними дівчатами.
(Інструкція для дівчат: дайте цю задачу знайомим програмістам. Якщо вони її не розв'яжуть, то або вони не програмісти, або не цікавляться дівчатами. В обох випадках женіть їх геть!)
Умова:
Програміст Вася зайшов у міський автобус, заплатив за проїзд і сів на вільне сидіння.
Так як в автобусі, на жаль, не було гарних дівчат, Вася почав від нудьги роздивлятися білет, що дав йому кондуктор. Всі, мабуть, знають, якщо сума перших трьох цифр дорівнює сумі останніх трьох цифр, то білет вважається щасливим. Якщо різниця між цими сумами – одиниця, наприклад 123232, то цей білет є передвісником якоїсь класної зустрічі. А програміст Вася отримав ось такого білета:
- Цікаво! Чотири четвірки, - подумав Вася, - може цей цікавий білет є передвісником якоїсь особливої вдачі? Може це щось означає?
І замислився. А скільки таких білетів в рулоні кондуктора, з чотирма четвірками? А скільки білетів, в яких три трійки в будь-якій послідовності? А п’ять пятірок?
І придумав Вася таке правило – якщо у білеті лише одна одиниця на будь-який позиції, або лише дві двійки на будь-яких позиціях, і так далі до випадку коли у білеті шість шісток, то цей білет можна вважати цікавим. І подумав Вася – а скільки таких цікавих білетів у рулоні кондуктора?
На зупинці в автобус зайшла настільки гарна дівчина, що Вася забув і про білет і про задачу. Але тепер йому стала абсолютно зрозуміла всесвітня автобусна логіка: після видачі кондуктором цікавого білету в автобус заходить гарна дівчина.
Отже, якщо Вася купить у кондуктора один рулон білетів з номерами від 000000 до 999999 і буде безкоштовно видавати білети всім пасажирам, то таким чином він видасть мільйон білетів. Порахуйте, скільки в цей чудовий автобус зайде гарних дівчат?
Ви можете дуже просто перевірити свій розв’язок. Ваше число гарних дівчат додайте до посилання на адресу сайту «Плетиво» і перевірте. Наприклад, ви вважаєте, що правильна відповідь – 1572. Тоді перейдіть на сторінку
http://pletyvo.in.ua/1572/
Якщо ви розв’язали задачу вірно, ви отримаєте відповідну оцінку і побачите одну з таких дівчат.
Успіхів!
p.s. Підказка для дівчат. Якщо ваш знайомий програміст ніяк не може впоратися з задачею, то можете дати йому підказку для розв’язку: https://oeis.org/A038291
Єдина проблема в тому, що якщо він ту підказку зрозуміє, то він, скоріше за все, взагалі не людина.
Автор задачі: Анатолій Анатолійович. Дата публікації: 13.09.2018, день програміста.
--------------------------------------------------------------------------------------------------------------------
Интересные билеты. Задача для программистов, которые интересуется красивыми девушками.
(Инструкция для девушек: дайте эту задачу знакомым программистам. Если они ее не решат, то либо они не программисты, либо не интересуются девушками. В обоих случаях гоните их прочь!)
Условие:
Программист Вася зашел в городской автобус, заплатил за проезд и сел на свободное сиденье.
Так как в автобусе, к сожалению, не было красивых девушек, Вася начал от скуки рассматривать билет, который дал ему кондуктор. Все, наверное, знают, если сумма первых трех цифр равна сумме последних трех цифр, то билет считается счастливым. Если разница между этими суммами - единица, например 123232, то этот билет является предвестником какой-то классной встречи. А программист Вася получил вот такой билет:
- Интересно! Четыре четверки, - подумал Вася, - может этот интересный билет является предвестником какой-то особенной удачи? Может это что-то значит?
И задумался. А сколько таких билетов в рулоне кондуктора, с четырьмя четверками? А сколько билетов, в которых три тройки в любой последовательности? А пять пятерок?
И придумал Вася такое правило — если в билете всего одна единица на любой позиции, или всего две двойки на любых позициях, и так далее до случая когда в билете шесть шестерок, то этот билет можно считать интересным. И подумал Вася - а сколько таких интересных билетов в рулоне кондуктора?
На остановке в автобус зашла настолько красивая девушка, что Вася забыл и о билете и о задаче. Но теперь ему стала совершенно ясна вселенская автобусная логика: после выдачи кондуктором интересного билета в автобус заходит красивая девушка.
Итак, если Вася купит у кондуктора один рулон билетов с номерами от 000000 до 999999 и будет бесплатно выдавать билеты всем пассажирам, то таким образом он выдаст миллион билетов. Посчитайте, сколько тогда в этот замечательный автобус зайдет красивых девушек?
Вы можете очень просто проверить свое решение. Ваше число красивых девушек добавьте к ссылке на адрес сайта «Плетиво» и проверьте. Например, вы считаете, что правильный ответ - 1572. Тогда перейдите на страницу
http://pletyvo.in.ua/1572/
Если вы решили задачу верно, вы получите соответствующую оценку и увидите одну из таких девушек.
Успехов!
p.s. Подсказка для девушек. Если ваш знакомый программист никак не может справиться с задачей, то можете дать ему подсказку для решения: https://oeis.org/A038291
Единственная проблема в том, что если он эту подсказку поймет, то он, скорее всего, вообще не человек.
Автор задачи: Анатолий Анатольевич. Дата публикации: 13.09.2018, день программиста.
