Шановні учні!

Даний довідник може стати вам у пригоді для розв'язку задач

Введення цілих чисел:

Якщо вам треба ввести ціле число від користувача в вашу програму, то використовуйте конструкцію:

x = int(input())

Якщо вам треба ввести два цілих числа, кожне з яких записане в окремому рядку, то це можна зробити так: 

x = int(input())

y = int(input())

Якщо вам треба ввести в вашу програму кілька цілих чисел, що записані через пропуск, то це можна зробити так: 

a, b, c = map(int, input().split())

Введення дійсних чисел:

Якщо вам треба ввести дійсне число від користувача в вашу програму, то використовуйте конструкцію:

x = float(input())

Якщо вам треба ввести в вашу програму кілька дійсних чисел, що записані через пропуск, то це можна зробити так: 

a, b, c = map(float, input().split())

Введення тексту:

Якщо вам треба ввести текст від користувача в вашу програму то використовуйте таку конструкцію:

x = input()

Якщо вам треба ввести текст від користувача в вашу програму, при цьому обрізати пропуски на початку тексту і в кінці, то використовуйте таку конструкцію:

x = input().strip()

Пам'ятайте, що з текстом не можна проводити математичні операції. З тексту ви можете вирізати один або кілька символів, і вирізана частина буде також текстом. Якщо ж вам треба виконати математичні дії з цими даними, то треба конвертувати текст в число. Якщо це стосується цілих чисел, то конструкція така:

y = int(x)

Приклад обчислення квадратного кореня:

import math

x = math.sqrt(4)

print(x)

Виведення даних:

Для виведення даних використовується оператор print()

Приклад виведення тексту:

print('Страшно хочу в школу!')

Приклад виведення числа:

a = 5

b = 3

print(a-b)

Для виведення дійсного числа з певною кількістю знаків після коми можна скористатися f-рядками. 

Приклад: Треба вивести дійсне число з трьома знаками після коми:

x = 12.34567

print(f"{x:.3f}")

Розгалуження:

Задача для прикладу:

Програма повинна прочитати від користувача ціле число та вивести -1, 0 або 1, якщо введене значення від’ємне, нульове і додатне, відповідно.

Приклад коду: 

n = int(input())

if n < 0:

    print(-1)

elif n == 0:

    print(0)

else:

    print(1)

Цикл FOR:

Задача для прикладу:

Програма повинна прочитати від користувача ціле число та вивести числа від одиниці до цього числа включно. Кожне число - в окремому рядку.

Приклад коду: 

 n = int(input())

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

    print(x)

Задача для прикладу:

Програма повинна прочитати від користувача ціле число та вивести числа від цього числа до нуля в порядку зменшення. Кожне число - в окремому рядку.

Приклад коду: 

n = int(input())

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

    print(x)

Якщо це саме треба зробити так, щоб всі числа були в одному рядку, ось приклад:

n = int(input())

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

    print(x, end = ' ')

Розбираємо задачу з 8545 з e-olimp під назвою «Таблиця множення».

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

Проста задача, в принципі. Знову таки, з дивно високим коефіцієнтом складності, 21%.  Треба побудувати квадратну матрицю, як на обкладинках зошитів з математики. Вхідні дані - розмірність матриці, від 1 до 9 включно. Результат відповідним чином відформатувати:

n = 5

 1  2  3  4  5

 2  4  6  8 10

 3  6  9 12 15

 4  8 12 16 20

 5 10 15 20 25

n = 7

 1  2  3  4  5  6  7

 2  4  6  8 10 12 14

 3  6  9 12 15 18 21

 4  8 12 16 20 24 28

 5 10 15 20 25 30 35

 6 12 18 24 30 36 42

 7 14 21 28 35 42 49

Запропонував Саша цю задачу. З приміткою «неробіт». Проходить 70% тестів. E-olimp, на відміну від codeforces, тести не відкриває, шукаємо помилку аналітично.

Показав Саша код:

a = int(input())

if a == 1:

    print( '1')

elif a == 2:

    print(' 1  2\n 2  4')

elif a == 3:

    print(' 1  2  3 \n 2  4  6 \n 3  6  9')

elif a == 4:

    print(' 1  2  3  4 \n 2  4  6  8 \n 3  6  9 12 \n 4  8 12 16')

elif a == 5:

    print(' 1  2  3  4  5 \n 2  4  6  8 10 \n 3  6  9 12 15 \n 4  8 12 16 20 \n 5 10 15 20 25')

elif a == 6:

    print(' 1  2  3  4  5  6 \n 2  4  6  8 10 12 \n 3  6  9 12 15 18 \n 4  8 12 16 20 24 \n 5 10 15 20 25 30 \n 6 12 18 24 30 36')

elif a == 7:

    print(' 1  2  3  4  5  6  7 \n 2  4  6  8 10 12 14 \n 3  6  9 12 15 18 21 \n 4  8 12 16 20 24 28 \n 5 10 15 20 25 30 35 \n 6 12 18 24 30 36 42 \n 7 14 21 28 35 42 49')

elif a == 8:

    print(' 1  2  3  4  5  6  7  8 \n 2  4  6  8 10 12 14 16 \n 3  6  9 12 15 18 21 24 \n 4  8 12 16 20 24 28 32 \n 5 10 15 20 25 30 35 40 \n 6 12 18 24 30 36 42 48 \n 7 14 21 28 35 42 49 56 \n 8 16 24 32 40 48 56 64')

else:

    print(' 1  2  3  4  5  6  7  8  9 \n 2  4  6  8 10 12 14 16 18 \n 3  6  9 12 15 18 21 24 27 \n 4  8 12 16 20 24 28 32 36 \n 5 10 15 20 25 30 35 40 45 \n 6 12 18 24 30 36 42 48 54 \n 7 14 21 28 35 42 49 56 63 \n 8 16 24 32 40 48 56 64 72 \n 9 18 27 36 45 54 63 72 81 ')

Звичайно, Саша дізнався про себе багато цікавого після оприлюднення такого щастя :)

Колегі-програмісти нагадали, що так робити не під час олімпіади – гріх.  Навіть запропонували з таким підходом приєднатися до написання прекрасного AceLewis-калькулятора. До речі, хто не в курсі, що це таке, дуже раджу ознайомитися, скоріше за все ви, як це побачите, то не забудете ніколи.

Чудовий в своєму різноманітті інструментарію Python дозволяє чудово форматувати текст при виводі. Нам треба вирівняти текст вправо в межах двох символів? Не проблема. Як просто і елегантно, правда?

n = int(input())

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

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

        print(str(x*y).rjust(2), end = ' ')

    print()

Не дуже популярна у нас інтелектуальна гра – це відомий європейський хіт. Гра року Швеції (2005), Фінляндії (2006), Франції (2006), володар призу Mensa Select (2006).   Абстрактна гра для двох гравців, винайдена Томасом Флоденом (Tomas Flodén). Комерційні права на Пентаго належать шведської кампанії Mindtwister Games. Гра має офіційний сайт, з 2006 року в технічному музеї в Стокгольмі проводиться чемпіонат з Pentago.

Стандартні класичні правила:

Гра проводиться на полі 6 на 6 лунок. Ігрове поле поділено на чотири сектори, кожний сектор обертається навколо своєї осі. Грають два гравця, у одного шари чорного кольору, у іншого – білого. Грають по черзі. Гравець кладе шар свого кольору в одну з вільних лунок після чого повинен повернути один  будь-який з чотирьох секторів ігрового поля на 90 градусів або за годинниковою стрілкою або проти. Після чого ходить інший гравець своїм кольором шару аналогічним чином.  Виграє той, хто побудує пряму лінію з п’яти шариків свого кольору по горизонталі, вертикалі або діагоналі.  В принципі – все.

Ціна офіційної версії гри на Розетці – 600 гривень. Ціна китайської версії на Аліекспресі  починається від 300 гривень.  В Україні продається цікава версія для кількох гравців, трьома кольорами шарів і картками.  

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

Цікаве, як на мене, відео-представлення гри від Светлани Коробач, вони в родині навіть трохи ускладнили правила:

Як то кажуть – рекомендую! 

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

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

Художник – аргентинський. Пазл – німецький. Кабінет інформатики – наш. І головне – діти. Українські. Розумні, позитивні, вперті. Було спекотно, складно. Але вони це зробили.

Фільм про те, як команда «i7 і друзі» збирала пазл «Crazy World Cup»

Ну от класно ж, на початку зими витягти з шафи зимову куртку і в кишені знайти щось приємне — цукерку, забуту купюру або  щасливий квиток. Так буває і в 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')