Тут мені підігнали простеньку задачку. Звучить вона так:
Ну допустимо у мене є монетки двушки (2грн) і п'ятішки (5грн). І з них треба зібрати певну суму грн, допустимо, 123 грн. Яка найменша кількість монеток потрібна щоб набрати цю суму?
Ну і потім задачка просить вирішити не тільки для 123 грн, а й для всіх 8 <= N <= 1000000
Бо у них є стандартне математичне представлення, лінійне діофантове рівняння:
Задача зводиться до пошуку всіх розв'язків рівняння 2x + 5y = N, підрахунку x+y і пошуку мінімального з них.
Лінійні діофантові рівнняння — це як звичайні рівняння, але з двома змінними. У таких рівнянь нескінченно багато розв'язків, але у нас є ще одне неявне обмеження:
x та y не можуть бути від'ємними, бо це кількості монеток.
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 документу якраз підоходить мені для першопочаткової задачі. Просто замінивши числа на свої, я отримую два варіанти (по модулю п'ятіши і по модулю двушки):
- П'ятіша
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)- Двушка
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% правильний. По хорошому тут треба було би провести аналіз, чому так вийшло, але є ідея як спростити алгоритм ще більше
Але ж якщо подумати, то алгоритм можна написати більш просто. Якщо ми хочемо максимізувати кількість п'ятіш, то давайте так і зробимо.
- Для чисел виду 10, 15, 20, 25, 30, ... можна легко порахувати оптимальне рішення
print(N//5)- Для чисел виду 10+2, 15+2, 20+2, 25+2, ... також легко порахувати, просто додати одну монетку двушку
print(N//5 + 1)- Так само для 10+4, 15+4, ..., треба додати дві монетки
print(N//5 + 2)- Для чисел 10+1, 15+1, 20+1, ... уже трошки складніше. Доведеться пожертувати однією п'ятішею, і додати 3 двушки
print(N//5 - 1 + 3)- Для останнього випадку, чисел 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 Кб використаної пам'яті, що в принципі і є очікуваним результатом.