На дошці виписані числа від 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.

А можливо, ви знайдете своє рішення?

Фотка не просто так :)

Успіхів!

Скільки можна?

(https://www.e-olymp.com/uk/problems/20)

Дано натуральне число n. Від даного числа віднімемо суму цифр цього числа, від утвореного числа знову віднімемо суму цифр утвореного числа і т. д. Дану операцію над числом будемо виконувати, поки утворене число додатне. Скільки разів будемо виконувати дану операцію.

Вхідні дані

Одне натуральне число n, що не перевищує 2 *10⁹.

Вихідні дані

Кількість виконаних операцій.

Ліміт часу 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). При цьому я рекомендую в програмах використовувати обнулення змінних. Якщо так звикнути, то нас не будуть цікавити налаштування «по замовчуванню» компіляторів і інтерпретаторів.