Час, коли всі школярі України вчили 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)