Джерело задачі: Збірник завдань для державної підсумкової атестації з інформатики. Автори: Н.В. Морзе, В.П. Вембер, О.Г. Кузьмінська, М.О. Войцеховський, Т.Г. Проценко. Рекомендовано Міністерством освіти і науки України. 2011 рік. 11 клас.
Варіант 7. Завдання 16: запишіть програму відомою вам мовою програмування. Вхідні дані вводяться з клавіатури, а вихідні дані виводяться на екран монітора.
Умова:
Дано натуральне число N (8 ≤ N ≤ 1000000), яке визначає будь-яку цілочислову грошову суму ≤ 1000000. Відомо, що цілочислову грошову суму, більшу чи рівну 7 грошовим одиницям, можна видати лише купюрами номіналом у 2 та 5 грошових одиниць. Визначте, якою кількістю купюр у 2 та 5 грошових одиниць можна видати суму в N грошових одиниць, щоб їхня загальна кількість була найменшою.
Кожен бажаючий може зімітувати собі ДПА в 11 класі, для цього достатньо зайти за посиланням на сайт eolymp.com і в швидкому режимі спробувати здати цю задачу однією з наступних мов програмування: С, С++, С#, D, Dart, Go, Haskel, Java, Javascript, Cotlin, Lua, MySQL, Pascal, Perl, PHP, Python, Ruby, Rust. Для роботи на сайті необхідно зареєструватися і підтвердити email. Все безкоштовно.
Давайте спробуємо розв’язати, нехай, за тридцять хвилин, добре? Відмітьте час початку, старт!
Посилання: https://www.eolymp.com/uk/problems/2033
Спробували? Тоді ще більше десяти варіантів розв'язку )
Ця задача відкриває книгу «Олімпіадна інформатика» В.Л.Дідковського і С.В.Матвійчука 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-лекції».
Мабуть, якщо йти вчитися, то на правильну спеціальність правильного університету. Тому що в такому місці за допомогою самоосвіти і викладачів можна системно і послідовно навчитися серйозним речам.
Де замість циклу використовують формулу. Згадують її або виводять з голови. Там, де неоптимально – це погано, і внутрішня освіта за таке сварить. Де олімпіадний принцип «здати у відведений час» - це недостатньо. Тому що і на співбесідах і на роботі — інші критерії.
Можливо, гарна вища айтішна освіта – це коли в голові не розкидані сторінки різних класних книжок, а більш-менш серйозна бібліотека?
Як Ви вважаєте?