Skip to content

Instantly share code, notes, and snippets.

@danbst
Last active Jan 5, 2022
Embed
What would you like to do?

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

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

Ну допустимо у мене є монетки двушки (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. Ось як його опис виглядав в оригіналі

image

Тобто, Пайтон розробники спеціально в Пайтон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)
  1. Двушка
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)
  1. Для чисел виду 10+2, 15+2, 20+2, 25+2, ... також легко порахувати, просто додати одну монетку двушку
print(N//5 + 1)
  1. Так само для 10+4, 15+4, ..., треба додати дві монетки
print(N//5 + 2)
  1. Для чисел 10+1, 15+1, 20+1, ... уже трошки складніше. Доведеться пожертувати однією п'ятішею, і додати 3 двушки
print(N//5 - 1 + 3)
  1. Для останнього випадку, чисел 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 в оригінальній програмі.

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

image Серйозно? 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 Кб використаної пам'яті, що в принципі і є очікуваним результатом.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment