Сьогодні буде неолімпіадне програмування. Коли нема куди поспішати, є електрика в розетці і ароматний чай в улюбленій чашці. Сідайте поряд.  Будемо розв’язувати задачу з сайту eolymp.com з номером 1536.  Англійською ця задача зветься «Sweet Child Makes Trouble», а українською  - «Улюблена дитина заважає», зловити б того креативного перекладача.

Умова:

Діти завжди любимі, але іноді вони можуть примусити вас вести себе різко. У цій задачі ви побачите, як Тінтін, п'ятирічний хлопчик, створює проблеми для своїх батьків. Тінтін - веселий хлопчик і завжди зайнятий справами. Але не все, що він робить, приносить радість його батькам. Більше всього йому подобається гратись з домашніми речами, як наприклад годинник батька або гребінець матері. Після гри він не повертає їх на місце. Тінтін дуже розумний хлопчик з достатнь чіткою памяттю. Він засмучує своїх батьків тим, що ніколи не повертає речі, взяті для гри, на їхнє місце.

Подумати лише! Якось вранці Тінтін вдалось викрасти три предмети домашнього вжитку. Скількома способами він може повернути ці речі так, щоб жоден з предметів не попав на своє попереднє місце? Тінтін не бажає засмучувати своїх батьків і приносити їм неприємноісті. Тому він нічого не ховає у нових місцях, а просто перекладає предмети.

Вхідні дані

Вхідні дані складаються з декількох тестів. Кожний тест містить натуральне число, яке не перевищує 800 - кількість речей, які Тінтін взяв для гри. Кожне число знаходиться у окремому рядку. Останній рядок містить -1 (мінус один) і не опрацьовується.

Вихідні дані

Для кожного тесту вивести кількість способів, якими Тінтін може повернути взяті речі.

Приклад вхідних даних:

2

3

4

-1

Приклад вихідних даних:

1

2

9

Давайте розбиратися.

Розглянемо варіант, коли Тінтін взяв дві речі. Якщо одну річ позначити одиничкою, а другу - двійкою, то варіант перестановки один:

12 (стартовий)

21 (перестановка)

Розглянемо варіант, коли Тінтін взяв три речі. Одну річ позначимо одиничкою, а другу – двійкою, третю – трійкою.  Пам’ятаємо, що згідно умови Тінтін не може класти речі на ті місця, звідки брав. Тобто, якщо в стартовій позиції одиничка на першому місці, но в жодній перестановці одиничка на першому місці бути не може. Тому варіанти будуть такими:

123 (стартова)

231 (перестановка)

312 (перестановка)

Це, до речі, підтверджує тестовий приклад, при трьох речах перестановок з даними умовами існує дві.

Розглянемо варіант, коли Тінтін взяв чотири речі. Тут варіанти перестановок будуть такими:

1234 (стартова)

2143 (перестановка)

2341 (перестановка)

2413 (перестановка)

3142 (перестановка)

3412 (перестановка)

3421 (перестановка)

4123 (перестановка)

4312 (перестановка)

4321 (перестановка)

Таку кількість ще можна перебрати вручну.  А от цікаво, а для п’яти речей скільки перестановок? Очікувано буде чимало, але то скільки в цифрах? Тут можна, потайки від математиків, знайти рішення перебором:

start = '12345'

c = 0

for x1 in range(1,6):

    for x2 in range(1,6):

        for x3 in range(1,6):

            for x4 in range(1,6):

                for x5 in range(1,6):

                    if x1 != 1 and x2 != 2 and x3 != 3 and x4 != 4 and x5 != 5 and len(set([x1,x2,x3,x4,x5])) == 5:

                        c += 1

                        print(x1, x2, x3, x4, x5, sep = '')

print(c)

У нас вийшло 44 перестановки:

21453
21534
23154
23451
23514
24153
24513
24531
25134
25413
25431
31254
31452
31524
34152
34251
34512
34521
35124
35214
35412
35421
41253
41523
41532
43152
43251
43512
43521
45123
45132
45213
45231
51234
51423
51432
53124
53214
53412
53421
54123
54132
54213
54231

Особисто я десь глибоко всередині відчуваю, що десь поряд ховається розумний математичний розв’язок. Десь дуже глибоко. У нас вже ж є послідовність, залежність кількості перестановок від кількості речей. Ось:

Кількість речей – кількість перестановок:

2 – 1

3 – 2

4 – 9

5 – 44

Так як у нас не олімпіада, а посиденьки з електрикою і чаєм, то давайте, поки математики знову не бачать, заглянемо до них в енциклопедію цілочислових послідовностей, у нас вже є чотири елементи послідовності: 1, 2, 9, 44

Отримуємо щось страшне і по суті і англійською  ))

І в довгих і страшних поясненнях для розумних математиків відшукуємо нам потрібну формулу! ))

Ну а далі вже просто. Тепер можна кликати математиків і ховати перебор. І розв’язати задачу, коли наступний член послідовності визначається формулою:

a(n) = n*a(n-1) + (-1)^n

 У вигляді Пайтон-програми це може бути, наприклад, так:

while True:

    c = int(input())

    if c == -1:

        break

    else:

        a = 0

        for n in range(2, c + 1):

            a = n * a + (-1) ** n

        print(a)

Яка у них, математиків, гарна наука, так? )

Джерело задачі: Збірник завдань для державної підсумкової атестації з інформатики. Автори: Н.В. Морзе, В.П. Вембер, О.Г. Кузьмінська, М.О. Войцеховський, Т.Г. Проценко. Рекомендовано Міністерством освіти і науки України.  2011 рік. 11 клас.  

Варіант 7. Завдання 16:  запишіть програму відомою вам мовою програмування. Вхідні дані вводяться з клавіатури, а вихідні дані виводяться на екран монітора.

Умова:

Дано натуральне число N (8 ≤ N ≤ 1000000), яке визначає будь-яку цілочислову грошову суму ≤ 1000000. Відомо, що цілочислову грошову суму, більшу чи рівну 7 грошовим одиницям, можна видати лише купюрами номіналом у 2 та 5 грошових одиниць. Визначте, якою кількістю купюр у 2 та 5 грошових одиниць можна видати суму в N грошових одиниць, щоб їхня загальна кількість була найменшою.

Кожен бажаючий може зімітувати собі ДПА в 11 класі, для цього достатньо зайти за посиланням на сайт eolymp.com і в швидкому режимі спробувати здати цю задачу однією з наступних мов програмування: С, С++, С#, D, Dart, Go, Haskel, Java, Javascript, Cotlin, Lua, MySQL, Pascal, Perl, PHP, Python, Ruby, Rust. Для роботи на сайті необхідно зареєструватися і підтвердити email. Все безкоштовно.

Давайте спробуємо розв’язати, нехай, за тридцять хвилин, добре? Відмітьте час початку, старт!

Посилання: https://www.eolymp.com/uk/problems/2033

Спробували? Тоді ще більше десяти варіантів розв'язку )

Ця задача відкриває книгу «Олімпіадна інформатика» В.Л.Дідковського і С.В.Матвійчука 2010 року.  Умова:

Нумерація 

https://www.e-olymp.com/uk/problems/109

Для нумерації m сторінок в книжці використано n цифр. По заданому n вивести m або 0, якщо розв’язку не існує. Нумерація починається з першої сторінки.

Вхідні дані

Єдине число n. У книзі не більше 7000 сторінок.

Вихідні дані

Вивести кількість сторінок у книзі.

Приклад вхідних даних:

27

Приклад вихідних даних:

18

Ліміт часу 1 секунда

Ліміт використання пам'яті 128 MiB

Автор: Сергій Матвійчук

Джерело: ІІ етап Всеукраїнської олімпіади в Житомирській області (2003)

Олімпіадне програмування відбувається у вкрай обмеженому проміжку часу. Але у нас зараз не олімпіада, тому пропоную підходити до задачі не поспішаючи, намагаючись підготувати її розв’язок  як для співбесіди щодо прийняття на роботу.

Розберемо умову задачі. Перша сторінка нумерується цифрою один. Нам навіть не принципово якою саме, нам важливо, що ця цифра одна. Отже, для книжки з 1 сторінки  використовується одна цифра, для книжки з двох сторінок використовується дві цифри, якщо конкретно це 1 і 2. Для книжки з 10 сторінок використовується 11 цифр, а саме: 1 2 3 4 5 6 7 8 9 1 0.  У нашому тестовому прикладі, для книги з 18 сторінок використовується 27 цифр: 1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8. Нашою задачею є визначити кількість сторінок по числу цифр.

Може бути ситуація, коли по числу цифр визначити кількість сторінок неможливо. Наприклад, якщо кількість цифр у нумерації сторінок – 26.

Очевидно, якщо номер сторінки однорозрядний (від 1 до 9), то і кількість цифр, що потрібні для нумерації кожної такої сторінки – одна. При нумерації дворозрядних номерів сторінок (від 10 до 99), для нумерації кожної сторінки потрібні дві цифри і т. д. Кількість цифр, необхідних для нумерації сторінки змінюється, коли номер сторінки змінює розрядність, стає 10, 100, 1000. Тобто, 10^x.

Задачу можна розв’язати за допомогою циклу. Будемо збільшувати номер сторінки і зберігати кількість цифр для нумерації поточної сторінки і загальну кількість цифр для нумерації всіх сторінок книги. Завершуємо цикл, коли кількість цифр для нумерування книги дорівнює або перевищує ту, що ми отримали на початку програми у вигляді вхідних даних. При рівності цих змінних необхідно вивести кількість сторінок, інакше — розв’язків не існує і виводимо нуль.

Далі розглянемо класичну цитату Роберта Мартіна з його класичної книги «Чистий код»:

Ім'я змінної, функції або класу має відповідати на всі головні питання. Воно повинно повідомити, чому ця змінна (і т. д.) існує, що вона робить і як використовується. Якщо ім'я вимагає додаткових коментарів, то воно не передає намірів програміста.

int d; // Минулий час

Ім'я d не передає абсолютно нічого. Воно не асоціюється ні з часовими інтервалами, ні з днями. Його слід замінити іншим ім'ям, яке буде вказувати, що саме вимірюється і в яких одиницях:

int elapsedTimeInDays;

int daysSinceCreation;

int daysSinceModification;

int fileAgeInDays;

Змістовні імена істотно спрощують розуміння і модифікацію коду  (кінець цитати).

Якщо проходити співбесіду в місця з цікавими зарплатами, то існує висока вірогідність, що там книги Мартіна читали. Тим більше варто прислухатися.

Визначимо простір імен змінних у стилістиці Python:

input_sum_digits  - (вхідна сума цифр) - кількість цифр, з яких складається книжка, вхідні дані

sum_digits  (сума цифр) – змінна, в якій ми будемо накопичувати суму і порівнювати з input_sum_ digits для  завершення роботи циклу

current_page_number  (номер поточної сторінки) – в змінній зберігатиметься номер сторінки, що опрацьовується при поточній ітерації циклу

number_of_digits_on_current_page (кількість цифр на поточній сторінці) – очевидна величина.

Код з використанням змістовних імен достатньо зрозумілий:

input_sum_digits = int(input())

sum_digits = 0

current_page_number = 0

number_of_digits_on_current_page = 1

while sum_digits < input_sum_digits:

    current_page_number += 1;

    if current_page_number == (10 ** number_of_digits_on_current_page):

        number_of_digits_on_current_page += 1

    sum_digits += number_of_digits_on_current_page

if sum_digits == input_sum_digits:

    print(current_page_number) 

else:

    print(0)

Ось усе це у стилістиці c#:

using System;

namespace MyApp

{

    class Program

    {

        static void Main(string[] args)

        {

            int sumDigits = 0;

            int currentPageNumber = 0;

            int numberOfDigitsOnCurrentPage = 1;

            int inputSumDigits = int.Parse(Console.ReadLine());

            while (sumDigits < inputSumDigits)

            {

                currentPageNumber++;

                if (currentPageNumber == Math.Pow(10, numberOfDigitsOnCurrentPage))

                {

                    numberOfDigitsOnCurrentPage++;

                }

                sumDigits += numberOfDigitsOnCurrentPage;

            }

            if (sumDigits == inputSumDigits)

            {

                Console.WriteLine(currentPageNumber);

            }

            else

            {

                Console.WriteLine(0);

            }

        }

    }

}

Погодьтесь, використання змістовних імен значно спрошує розуміння коду і для самого себе. Уявіть, що ви повернетеся до вашого коду розміром з сотню рядків через рік. Вам спростить розуміння коду використання змістовних імен? А тепер уявіть іншу ситуацію, коли вам треба на фоні дедлайну модифікувати сотні рядків чужого спагетті-коду, створеного з використанням неочевидних імен змінних, класів, методів.  Як вам? Нікому не подобається, тож і ви так не пишіть )

В наші чудові часи шедеври поряд. Інтернет не замінить всіх відчуттів, але тепер можна, наприклад, не їдучі до Музею сучасного мистецтва в Нью-Йорку роздивитися чудо. 

Але шедеври трапляються не лише у живопису. Сьогодні хочу представити чудовий розв’язок задачі. Умова:

Задача «Бочка»
(https://www.e-olymp.com/uk/problems/7375)

Використавши дві посудини ємкістю 3л і 5л потрібно набрати в столітрову бочку M літрів воду, причому сумарна кількість переливань в бочку і з бочки має бути мінімальною. Наприклад, щоб набрати 7 літрів води: два рази виливаємо в бочку по 5л, потім відливаємо один раз 3л, всього три переливання.

Вхідні дані: ціле невід’ємне число M. 0 ≤ M ≤ 100.

Ліміт часу 1 секунда

Ліміт використання пам'яті 64 MiB

Приклад вхідних даних: 7

Приклад вихідних даних: 3

Автор Сергій Матвійчук

Джерело III етеп Всеукраїнської олімпіади з інформатики в Житомирській обл. 2014-2015 р

Як на мене – представлений розв’язок не потребує коментарів або пояснень. Автор даного розв’язку – Віталій Терещук, доктор політичних наук, доцент, відомий у відповідних  колах науковець. Вважаю, що це – шедевр:

vol = int(input())

x3 = 0

x5 = 0

a, b = divmod(vol,10)

if b == 1:

    x3 = 2; x5 = -1

elif b == 2:

    x3 = -1; x5 = 1

elif b == 3 or b == 6 or b == 9:

    x3 = b // 3

elif b == 4:

    x3 = 3; x5 = -1

elif b == 5:

    x5 = 1

elif b == 7:

    x3 = -1; x5 = 2

elif b == 8:

    x3 = 1; x5 = 1

x5  = x5 + (a*2)

totalmoves = abs(x3) + abs(x5)

print(totalmoves)

Сьогодні розв'яжемо достатньо просту задачу.

Але на сайті e-olymp на початок 2020 року задача має рейтинг складності 41%. Це означає, що з тих, хто брався, 41% не змогли розв'язати дану задачу. Отже, умова:

Трицифрове число

https://www.e-olymp.com/uk/problems/5628

 Дано ціле трицифрове число.

Переставляючи цифри цього числа створіть найменш можливе трицифрове число.

Вхідні дані

Одне ціле трицифрове число.

Вихідні дані

Відповідь до задачі.

Ліміт часу 1 секунда

Ліміт використання пам'яті 64 MiB

 Вхідні дані

132

Вихідні дані

123

Ще раз звертаю увагу на уважне читання умови. Трицифрове число, що є вхідними даними, може бути як додатнім, так і від'ємним. Якщо число додатнє, то, очевидно, що треба з трьох цифр сформувати якомога менше число. Саме такому випадку відповідає тестовий приклад:

Вхідні дані

132

Вихідні дані

123

Давайте візьмемо вхідними даними від’ємне число:

Вхідні дані

-132

Очевидно, що розв’язком задачі буде:

-321

Відповідно, якщо вхідне число – від’ємне, то нам треба перестановками сформувати якомога більше по модулю число. 

Крім того, числа, що ми отримаємо після перестановки і які варті уваги, повинні бути трицифрові. Тобто, якщо у вхідних даних число 901, то ми можемо брати до уваги не всі варіанти перестановок, а лише ті, що трицифрові, а таких варіантів чотири: 901, 910, 109, 190. Бо всі інші (19, 91) не є трицифровими. Умову перевірки на трицифровість в даному випадку пропоную використати таку: x>99.

Зверніть увагу, всього з трицифрового числа без знака, можна сформувати перестановками ще п'ять чисел. Разом з вхідним числом буде шість чисел. Можуть бути повтори, звичайно, наприклад якщо вхідним числом буде 111. 

Для початку пропоную запам’ятати, додатнє чи від'ємне у нас число. Далі будемо працювати з модулем числа, формуючи нові числа перестановками і додаючи нові числа в список. За допомогою list comprehension  можна відфільтрувати нетризначні числа і, в залежності, від знака вхідного числа, знайти потрібне нам. 

Виходить, що задача нескладна, якщо уважно прочитати і зрозуміти умову.

Ось один з варіантів самого простого розв’язку:

n = int(input())

s = str(abs(n))

i = []

i.append(int(s)) 

i.append(int(s[0] +  s[2] +  s[1]))

i.append(int(s[1] +  s[2] +  s[0]))

i.append(int(s[1] +  s[0] +  s[2]))

i.append(int(s[2] +  s[1] +  s[0]))

i.append(int(s[2] +  s[0] +  s[1]))

i = [x for x in i if x>99]

if n>0:

    print(min(i))

else:

    print(-max(i))

Звичайно, якщо мова йде про «здати задачу», то такий код нас влаштовує. Якщо ж ви отримали цю задачу на співбесіді при прийомі на роботу, то слабкою ланкою в коді є нарізання шматків тексту і формування з них нових чисел. Пайтон-програмер, що проводить співбесіду, побачивши таке, може подумати, що це ви просто зайшли погрітися. Логічно припустити, що у потужному і стильному Пайтоні існують інструменти, для того, щоб швидко і без помилок сформувати всі можливі варіанти перестановок. Звичайно, так і є, да ще і в стандартній бібліотеці, в модулі itertools.  Наскільки краще читається тепер код, правда? Крім того, підправивши умову відбору тризначних чисел, даний код можна використати для n-значних чисел, не переживаючи, що можна помилитися в нарізанні текстових даних.

from itertools import permutations

n = int(input())

s = str(abs(n))

i = list(map("".join, permutations(s)))

i = [int(x) for x in i if int(x)>99]

if n>0:

    print(min(i))

else:

    print(-max(i))

Перед самим Новим Роком дід Мороз вирішив знайти собі помічничку-Снігурку. Дідусь був трохи дивний – він боявся високих снігурок, але малі йому не подобались. Тому він шукав або таку, яка одного з ним зросту, або трошки меншу.

Дід Мороз прийшов на спеціальні курси і побачив там одночасно стоп’ятсот снігурок. Можна було, звичайно, мірятися зростом з кожною з них, але так можна було шукати до травня. Але дід був програмістом на Python і тому попросив снігурок вишукуватися в шеренгу, як на уроці фізкультури – відсортованими по зросту, від самої малої до самої високої.

Він поділив цю шеренгу навпіл, підійшов до снігурки, що була посередині і помірявся з нею зростом. Снігурка була вища зростом за діда Мороза. Це означало, що серед другої, високої половини снігурок йому пари немає, він їх всіх боїться, тому високу половину можна з пошуків виключити. Половину, що залишилась, він знову поділив на дві частини, підійшов до снігурки, що була посередині і помірявся з нею зростом. Ну і так далі до тих пір, поки не знайшов саме ту Снігурку, що шукав.

Подібний алгоритм пошуку, з поділом сортованого списку на дві частини зветься бінарним або двійковим пошуком. Це відомий і швидкий алгоритм.

І не просто так дід Мороз був програмістом на Python. Річ у тому, що в Python бінарний пошук вже є. Він реалізований в стандартній бібліотеці. Потрібні  діду Морозу функції знаходяться в модулі bisect.  

Якщо б всі снігурки були б різного зросту, то ось як просто діду Морозу знайти свою:

import bisect

did_moroz = 180

snigurky = [151, 160, 163, 171, 175, 180, 183, 200]

moya = bisect.bisect_left(snigurky, did_moroz)

print(moya)

Результат: 5 (п’ята в черзі, черга нумерується від нуля)

Якщо точно такої за зростом немає, то можна знайти найближчу меншу:

import bisect

did_moroz = 174

snigurky = [151, 160, 163, 171, 175, 180, 183, 200]

moya = bisect.bisect_left(snigurky, did_moroz)

print(moya)

Результат: 4 (четверта в черзі, черга нумерується від нуля, це снігурка зі зростом 171)

А якщо зріст снігурок може дублюватися і діду Морозу підходить не одна, а кілька снігурок? Давайте ми йому в такому випадку  скажемо кількість снігурок, що йому підходять, нехай сам з тим розбирається:

import bisect

did_moroz = 180

snigurky = [151, 160, 163, 171, 175, 180, 180, 180, 200]

moya_mensha = bisect.bisect_left(snigurky, did_moroz)

moya_bilsha = bisect.bisect_right(snigurky, did_moroz)

print(moya_bilsha - moya_mensha)

Результат: 3 (діду Морозу підходять три снігурки однакового зросту)

Ось так просто і стильно це все в Python.

Давайте використаємо бінарний пошук для розв’язання задачі 3970 з e-olymp – з назвою МУТАНТИ.

Умова:

Вже тривалий час в Інституті Местецтв, Мутантів та Інформаційоних Технологій розводять милих різнокольорових звіряток. Для зручності кожний колір позначено своїм номером, усього кольорів не більше 10⁹. В один з прекрасних днів у розпліднику сталося диво: усі тваринки вишикувалися в ряд в порядку зростання кольорів. Користуючись нагодою, лаборанти вирішили порахувати, скільки звіряток різних кольорів живе у розпліднику, і, за законом жанру, попросили вас написати програму, яка допоможе їм у вирішенні цього нелегкого завдання.

Вхідні дані

У першому рядку вхідного файлу міститься єдине число N (0 ≤ N ≤ 10⁵) - кількість звіряток в Інституті. У наступному рядку знаходиться N упорядкованих за неспаданням невід'ємних цілих чисел, які не перевищують 10⁹ і відокремлених пропусками - їх кольори. У третьому рядку файлу записано число M (1 ≤ M≤ 100000) - кількість запитів вашій програмі, у наступному рядку через пропуск записано M цілих невід'ємних чисел (які не перевищують 10⁹+1).

Вихідні дані

Вихідний файл повинен містити M рядків. Для кожного запиту виведіть кількість звіряток заданого кольору у розпліднику.

Ліміт часу 4 секунди

Ліміт використання пам'яті 64 MiB

Вхідні дані #1

10

1 1 3 3 5 7 9 18 18 57

5

57 3 9 1 179

Вихідні дані #1

1

2

1

2

0

Можна підряд перебирати список і шукати потрібні елементи. Але при такому підході ми не встигнемо розв’язати задачу за відведений час. Тому, розуміючи, що бінарний пошук – чудова по оптимальності штука, давайте використаємо саме його. Думаю, після допомоги діду Морозу в його пошуку Снігурок, лістинг програми «Мутанти» не потребує пояснень:

from bisect import bisect_left, bisect_right

n = int(input())

colors = [int(x) for x in input().split()]

m = int(input())

request = [int(x) for x in input().split()]

for i in range(m):

    find_left = bisect_left (colors, request[i])

    find_right = bisect_right(colors, request[i])

    print (find_right - find_left)

Ну от класно ж, на початку зими витягти з шафи зимову куртку і в кишені знайти щось приємне — цукерку, забуту купюру або  щасливий квиток. Так буває і в Python – працюєш, ліпиш, видумуєш, а потім виявляється, що все можна зробити гарніше і простіше. Що розумні люди цей велосипед давно вже придумали. Бери та й катайся.

Сьогодні розберемо задачу 835 з e-olymp – з назвою ПОКЕР.

Умова:

Задано 5 цілих чисел. Серед них:

• якщо однакові 5, то вивести "Impossible", інакше
• якщо однакові 4, то вивести "Four of a Kind", інакше
• якщо однакові 3 і 2, то вивести "Full House", інакше
• якщо є 5 послідовних, то вивести "Straight", інакше
• якщо однакові 3, то вивести "Three of a Kind", інакше
• якщо однакові 2 і 2, то вивести "Two Pairs", інакше
• якщо однакові 2, то вивести "One Pair", інакше
• вивести "Nothing".

Вхідні дані

У першому рядку задано 5 чисел (від 1 до 13 включно) через пропуск.

Вихідні дані

Виводиться один рядок - результат аналізу.

Ліміт часу 1 секунда

Ліміт використання пам'яті 64 MB

Приклади:

Sample 1

1 3 9 3 2

One Pair

Sample 2

1 5 5 4 4

Two Pairs

Sample 3

1 5 2 4 3

Straight

Sample 4

10 11 12 13 1

Nothing

У більшості мов програмування  закидаємо числа в масив або список і граємося за допомогою комбінацій IF. Чи можна так розв’язати задачу? Звичайно. Але пайтон — то як модна куртка з купою кишень. І в деяких кишенях ховаються справжні смаколики. Сьогодні дістанемо модуль сollection. При чому цей модуль дістанемо зі стандартної бібліотеки, не треба гукати pip або GitHub.

А в модулі сollection є чудова штука - Counter - вид словника, який дозволяє рахувати кількість незмінних об'єктів.

А функція  most_common ([n])  повертає n елементів, що найчастіше зустрічаються, в порядку убування зустрічальності (сподіваюсь, що мене не читають філологі, бо приб’ють).

Якщо n не вказано, повертаються всі елементи.

Давайте на прикладі:

import collections

girls  = ['гарна', 'дуже гарна', 'гарна', 'страшно гарна', 'неймовірно гарна', 'дуже гарна', 'дуже гарна']

c = collections.Counter(girls)

Ось  як воно працює, якщо попросити всі елементи і частоту їх в послідовності:

print(c.most_common())

# [('дуже гарна', 3), ('гарна', 2), ('страшно гарна', 1), ('неймовірно гарна', 1)]

Визначити елемент, що зустрічається частіше за всіх  і його лічильник можна так:

print(c.most_common(1)[0][0])

# 'дуже гарна'

print(c.most_common(1)[0][1])

# 3

Можна сформувати повний список, а не лише одну пару (елемент-лічильник) і знайти, наприклад, який елемент другий по популярності в послідовності і скільки разів він зустрічається:

print(c.most_common()[1][0])

# 'гарна'

print(c.most_common()[1][1])

# 2

Перейдемо до задачі про покер.  Як дізнатися, що елемент в послідовності зустрічається 5 разів?

if c.most_common(1)[0][1] == 5:

    print('Impossible')

Ну і так далі. Думаю, зрозуміло. Але там є хитрість щодо варіанта "Straight", тобто якщо є 5 послідовних, наприклад 1 5 2 4 3.

Тут, як на мене, варто відсортувати список елементів і порівняти значення першого і останнього. Якщо різниця між ними – чотири, то це і буде те, що нам треба. Але перевірку на "Straight" необхідно проводити в самому кінці програми, тому що інакше програма невірно відпрацює, наприклад, варіант «1 5 5 4 4». Тому нехай спочатку відпрацюють всі попередні правила, а лише потім перевіримо послідовність на "Straight".

І ще, давайте оптимізуємо програму, щоб якомога рідше викликати most_common(). Все ж функція хоч і внутрішня, оптимізована, але час для роботи їй потрібен. Тим більше, що нам треба лише два перших значення лічильника. При чому, якщо послідовність буде «1 1 1 1 1», то другого значення лічильника взагалі не отримаємо, тому що всі елементи однакові.

Враховуючи описані вище нюанси, пропоную свій варіант програми. Своїх учнів я прошу уважно переглянути кожен рядок. Всі варіанти оптимізації або власних підходів – вітаються як завжди.

# Задача 835

# www.e-olymp.com/uk/problems/835

import collections

lst = [int(x) for x in input().split()]

lst.sort()

c = collections.Counter(lst)

first_counter = c.most_common(1)[0][1]

second_counter = c.most_common(2)[1][1] if first_counter != 5 else 0

if first_counter == 5:

    print('Impossible')

elif first_counter == 4:

    print('Four of a Kind')

elif first_counter == 3 and second_counter == 2:

    print('Full House')

elif first_counter == 3:

    print('Three of a Kind')

elif first_counter == 2 and second_counter == 2:

    print('Two Pairs')

elif first_counter == 2:

    print('One Pair')

elif lst[4] - lst[0] == 4:

    print('Straight')

else:

    print('Nothing')

Відома задача, про яку чимало написано, як в серйозних виданнях по теорії ймовірностей так і на Вікіпедії.

Давайте спростимо умову до загальноголюдського  розуміння. Якщо в певній групі людей, наприклад в шкільному класі буде 500 учнів, то яка вірогідність того, що два учні будуть мати однаковий день народження, тобто однакове число і один місяць? Звичайно,  100%. Ми зараз не говоримо про те, як буде виглядати нещасний класний керівник такого великого класу :) , ми про математику. А якщо в класі буде 366 дітей, а рік приймемо за 365 днів, то яка вірогідність? Так, знову 100%. У варіанті, коли дні народження перших 365 дітей розподіляться рівномірно на весь рік: 1 січня, 2 січня і т.д., то 366 по списку дитині вільних днів вже не залишиться, а це означає що його день народження співпаде з днем народження іншої дитини в класі. А тепер припущення:

У групі, що складається з 23 або більше осіб, ймовірність збігу днів народження (число і місяць) хоча б у двох людей перевищує 50%. Наприклад, якщо в класі 23 учня або більше, то більш імовірно те, що у когось з однокласників дні народження припадуть на один день, ніж те, що у кожного буде свій неповторний день народження.

На перший погляд – це неправда. Так, у моєї доньки в класі з 30 учнів є дві дівчини, що народилися в один день і місяць. В школі, де я працюю, так само співпадають дні народження двох вчителів інформатики. Але при порівняно невеликій групі з 23 осіб мати вірогідність більше ніж 50% - це, здається, математичною помилкою. Але – ні. В російськомовній Вікі дуже детально все розписано, саме її і раджу для системного аналізу.

А тепер задача з e-olymp.com на цю тему:

Дні народження

https://www.e-olymp.com/uk/problems/1317

Відомо, що у групі з 23 або більше людей ймовірність того,  що хоча б у двох з них дні народження (число та місяць) співпадуть, перевищує 50%. Цей факт може здатись як таким, що протирічить здоровому глузду, так як ймовірність одному народитись у певний день року досить мала, а ймовірність того, що двоє народились у конкретний день – ще менша, але є вірним у відповідності з теорією ймовірності. Таким чином, факт не є парадоксом у строгому науковому сенсі – логічного протиріччя у ньому нема, а парадокс полягає лише у відмінностях між інтуїтивним сприйняттям ситуації людиною та результатами математичного розрахунку.

Для заданої кількості людей обчислити ймовірність того, що двоє з них народились у один день року. Рік вважати рівним 365 дням.

Вхідні дані

Кожен рядок є окремим тестом і містить кількість людей n (1 < n < 400).

Вихідні дані

Для кожного значення n в окремому рядку вивести ймовірність того, що хоча б у двох з n людей дні народження (число та місяць) співпадають. Шукану ймовірність виводити у відсотках і округлювати до 8 знаків після коми як показано у прикладі.

Ліміт часу: 1 секунда

Ліміт використання пам'яті: 64 MB

Джерело: Медведев М.Г. – «Зимняя школа в Харькове 2009»

Класифікація задачі: теорія ймовірностей

Давайте аналізувати.  Вікі права:

У групі з 23 людей ймовірність збігу днів народження у двох людей настільки висока, тому що розглядається ймовірність збігу днів народження у будь-яких двох людей в групі. Ця ймовірність визначається кількістю пар людей, які можна скласти з 23 чоловік. Так як порядок людей в парах не має значення, загальне число таких пар дорівнює числу сполучень з 23 по 2, тобто (23 × 22) / 2 = 253 пари.

У формулюванні парадоксу мова йде саме про збіг днів народження у будь-яких двох членів групи. Одна з поширених помилок полягає в тому, що цей випадок плутають з іншим випадком, на перший погляд схожим, коли з групи вибирається одна людина, і оцінюється ймовірність того, що день народження будь-яких інших членів групи співпаде з днем ​​народження цієї обраної людини. В такому випадку ймовірність збігу значно нижче.

Сподіваюсь, теорію на вікі вже прочитали. З математичної точки зору при рівномірному розподілі:

Наведене в червоному прямокутнику можна розписати математично:

Ну а на Python наведене в червоному прямокутнику реалізується просто і елегантно:

x = 1
for i in range(2, n+1):
     x *= 1 - (i-1)/365

Все інше – деталі. Робота з файлами описана, хто забув, у Пісочниці, в задачі «Робота з текстовими файлами в Python».

А для тих, хто забув про форматування виводу змінних в Python, існує довідник «input_print».

А в вашому класі скільки учнів? А в вашому класі є співпадіння днів народження?

Ps. Для учасників гуртка i7 здача задачі є обов’язковою, код мені в телеграм, будь ласка, PEP8, ага :)