В наші чудові часи шедеври поряд. Інтернет не замінить всіх відчуттів, але тепер можна, наприклад, не їдучі до Музею сучасного мистецтва в Нью-Йорку роздивитися чудо.
Але шедеври трапляються не лише у живопису. Сьогодні хочу представити чудовий розв’язок задачі. Умова:
Задача «Бочка»
(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 – з назвою МУТАНТИ.
Умова:
Вже тривалий час в Інституті Местецтв, Мутантів та Інформаційоних Технологій розводять милих різнокольорових звіряток. Для зручності кожний колір позначено своїм номером, усього кольорів не більше 109. В один з прекрасних днів у розпліднику сталося диво: усі тваринки вишикувалися в ряд в порядку зростання кольорів. Користуючись нагодою, лаборанти вирішили порахувати, скільки звіряток різних кольорів живе у розпліднику, і, за законом жанру, попросили вас написати програму, яка допоможе їм у вирішенні цього нелегкого завдання.
Вхідні дані
У першому рядку вхідного файлу міститься єдине число N (0 ≤ N ≤ 105) - кількість звіряток в Інституті. У наступному рядку знаходиться N упорядкованих за неспаданням невід'ємних цілих чисел, які не перевищують 109 і відокремлених пропусками - їх кольори. У третьому рядку файлу записано число M (1 ≤ M≤ 100000) - кількість запитів вашій програмі, у наступному рядку через пропуск записано M цілих невід'ємних чисел (які не перевищують 109+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
|
Вхідні дані
|
Вихідні дані
|
|
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, ага :)
Час, коли всі школярі України вчили 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.
А можливо, ви знайдете своє рішення?
Фотка не просто так :)
Успіхів!
Скільки можна?
(https://www.e-olymp.com/uk/problems/20)
Дано натуральне число n. Від даного числа віднімемо суму цифр цього числа, від утвореного числа знову віднімемо суму цифр утвореного числа і т. д. Дану операцію над числом будемо виконувати, поки утворене число додатне. Скільки разів будемо виконувати дану операцію.
Вхідні дані
Одне натуральне число n, що не перевищує 2 *109.
Вихідні дані
Кількість виконаних операцій.
Ліміт часу 2 секунд
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
21
Вихідні дані #1
3
Дана задача – яскравий приклад задач на e-olymp, умови яких не дають можливості розв’язання задачі на 100% мовою python через обмеження часу. Всі знають, що python – інтерпретатор, а, відповідно, достатньо повільний.
На python наразі я зробив два розв’язки, обидва проходять 70% тестів на e-olymp. Рішення на 100% я не знайшов.
Виникає концептуальне питання – а як до цього ставитися? На дану хвилину я переконаний, що python – найкращий для навчання учнів (незважаючи на неймовірну крутизну Brainfuck і Whitespace). І треба враховувати, що частину задач в системі e-olimp не можна здати на 100% мовою python. Виходів тут, як мінімум, я бачу два:
1. Прийняти такий стан речей як інформацію і жити далі. Якщо ви плануєте у майбутньому бути програмером, то вам скоріше за все з часом буде треба познайомитися з однією з швидких, «компільованих» мов, щось із родини сі-подібних. Якщо ваші думки плинуть у сторону продуктів яблучної компанії, то варто звернути увагу на Objective C та найновішу на даний час мову від Apple під назвою Swift. Не можу рекомендувати Pascal. Вчити мову, знання якої не допоможе вам у працевлаштуванні, немає практичного сенсу. Нішу простої мови для початкового навчання шикарно зайняв python, а для швидких програм дідусь Pascal не може бути конкурентом родині сі, яка живе і розвивається.
2. Другий вихід при неможливості здати частину задач на e-olymp мовою python завдяки обмеженнях по часу – це відмовитися від мови python, замінив її на варіант з родини сі. Мені цей варіант менше подобається, як мінімум, через більш складний синтаксис сі, необхідність типізації і описання змінних, більшу кількість «магії» при написанні програм. Те, що на python робиться просто і прозоро, далеко не завжди на сі так само. Мені здається, що python для програмування – чудовий і для початківців найкращий (як ефективно хреститися, хтось знає?).
Саме тому я буду пропонувати собі і своїм учням задачі такого класу розв’язувати алгоритмічно, шукати оптимальне рішення, можливо розв'язок в даних умовах існує. Якщо планувати майбутнє в IT, то готувати голову для пошуку оптимальних розв'язків - дуже перспективно. Ну а якщо частина тестів при всіх оптимізаціях не проходить по часу на e-olymp, то пропоную (плювати слюнями - закреслено) до цього відноситися філософськи.
А для аналізу даної задачі пропоную два підходи. Вони різняться способом отримання суми розрядів числа.
Перший підхід – для тих, хто не шарить в математиці або плутається з div та mod
(звичайно, по таким програмерам плаче ремінь і біржа безробітних, я в курсі).
Можна визначити суму цифр за допомогою list comprehension. При такому підході значення текстової змінної n буде перебиратися посимвольно:
n = input()
sumа_tsyfr = sum([int(x) for x in n])
(до речі, можете спробувати так просто на Сі написати)
Звичайно, для математичних розрахунках нам треба буде конвертувати текст в число, а по звершенню розрахунків, знову повертатися до текстової змінної, бо ми з неї отримуємо суму цифр.
Другий підхід – математичний. Сума цифр числа визначається в python просто і зручно через функцію divmod, Зручно і концептуально правильно оформити підрахунок суми цифр числа в функцію. Ми даній функції передаємо число, функція повертає суму його цифр. Можливо так:
def suma_tsyfr (x):
result = 0
while x > 0:
x, a = divmod(x, 10)
result += a
return result
Окреме питання – обнулення змінної result. Тут це не лише обнулення, а ще і ініціалізація. Якщо другий рядок видалити, програма видасть помилку на рядку result+=a (local variable 'result' referenced before assignment). При цьому я рекомендую в програмах використовувати обнулення змінних. Якщо так звикнути, то нас не будуть цікавити налаштування «по замовчуванню» компіляторів і інтерпретаторів.
Категорія доступна окремим категоріям користувачів.
Лише частина статей може бути доступна гостям сайту.
