Ця задача відкриває книгу «Олімпіадна інформатика» В.Л.Дідковського і С.В.Матвійчука 2010 року. Умова:
Нумерація
https://www.e-olymp.com/uk/problems/109
Для нумерації m сторінок в книжці використано n цифр. По заданому n вивести m або 0, якщо розв’язку не існує. Нумерація починається з першої сторінки.
Вхідні дані
Єдине число n. У книзі не більше 7000 сторінок.
Вихідні дані
Вивести кількість сторінок у книзі.
Приклад вхідних даних:
27
Приклад вихідних даних:
18
Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Автор: Сергій Матвійчук
Джерело: ІІ етап Всеукраїнської олімпіади в Житомирській області (2003)
Олімпіадне програмування відбувається у вкрай обмеженому проміжку часу. Але у нас зараз не олімпіада, тому пропоную підходити до задачі не поспішаючи, намагаючись підготувати її розв’язок як для співбесіди щодо прийняття на роботу.
Розберемо умову задачі. Перша сторінка нумерується цифрою один. Нам навіть не принципово якою саме, нам важливо, що ця цифра одна. Отже, для книжки з 1 сторінки використовується одна цифра, для книжки з двох сторінок використовується дві цифри, якщо конкретно це 1 і 2. Для книжки з 10 сторінок використовується 11 цифр, а саме: 1 2 3 4 5 6 7 8 9 1 0. У нашому тестовому прикладі, для книги з 18 сторінок використовується 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. Нашою задачею є визначити кількість сторінок по числу цифр.
Може бути ситуація, коли по числу цифр визначити кількість сторінок неможливо. Наприклад, якщо кількість цифр у нумерації сторінок – 26.
Очевидно, якщо номер сторінки однорозрядний (від 1 до 9), то і кількість цифр, що потрібні для нумерації кожної такої сторінки – одна. При нумерації дворозрядних номерів сторінок (від 10 до 99), для нумерації кожної сторінки потрібні дві цифри і т. д. Кількість цифр, необхідних для нумерації сторінки змінюється, коли номер сторінки змінює розрядність, стає 10, 100, 1000. Тобто, 10x.
Задачу можна розв’язати за допомогою циклу. Будемо збільшувати номер сторінки і зберігати кількість цифр для нумерації поточної сторінки і загальну кількість цифр для нумерації всіх сторінок книги. Завершуємо цикл, коли кількість цифр для нумерування книги дорівнює або перевищує ту, що ми отримали на початку програми у вигляді вхідних даних. При рівності цих змінних необхідно вивести кількість сторінок, інакше — розв’язків не існує і виводимо нуль.
Далі розглянемо класичну цитату Роберта Мартіна з його класичної книги «Чистий код»:
Ім'я змінної, функції або класу має відповідати на всі головні питання. Воно повинно повідомити, чому ця змінна (і т. д.) існує, що вона робить і як використовується. Якщо ім'я вимагає додаткових коментарів, то воно не передає намірів програміста.
int d; // Минулий час
Ім'я d не передає абсолютно нічого. Воно не асоціюється ні з часовими інтервалами, ні з днями. Його слід замінити іншим ім'ям, яке буде вказувати, що саме вимірюється і в яких одиницях:
int elapsedTimeInDays;
int daysSinceCreation;
int daysSinceModification;
int fileAgeInDays;
Змістовні імена істотно спрощують розуміння і модифікацію коду (кінець цитати).
Якщо проходити співбесіду в місця з цікавими зарплатами, то існує висока вірогідність, що там книги Мартіна читали. Тим більше варто прислухатися.
Визначимо простір імен змінних у стилістиці Python:
input_sum_digits - (вхідна сума цифр) - кількість цифр, з яких складається книжка, вхідні дані
sum_digits (сума цифр) – змінна, в якій ми будемо накопичувати суму і порівнювати з input_sum_ digits для завершення роботи циклу
current_page_number (номер поточної сторінки) – в змінній зберігатиметься номер сторінки, що опрацьовується при поточній ітерації циклу
number_of_digits_on_current_page (кількість цифр на поточній сторінці) – очевидна величина.
Код з використанням змістовних імен достатньо зрозумілий:
input_sum_digits = int(input())
sum_digits = 0
current_page_number = 0
number_of_digits_on_current_page = 1
while sum_digits < input_sum_digits:
current_page_number += 1;
if current_page_number == (10 ** number_of_digits_on_current_page):
number_of_digits_on_current_page += 1
sum_digits += number_of_digits_on_current_page
if sum_digits == input_sum_digits:
print(current_page_number)
else:
print(0)
Ось усе це у стилістиці c#:
using System;
namespace MyApp
{
class Program
{
static void Main(string[] args)
{
int sumDigits = 0;
int currentPageNumber = 0;
int numberOfDigitsOnCurrentPage = 1;
int inputSumDigits = int.Parse(Console.ReadLine());
while (sumDigits < inputSumDigits)
{
currentPageNumber++;
if (currentPageNumber == Math.Pow(10, numberOfDigitsOnCurrentPage))
{
numberOfDigitsOnCurrentPage++;
}
sumDigits += numberOfDigitsOnCurrentPage;
}
if (sumDigits == inputSumDigits)
{
Console.WriteLine(currentPageNumber);
}
else
{
Console.WriteLine(0);
}
}
}
}
Погодьтесь, використання змістовних імен значно спрошує розуміння коду і для самого себе. Уявіть, що ви повернетеся до вашого коду розміром з сотню рядків через рік. Вам спростить розуміння коду використання змістовних імен? А тепер уявіть іншу ситуацію, коли вам треба на фоні дедлайну модифікувати сотні рядків чужого спагетті-коду, створеного з використанням неочевидних імен змінних, класів, методів. Як вам? Нікому не подобається, тож і ви так не пишіть )
В наші чудові часи шедеври поряд. Інтернет не замінить всіх відчуттів, але тепер можна, наприклад, не їдучі до Музею сучасного мистецтва в Нью-Йорку роздивитися чудо.
Але шедеври трапляються не лише у живопису. Сьогодні хочу представити чудовий розв’язок задачі. Умова:
Задача «Бочка»
(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
|
1
|
2
|
3
|
4
|
|
результат
|
1
|
5
|
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))
