Ну от класно ж, на початку зими витягти з шафи зимову куртку і в кишені знайти щось приємне — цукерку, забуту купюру або щасливий квиток. Так буває і в 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
|
Вхідні дані
|
Вихідні дані
|
|
2
|
0.27397260%
|
|
10
|
11.69481777%
|
|
23
|
50.72972343%
|
|
366
|
100.00000000%
|
Джерело: Медведев М.Г. – «Зимняя школа в Харькове 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, ага :)
На дошці виписані числа від 1 до 2150.
Кожну хвилину кожне число піддається наступній операції: якщо число націло ділиться на 100, то його ділять на 100, якщо ж не ділиться, то від нього віднімають 1. Знайдіть найбільше серед чисел на дошці через 87 хвилин.
Спочатку пробуйте самостійно, а потім можете перевірити свою відповідь, переглянути розумне математичне пояснення і код перебору на python
Час, коли всі школярі України вчили Pascal, на щастя, закінчується. Парадоксальність ситуації була в тому, що в школі (да і в інститутах, до речі) вчили мову програмування, яка для реальної роботи була практично непотрібна. Сьогодні в школах та інститутах іноді вивчають те, що має шанс бути реально прикладним. А що є прикладним, легко перевіряється за допомогою індексу TIOBE, наприклад. Незважаючи на його певні особливості, пов’язані з методикою оцінки, він достатньо системно представляє масовість використання сучасних мов програмування.
Курси університетів необхідно розглядати окремо через більш дорослий вік цільової аудиторії. До того ж треба враховувати, що університети розробляють свої курси програмування, і що крім харизматичного Девіда Малана з його CS50, існує чимало альтернатив. А щодо шкільного програмування, то, на думку автора, на 2017 рік, реальних варіантів з мовами програмування - три.
Перше – це «ще не вмерлий» паскаль і його доживаюча об’єкт-реінкарнація у вигляді Lazarus та Delphi. По друге — варіанти мови сі. Ну і, звичайно, python з неймовірною простотою синтаксису, шикарно низьким порогом входження, вбудованою черепашкою, морем сторонніх модулів і стабільним п’ятим рядком в індексі TIOBE-2017.
Вибір очевидний, починаємо з Python, навчаємось працювати ефективно, з часом переходимо до вмінь використання сторонніх бібліотек та API. Як мінімум, через те що GitHub вже давно став океаном якісного коду.
Сучасна логіка підготовки школяра, на думку автора – це необхідність підготувати цього самого школяра до реальної роботи. Не в межах шкільної програми або олімпіадного програмування, а в межах компетенцій, які вимагаються роботодавцями. І тут треба врахувати певні особливості.
Олімпіадне програмування має дуже багато цікавих граней. Це і різні типи задач, і формат змагань, тайм-ліміти і багато іншого. На думку автора, при підготовці учнів, необхідно максимально дистанціюватися від системи «просто заробити більше балів». А максимально орієнтувати школярів шукати оптимальні розв’язки. Тому що, незважаючи на значне підвищення швидкості апаратної частини, роботодавця часто цікавить не працюючий «спагеті-код» на ранок, а в міру оптимальний і зрозумілий в ком’юніті код за розумний час.
Час самозваних геніїв завершився масовістю і якістю освіти в сфері програмування. І код, що написаний сьогодні одним програмістом назавтра може читатися і редагуватися іншим. Для роботодавця оптимально, щоб обидва вони були професіонали, що мають взаємозрозумілі системи знань і навичок.
В якості ілюстрації вищенаведеного, автор пропонує розглянути задачу II (міскрайонного) етапу олімпіади з програмування серед школярів Житомирської області 2003 року.
Link: https://www.e-olymp.com/uk/problems/109
Автор задачі – С. В. Матвійчук, вчитель Ружинської гімназії. Сергій Володимирович є автором частини задач, що пропонуються на II і III етапі всеукраїнської олімпіади з програмування.
Також С.В. Матвійчук є співавтором книги «Олімпіадна інформатика» де зібрані цікаві задачі олімпіад 2000-2010 року.
Отже, умова:
Для нумерації m сторінок в книжці використано n цифр. По заданому n вивести m або 0, якщо розв’язку не існує. Нумерація починається з першої сторінки.
Вхідні дані
Єдине число n. У книзі не більше 1001 сторінки.
Вихідні дані
Вивести кількість сторінок у книзі.
Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB
Приклад вхідних даних
27
Приклад вихідних даних
18
Деякі пояснення щодо тестового прикладу.
На першій сторінці стоїть номер сторінки – цифра 1. На десятій сторінці – дві цифри, один и нуль. В тестовому прикладі 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
Це і буде вісімнадцята сторінка.
Ось який розв’язок даної задачі пропонує в свої частині книги її співавтор, С.В.Матвійчук:
На думку автора данного тексту, Сергій Володимирович представив класичний приклад поганого олімпіадного програмування. В якому немає ні стилю ні оптимальності. І якщо претендент на вакансію в серйозне місце представить такий код на співбесіді, то з величезною ймовірністю, отримає абсолютно об’єктивну відмову. В даному випадку мова навіть не про синтаксичні приколи на кшталт ReSet та незрозумілі однобуквені великомалі назви змінних. Хоча програмісти потенційного роботодавця можуть бути проти нового колеги, який пише текст на кшталт «приВіт, хлоп4Ики !!». Мова про традиційний для олімпіадного програмування підхід – швидко зробити программу заради балів. Сергій Володимирович детально пояснив свій розв'язок і запропонував свій код.
Очевидно, що при вхідному n=2889, його програма майже тисячу разів виконає цикл repeat-until
Для олімпіадного програмування і компілятора мови Pascal, в межах заданих time-лімітів – задача проходить всі тести.
Але не дуже зрозуміло, навіщо робити розв’язки, що можуть пройти на олімпіаді і непотрібні в індустрії? Автору дещо дивно бачити такий розв’язок у книзі, яка навчає олімпіадного програмування і він пропонує інший.
І почати пропонується не з математичного, а зі звичайного «на хлопський розум» аналізу.
Зі сторінками і цифрами від 1 до 9 все просто. Якщо для нумерування книги використано п’ять цифр, то сторінка п’ята, якщо використано дев’ять цифр, то сторінка дев’ята.
Отже, якщо для нумерування книги використано від 1 до 9 цифр – то кількість сторінок в книзі є числом в межах від 1 до 9.
Для нумерування книги з 10 сторінок треба використати 11 цифр: 1 2 3 4 5 6 7 8 9 1 0
Для нумерування книги з 11 сторінок треба використати 13 цифр: 1 2 3 4 5 6 7 8 9 1 0 1 1
Двозначних номерів сторінок (від 10 до 99) – 90. Для нумерації кожної треба дві цифри, тобто для нумерування сторінок від 10 до 99 — нам потрібно 180 цифр.
Якщо для нумерування книги використано від 10 до 189 цифр – то кількість сторінок в книзі є числом в межах від 10 до 99. Де ми взяли 189? 9+90*2=189. Крім того, ми можемо перевірити коректність даних. Якщо для нумерування книги використано від 10 до 189 цифр, то при відніманні дев’яти, отримане число повинно націло ділитися на два.
Тризначних номерів сторінок (від 100 до 999) – 900. Для нумерації кожної з таких треба три цифри. Для нумераціі 900 сторінок (від 100 до 999) нам треба 900*3=2700 цифр.
Отже, якщо для нумерування книги використано від 190 до 2889 цифр – то кількість сторінок в книзі є числом в межах від 100 до 999. Де ми взяли 2889? 9+90*2+900*3=2889. Крім того, ми можемо перевірити коректність даних. Якщо для нумерування книги використано від 190 до 2889 цифр, то при відніманні 189, отримане число повинно націло ділитися на три.
Залишається два числа сторінок, з якими ми попрацюємо індивідуально, сторінка 1000 і сторінка 1001. Це максимальне число сторінок в книзі, згідно умови.
До речі, розрахунки легко перевірити п’ятирядковою програмою «навиворот». На вхід будемо давати номер сторінки, а програма порахує кількість цифр, що треба буде використати:
stor = int(input())
kilk_tsyfr = 0
for x in range(1, stor+1):
kilk_tsyfr += len(str(x))
print(kilk_tsyfr)
Наша простенька програма підтвердила, що для нумерації книги з 99 сторінок потрібно 189 цифр. Ми можемо за допомогою неї сформувати відповідність кількості сторінок і кількості використаних для нумерування цифр:
1 – 1
5 – 5
10 – 11
80 – 151
99 – 189
100 – 192
101 – 195
998 – 2886
999 – 2889
1000 – 2893
1001 – 2897
На даному матеріалі написання програми для розв’язання задачі — питання часу. Автор пропонує варіант програми, яка за один проход, без жодного циклу, розв’язує дану задачу. Лістинг публікується повністю, що дає можливість перевірки розв'язків для всіх варіантів умов.
n = int(input())
if n <= 9:
print(n)
elif 10 <= n <=189:
n = n - 9
if n % 2 != 0:
print(0)
else:
print(n//2 + 9)
elif 190 <= n <= 2889:
n = n - 189
if n % 3 != 0:
print(0)
else:
print(n//3 + 99)
elif n == 2893:
print(1000)
elif n == 2897:
print(1001)
else:
print(0)
У коробці лежать 7 карток, на яких з одного боку написана одна з цифр: 1, 2, 3, 4, 5, 6, 9.
З коробки послідовно дістають картки у випадковому порядку і кладуть на стіл одну за одною, утворюючи 7-значне число. Яка ймовірність того, що отримане число просте?
Відповідь запишіть у вигляді десяткового дробу.
Джерело: Problem-solving strategies for efficient and elegant solutions: a resource for the mathematics teacher. (Alfred S. Posamentier, Stephen Krulik)
Якщо розв'язувати задачу перебором, то можна використати функцію permutations(), за допомогою якої можна сформувати список, в якому будуть всі варіанти перестановок даних карток:
lst = list(map("".join, permutations('1234569')))
Функція permutations() знаходиться в модулі itertools.
А можливо, ви знайдете своє рішення?
Фотка не просто так :)
Успіхів!
