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

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

Задача «Бочка»
(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.com на чистих акаунтах. Під час олімпіади можна користуватися help-системою мови програмування. Через те, що навчальний рік тільки розпочався і деякі учні позабували синтаксис, можна користуватися довідниками мови Python.

Приємно, що завантажені навчанням студенти-випускники школи кожного року мотивують молодь своїми гарними результатами по принципу «Навчайтеся, і ви також все це зможете зробити». Цього року у відкритій шкільній  олімпіаді взяли участь студенти-айтішники КПІ, Львівської політехніки, НАУ. А студентка медичного факультету університету ім. Богомольця журилася, що «забула увесь Пайтон» але при цьому не забула математику і вивела формулу для однієї з задач.

В даній статті хочу звернути увагу на задачу «Байтик і шахи» (https://www.e-olymp.com/uk/problems/8659).

Нескладна задача, що має на e-olymp.com рейтинг складності лише 12%.

Ось умова:

Байтик та шахи

Якось, вкотре запізнившись на урок, Байтик, проходячи повз ігрову кімнату, помітив шахову дошку. Порахував усі клітинки на ній, і йому стало цікаво: скільки різних квадратів зі стороною k (1≤ k ≤ n) можна розмістити на дошці розміру n.

Вхідні дані:

Натуральне число n (n ≤ 10000) розмір шахової дошки.

Вихідні дані:

Єдине число – кількість різних квадратів, які можна розмістити на шаховій дошці.

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

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

Логічними міркуваннями, листочком і олівцем можна легко знайти кілька окремих випадків. Наприклад, при n=1 очевидно, що кількість різних квадратів – 1. При n=2, тобто дошці 2 на 2 клітинки, квадратів буде п’ять, чотири малих і один загальний, що вміщує в себе чотири малих.

При n =3 відповідь - 14.  Це можна порахувати вручну або просто подивитися тестовий приклад в умові задачі.

Давайте складемо табличку:

Тут можна побачити класичну задачу з розділу динамічного програмування. Кожне наступне число-відповідь, це n в квадраті плюс відповідь від попереднього n. Відповідно, для n=4, відповідь буде 4*4 + 14 = 30.

На Python це буде, наприклад, так:

n = int(input())

s = 0

for x in range(1, n+1):

    s += x**2

print(s)

Я попросив у учнів дозволу переглянути код їх розв’язків. І здивовано побачив такий розв’язок цієї задачі:

n = int(input())
print('{:.0f}'.format((n*(n+1)*(2*n+1))/6))

Це студентський розв’язок. КПІ, 1 курс, прикладна математика. Питаю: «звідки формула»?

Почув відповідь: «Це квадратне пірамідальне число. Нам тиждень тому пояснював це викладач матану. Це не було темою, це він відповідав на запитання під час ZOOM-лекції».

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

Де замість циклу  використовують формулу. Згадують її або виводять з голови. Там, де неоптимально – це погано, і внутрішня освіта за таке сварить. Де олімпіадний принцип «здати у відведений час»  - це недостатньо. Тому що і на співбесідах і на роботі — інші критерії.

Можливо, гарна вища айтішна освіта – це коли в голові не розкидані сторінки різних  класних книжок, а більш-менш серйозна бібліотека?

Як Ви вважаєте?

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

Але на сайті 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')