Джерело задачі: Збірник завдань для державної підсумкової атестації з інформатики. Автори: Н.В. Морзе, В.П. Вембер, О.Г. Кузьмінська, М.О. Войцеховський, Т.Г. Проценко. Рекомендовано Міністерством освіти і науки України.  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

 

Спробували? Тоді ще більше десяти варіантів розв'язку )

  

Логіка мого роз’явку полягала в перевірці, чи можна видати суму лише п’ятірками. Якщо можна – видаємо і радіємо. Окремо розглянув варіант, коли N=8. Якщо ж видати суму лише п’ятірками не вдається, тоді беремо максимальну кількість п’ятірок і намагаємо додати двійками. Якщо не виходить, зменшуємо кількість п’ятірок і знову пробуємо доповнити двійками. І так до успіху.

 Таке рішення, хоч і здалось на сайті eolymp.com на 100%, але мені особисто здається важкуватим, а окреме опрацювання N=8 ще і кривуватим )

Тим не менше, як здалося, так і публікую, бо умовою було здати швидко, не покращувати потім нічого. Мій код не найкращий, але ось:

 

n = int(input())

number_5, remainder_5 = divmod(n, 5)

if n == 8:

    print(4)

elif remainder_5 == 0:

    print(number_5)

else:

    for x in range(number_5, 0, -1):

        if (n - x * 5) % 2 == 0:

            print((n - x * 5) // 2 + x)

            break

 

Дуже радію, що відповіді на задачу прийшли від багатьох чудових людей, яких я знаю особисто.

 

Пропоную програми різних авторів, що поділилися кодом. Розв'язки проходять на сайті eolymp.com на 100%:

 

Вікторія:

n = int(input())

k = n // 5

if (n - (k * 5)) % 2 == 0:

    print(int(k + ((n - (k * 5)) / 2)))

else:

    print(int(k - 1 + (n - ((k - 1) * 5)) / 2))

 

 

Коля:

n = int(input())

a = int(n / 5)

if (n - (a * 5)) == 0:

    print(a)

elif (n - (a * 5)) % 2 == 0:

    print('%.0f' % ((n - (a * 5)) / 2 + a))

elif (n - (a * 5)) % 2 != 0:

    a -= 1

    print('%.0f' % ((n - (a * 5)) / 2 + a))

 

Олександр:

n = int(input())

k_5 = n // 5

k_2 = (n - 5 * (k_5)) // 2

while True:

    s = k_5 * 5 + k_2 * 2

    if s != n:

        k_5 -= 1

        k_2 = (n - 5 * (k_5)) // 2

    else:

        break

print(k_5 + k_2)

 

 

Валер’янка:

number = int(input())

d, m = divmod(number, 10)

if m == 0:

    print(2 * d)

elif m == 2 or m == 5:

    print(2 * d + 1)

elif m == 1 or m == 4 or m == 7:

    print(2 * d + 2)

elif m == 3 or m == 6 or m == 9:

    print(2 * d + 3)

elif m == 8:

    print(2 * d + 4)

 

Віталій:

<?PHP

$N = trim(stream_get_contents(STDIN));
$a = array(0, 2, 1, 3, 2);
$b = $N % 5;
$out = intdiv($N, 5) + $a[$b];

echo $out; ?>

 

 

Автор розв'язку — Володимир Заїка:

n = int(input())

x = n // 5

y = n % 5

if y % 2 != 0:

    x = x - 1

    y = y + 5

print(x + int(y / 2))

 

 

Автор розв'язку — Віктор Ковбаса:

 #include <iostream>

 

int main()

{

  long int n,k;

  std::cin>>n;

  k=(n/5)-(((n-(n/5)*5)%2)==1);

  k+=(n-k*5)/2;

  std::cout<<k;

}

 

Автор розв'язку — Василь Корилюк:

n = int(input())

x = n // 5

y = n % 5

z = y % 2

if z == 0:

    print(x + y // 2)

elif z == 1:

    print(x + y // 2 + 2)

 

Як на мене, класний розв’язок. Автор — Олександр Пилипчук:

n = int(input())

x = n // 5 - n % 5 % 2

y = (n - x * 5) // 2

print(x + y)

 

 

Данило Глинський подарував нам не лише кілька класних розв’язків, а і пояснення:

 

Мінімальна кількість купюр

Тут мені підігнали простеньку задачку. Звучить вона так:

Ну допустимо у мене є монетки двушки (2грн) і п'ятішки (5грн). І з них треба зібрати певну суму грн, допустимо, 123 грн. Яка найменша кількість монеток потрібна щоб набрати цю суму?

Ну і потім задачка просить вирішити не тільки для 123 грн, а й для всіх 8 <= N <= 1000000

 

Математики люблять такі задачки

Бо у них є стандартне математичне представлення, лінійне діофантове рівняння:

Задача зводиться до пошуку всіх розв'язків рівняння 2x + 5y = N, підрахунку x+y і пошуку мінімального з них.

Лінійні діофантові рівнняння — це як звичайні рівняння, але з двома змінними. У таких рівнянь нескінченно багато розв'язків, але у нас є ще одне неявне обмеження:

x та y не можуть бути від'ємними, бо це кількості монеток.

 

При чому ж тоді тут Release Notes?

Release Notes — це такий документ, який описує які зміни отримав певний програмний продукт. І так склалось, що я перечитував всі Release Notes для всіх версій Python3 з дуже конкретною метою — взнати, коли змінювався синтаксис мови. Якщо цікаво, то ось як:

• Python 3.1 додав правило, щоб можна було відкривати кілька контекстів в "with .. as"
• Python 3.3 додав конструкцію "yield from"
• Python 3.5 додав конструкції "async/await", оператор для множення матриць і розширив місця, де можна робити unpack/spread ("*", "**")
• Python 3.6 додав нові правила: f-рядки, підкреслення в числах, анотації типів
• Python 3.8 додав морж-оператор ":=" (walrus operarator)
• Python 3.10 додав конструкцію "match .. case .."

Цікаво, еге ж? Але ще цікавим було розширення функції pow. Ось як його опис виглядав в оригіналі

 

 

Тобто, Пайтон розробники спеціально в Пайтон3.8 додали фішку для розв'язку діофантових рівнянь? Вау, прикольно, але навіщо???

Я знаю відповідь "навіщо". Окрім як для діофантових рівнянь, інверсний елемент по модулю використовується ще в криптографії. Конкретно, в криптографії RSA. І якщо мати "з-коробки" цю функцію для інверсного елементу, то стає можливо написати свій шифратор/валідатор RSA в 10 рядочків!

Але я відступив. Так, цей приклад з Release документу якраз підоходить мені для першопочаткової задачі. Просто замінивши числа на свої, я отримую два варіанти (по модулю п'ятіши і по модулю двушки):

 

1. П'ятіша

N = int(input())

x = N * pow(2, -1, 5) % 5   # N*3 % 5 також спрацює, бо pow(2, -1, 5) = 3

y = (2*x - N) // -5

print(x + y)

 

2. Двушка

N = int(input())

x = N * pow(5, -1, 2) % 2   # N % 2 також спрацює, бо pow(5, -1, 2) = 1

y = (5*x - N) // -2

print(x + y)

 

Оскільки перший метод максимізує кількість п'ятіш, то його і виберемо, бо п'ятішами набирати потрібно суму більш вигідно. Неймовірно, але цей код проходить всі тести, а значить 99.99% правильний. По хорошому тут треба було би провести аналіз, чому так вийшло, але є ідея як спростити алгоритм ще більше

 

Спеціалізація алгоритму

Але ж якщо подумати, то алгоритм можна написати більш просто. Якщо ми хочемо максимізувати кількість п'ятіш, то давайте так і зробимо.

1. Для чисел виду 10, 15, 20, 25, 30, ... можна легко порахувати оптимальне рішення

print(N//5)

2. Для чисел виду 10+2, 15+2, 20+2, 25+2, ... також легко порахувати, просто додати одну монетку двушку

print(N//5 + 1)

3. Так само для 10+4, 15+4, ..., треба додати дві монетки

print(N//5 + 2)

4. Для чисел 10+1, 15+1, 20+1, ... уже трошки складніше. Доведеться пожертувати однією п'ятішею, і додати 3 двушки

print(N//5 - 1 + 3)

5. Для останнього випадку, чисел 10+3, 15+3, ... те саме, тільки додавати треба 4 двушки

print(N//5 - 1 + 4)

 

В принципі, цей жадібний алгоритм можна записати як аналіз остачі від ділення на 5:

 

def solve(N):

    if N % 5 == 0:

        return(N//5)

    elif N % 5 == 1:

        return(N//5 + 2)

    elif N % 5 == 2:

        return(N//5 + 1)

    elif N % 5 == 3:

        return(N//5 + 3)

    else:

        return(N//5 + 2)

 

І тут самий час застосувати ... індекси! Оскільки кожна гілка if відрізняється тільки доданком, то можна цей доданок записати в хардкод список, і використовувати остачу від ділення замість індексу!

 

N = int(input())

print(N//5 + [0,2,1,3,2][N%5])

 

Код тепер використовує тільки ділення, остачу і додавання, і це мабуть уже оптимально.

 

Але що це за дічь з індексацією? Ця техніка прийшла з дисципліни Code Golf (написання мінімального коду), і в оригіналі виглядає так:

Q: Як написати код 10 if var > 5 else 32 коротше?

A: [32,10][var>5]

 

Тобто, var>5 повертає True або False, але в Пайтоні True=1, False=0 і їх можна використовувати в усіх місцях де є числа. Подібним способом я і позбувся від if ... elif в оригінальній програмі.

 

Пайтон якось повільно працює

 

 

 Серйозно? 5 Мб пам'яті, 18 мсек часу? Це якось забагато для двух рядків коду. Давайте перепишемо це ж на C

#include "stdio.h"

 

void main() {

   int N;

   scanf("%d", &N)

   int buf[5] = {0, 2, 1, 3, 2};

   printf("%d", buf[N%5] + N/5); 

}

 

Працює! Але чомусь дуже довго, 6 мсек. Топ-лідери в рейтингу виконують завдання за 1 мсек. Виявляється, потрібно використовувати не С компілятор, а С++ компілятор. Схоже, саме він в системі EOlymp найкраще налагоджений на швидкодію.

Цей самий код при запуску на С++ 17 компіляторі видає 1 мсек часу і 72 Кб використаної пам'яті, що в принципі і є очікуваним результатом.

 

 

Ось таким вийшов у нас розв'язок задачі з ДПА. Згадаю разом всіх, хто взяв участь в розв'язку і дозволив використати код для цієї статті: Вікторія, Коля, Олександр, Валер’янка, Віталій, Володимир Заїка, Віктор Ковбаса, Василь Корилюк, Олександр Пилипчук, Данило Глинський. Дякую вам всім за гарну компанію!

 

Ну і питання, яке мене не залишало весь час роботи над задачею:  якщо видати цю задачу усередненому українському одинадцятикласнику, надійно заблокувавши можливість списати, то, на вашу думку, якій відсоток учнів зможуть її будь-яким способом здати?

 

---