Неделя 4

Семинар. Рекурсия и бинарный поиск

скачать .ipynb

Семинар 4. Рекурсия и бинарный поиск

Лекция 4 дала рекурсию (репка, матрёшка, фракталы, генерация) и бинарный поиск. На паре сначала короткая разминка на простую рекурсию, потом бинпоиск по полуинтервалу $[l, r)$ на примерах, и только затем контест.

Ноутбук — тетрадь пары. Его семинаристу не отправляйте. Зачёт пары — выполнение обязательных задач № 4 (278) и № 5 (875) из контеста на algo.ai.msu.ru (задачи с LeetCode).

Заглушки печатают неверный ответ — так и задумано, их надо переписать.

Можно спрашивать соседа и семинариста. Готовое решение копировать не стоит: на зачёте рядом никого не будет.

Как устроен ноутбук

Как на семинарах 1–3: ячейки Markdown и Code; командный режим — Esc, правка — Enter; Shift+Enter выполняет ячейку.

Скачайте с сайта курса этот файл .ipynb. Отдельного файла тестов на этой неделе нет: упражнения смотрите по выводу, сдаёте контест на платформе.

Ячейки с комментарием «Ваш эксперимент» никто автоматически не проверяет.

Порядок работы

  1. Разминка: простая рекурсия — база, шаг, глубина.
  2. Почему «пополам» быстро, и мост от рекурсии к поиску.
  3. Полуинтервал $[l, r)$ на примерах.
  4. Массив: lower_bound, upper_bound, диапазон равных.
  5. Шкала без массива: first_true и монотонный предикат.
  6. Поиск по ответу: проверка ok(t), которая сама стоит линейное время.
  7. Контест на algo.ai.msu.ru — две обязательные задачи, разминка и задачи повышенной сложности.

Повтор задач прошлых недель — в конце ноутбука, как запас. Merge sort и quick sort на этой паре не пишем: это семинар 5.

Разминка: простая рекурсия

На лекции рекурсия была на матрёшке и фракталах. Здесь несколько коротких функций, чтобы база и шаг стали привычными.

В каждой задаче проверяйте три вещи:

  • база — случай, который решается без нового вызова;
  • шаг — сведение к меньшему аргументу;
  • уменьшение — параметр обязан двигаться к базе, иначе получите RecursionError.

Обратный отсчёт и прямой

countdown(n) печатает $n, n-1, \ldots, 1$, затем строку Пуск!. countup(n) печатает $1, 2, \ldots, n$. Циклы не используем, только рекурсия.

Две функции отличаются местом печати: до рекурсивного вызова или после него. Это та же разница, что «открываем матрёшку» и «закрываем матрёшку» на лекции.

In [ ]:
def countdown(n):
    """Печатает n, n-1, ..., 1, затем 'Пуск!'; n — целое, n >= 0."""
    print("заглушка")


def countup(n):
    """Печатает 1, 2, ..., n; n — целое, n >= 0."""
    print("заглушка")


countdown(3)  # ожидается 3, 2, 1, Пуск!
print("---")
countup(3)    # ожидается 1, 2, 3

Факториал и сумма цифр

$$F(0)=1,\qquad F(n)=n\cdot F(n-1),\quad n\ge 1.$$

Здесь функция возвращает значение, а не печатает: базовый случай тоже обязан вернуть число.

Затем напишите digit_sum(n): отделите последнюю цифру с помощью n % 10, а сумму остальных найдите рекурсивно для n // 10. Продумайте базу для n = 0.

In [ ]:
def factorial(n):
    """n! по рекуррентной формуле; n — целое, n >= 0."""
    return 0


def digit_sum(n):
    """Сумма десятичных цифр; n — целое, n >= 0. Подсказка: n % 10 и n // 10."""
    return -1


print(factorial(0), factorial(1), factorial(5))  # ожидается 1 1 120
print(digit_sum(0), digit_sum(7), digit_sum(1234))  # ожидается 0 7 10

Глубина рекурсии и число вызовов

Это две разные величины. У countdown(n) каждый вызов делает ровно один вложенный: вызовов $n+1$ и глубина $n+1$ — «палка». Если вызовов два, получается дерево: число вызовов растёт гораздо быстрее, чем глубина.

Посмотрите на числах Фибоначчи: fib(0) = 0, fib(1) = 1, fib(n) = fib(n-1) + fib(n-2). Счётчик уже встроен, вам нужно только тело функции.

In [ ]:
calls = 0


def fib(n):
    """n-е число Фибоначчи; n — целое, n >= 0."""
    global calls
    calls += 1
    return 0


for n in (5, 10, 20):
    calls = 0
    value = fib(n)
    print(f"n={n}: fib={value}, вызовов={calls}")

# ожидается fib(5)=5, fib(10)=55, fib(20)=6765
# глубина при этом всего n: число вызовов и глубина — не одно и то же

Мост к бинпоиску: уменьшать вдвое, а не на единицу

Рекурсия уменьшает аргумент. Если вычитать единицу, шагов будет $n$. Если делить пополам, шагов будет около $\log_2 n$. На этом стоит весь бинарный поиск.

Возведение в степень двумя способами:

$$a^n = a\cdot a^{n-1} \quad\text{— около } n \text{ умножений};$$

$$a^n = \bigl(a^{n/2}\bigr)^2 \text{ при чётном } n, \qquad a^n = a\cdot a^{n-1} \text{ при нечётном} \quad\text{— } O(\log n) \text{ умножений при } n\ge 2.$$

В чётном случае вычислите половинную степень один раз, сохраните результат и умножьте его на себя. Два одинаковых рекурсивных вызова уничтожат выигрыш.

In [ ]:
def power_slow(a, n):
    """a ** n за n умножений; n — целое, n >= 0."""
    return 0


def power_fast(a, n):
    """a ** n делением степени пополам; n — целое, n >= 0."""
    return 0


print(power_slow(2, 10), power_fast(2, 10))  # ожидается 1024 1024
print(power_fast(3, 0), power_fast(3, 1))    # ожидается 1 3
print(power_fast(2, 100) == 2 ** 100)        # ожидается True
In [ ]:
# Ваш эксперимент: добавьте в обе функции счётчик умножений
# и сравните его при n = 100. Во сколько раз разница?
# При n = 1000 медленная версия может превысить лимит глубины рекурсии Python.

Почему «пополам» — это быстро

Линейный просмотр упорядоченного массива из $10^9$ элементов — миллиард сравнений. Деление пополам сводит задачу к десяткам шагов: сосчитайте, сколько раз миллиард делится пополам до единицы.

In [ ]:
n = 10 ** 9
steps = 0
while n > 1:
    n //= 2
    steps += 1

print("шагов деления пополам для 10**9:", steps)
print("линейный проход сделал бы 10**9 сравнений")

Полуинтервал $[l, r)$

На этой неделе один договор, его не меняем.

Держим целые $l$ и $r$, непроверенные значения — $l, l+1, \ldots, r-1$. $l$ входит, $r$ не входит. При этом граница ответа лежит в замкнутом диапазоне $[l, r]$: сам $r$ тоже может быть ответом.

Ищем первый $t$ на шкале, где предикат стал истинным (и дальше не становится ложным):

  • все значения строго левее $l$ — предикат ложен;
  • все значения с $r$ и правее — предикат истинен, либо шкала уже кончилась.

Пока $l < r$:

  • середина $m = (l + r) // 2$ попадает в $[l, r)$;
  • если предикат на $m$ истинен — ответ не правее $m$, поэтому $r = m$;
  • иначе $l = m + 1$.

Когда цикл остановился, $l = r$, и $l$ — первый истинный (если истинных не было, вернётся исходный правый конец).

После каждой итерации полуинтервал строго короче. Если оставить $m$ в диапазоне ($l = m$ при ложном предикате), цикл может не сузиться.

Тот же поиск на двух примерах

$a = [1, 2, 4, 4, 7]$, ищем первый индекс с $a[i] \ge 4$. Шкала — индексы, полуинтервал $[0, 5)$.

Шаг$l$$r$$m$$a[m]$$a[m] \ge 4$Что делаем
10524истина$r = m = 2$
20212ложь$l = m + 1 = 2$
322———$l = r$, стоп

Ответ $l = 2$. При истинном предикате элемент на $m$ остаётся кандидатом ($r = m$, а не $m - 1$); при ложном — выбрасывается ($l = m + 1$).

Теперь тот же массив и $x = 3$, которого в массиве нет:

Шаг$l$$r$$m$$a[m]$$a[m] \ge 3$Что делаем
10524истина$r = 2$
20212ложь$l = 2$
322———стоп

Ответ снова $2$ — это место, куда вставить тройку, чтобы массив остался упорядоченным. Цикл находит место вставки. Чтобы ответить «где ключ», дополнительно проверьте i < len(a) и a[i] == x; иначе ключа нет.

Проследите третий пример сами: $x = 8$ на том же массиве. Ответ должен получиться $5$, то есть за концом.

Массив: lower_bound и upper_bound

Неубывающий массив — частный случай шкалы: предикат на середине — это сравнение a[m] >= x.

  • lower_bound — первый индекс с $a[i] \ge x$. Если все элементы меньше $x$, ответ $n$.
  • upper_bound — первый индекс с $a[i] > x$.

Равные $x$ занимают полуинтервал $[\texttt{lower\_bound}, \texttt{upper\_bound})$, а их количество — разность концов. Пустой массив: $[0, 0)$, цикл сразу останавливается, ответ $0$.

In [ ]:
def lower_bound(a, x):
    """Первый индекс i с a[i] >= x; если такого нет — len(a)."""
    return -1


print(lower_bound([1, 2, 4, 4, 7], 4))  # ожидается 2
print(lower_bound([1, 2, 4, 4, 7], 3))  # ожидается 2
print(lower_bound([1, 2, 4, 4, 7], 8))  # ожидается 5
print(lower_bound([7, 7, 7], 7))        # ожидается 0
print(lower_bound([], 1))               # ожидается 0
In [ ]:
def upper_bound(a, x):
    """Первый индекс i с a[i] > x; если такого нет — len(a)."""
    return -1


def equal_range(a, x):
    """Полуинтервал (первый равный, за последним равным)."""
    return (-1, -1)


print(upper_bound([1, 2, 4, 4, 7], 4))  # ожидается 4
print(upper_bound([1, 2, 4, 4, 7], 7))  # ожидается 5
print(equal_range([1, 2, 4, 4, 7], 4))  # ожидается (2, 4): две четвёрки
print(equal_range([1, 2, 4, 4, 7], 3))  # ожидается (2, 2): равных нет
In [ ]:
# Ваш эксперимент: все элементы больше x; массив из одного элемента;
# ключ меньше всех. Что должен вернуть каждый из двух поисков?

Когда цикл не сужается

Нарочно оставим $m$ в диапазоне при ложном предикате. Ограничьте число итераций, иначе ячейка зависнет.

In [ ]:
def stuck_lower_bound(a, x, max_steps=20):
    l, r = 0, len(a)
    for step in range(max_steps):
        if l >= r:
            return l
        m = (l + r) // 2
        print(f"шаг {step}: l={l}, r={r}, m={m}")
        if a[m] >= x:
            r = m
        else:
            l = m  # ошибка: должно быть m + 1
    print("полуинтервал не сжался")
    return None


stuck_lower_bound([1, 2, 4, 4, 7], 4)

Шкала без массива: first_true

В lower_bound предикат — это a[m] >= x. Но самому циклу неважно, откуда берётся ответ «да / нет». Вынесем предикат в функцию ok(t) — получится универсальный first_true, который ищет первое True на шкале $[l, r)$.

Так решают задачи, где массива значений нет вообще: есть только «уже можно / ещё нельзя» при данном $t$. Договоримся: если истинных нет, ответ равен исходному $r$.

In [ ]:
def first_true(ok, l, r):
    """Первый t в [l, r), где ok(t) истинно; если таких нет — вернуть r."""
    return -1


print(first_true(lambda t: t >= 4, 0, 10))  # ожидается 4
print(first_true(lambda t: t >= 0, 0, 5))   # ожидается 0
print(first_true(lambda t: False, 0, 5))    # ожидается 5

Медленный эталон для сверки

Пока свой цикл не отлажен, держите рядом заведомо правильную, но медленную версию: перебрать все $t$ слева направо. На контесте она получит TLE, а для сверки на маленькой шкале годится.

In [ ]:
import random


def first_true_slow(ok, l, r):
    """Перебор всех t: медленно, зато очевидно правильно."""
    for t in range(l, r):
        if ok(t):
            return t
    return r


for _ in range(5):
    threshold = random.randint(0, 25)
    ok = lambda t: t >= threshold
    fast, slow = first_true(ok, 0, 20), first_true_slow(ok, 0, 20)
    print(f"порог {threshold:2}: быстро {fast:2}, медленно {slow:2}", "ok" if fast == slow else "РАСХОЖДЕНИЕ")

Предикат обязан быть монотонным: один переход с «ещё нельзя» на «уже можно». Если в середине дырка, тот же цикл имеет право соврать.

In [ ]:
def not_monotonic(t):
    return t in (2, 5)


# Запустите после того, как напишете first_true.
print(first_true(not_monotonic, 0, 8))
print([not_monotonic(t) for t in range(8)])
# цикл ищет «первый истинный на монотонной шкале» — здесь шкалы такой нет

Поиск по ответу

Шкала — не индексы, а сами возможные ответы: скорость, вместимость, длина, порог. Схема из двух шагов:

  1. написать ok(t) — «при этом $t$ уже получается?»;
  2. пустить first_true по шкале $t$.

Почти вся работа — в ok. Начнём с разминки, где ok дешёвый: целый квадратный корень.

Максимальное целое $x \ge 0$ с $x^2 \le n$. Предикат «$t^2 > n$» ложен на префиксе шкалы и истинен после; первый такой $t$ минус единица — ответ. Правый конец берите заведомо истинным: подойдёт $[0, n+2)$. Никаких sqrt и float — на больших числах вещественная арифметика врёт.

In [ ]:
def isqrt(n):
    # максимальное x >= 0 с x * x <= n; полуинтервал [l, r)
    return -1


print(isqrt(0))   # ожидается 0
print(isqrt(1))   # ожидается 1
print(isqrt(8))   # ожидается 2
print(isqrt(9))   # ожидается 3
print(isqrt(10))  # ожидается 3

Когда одна проверка стоит линейное время

Дальше ok(t) сам проходит по входу. Два типовых вида проверки:

  1. Сумма с округлением вверх. Кучки размеров $a_i$, скорость $v$ за час, за час берут только одну кучку: нужно $\sum_i \lceil a_i / v \rceil$ часов. Округление вверх целыми числами — (x + v - 1) // v, без math.ceil.
  2. Жадное разрезание. Идём слева направо и набираем подряд идущие элементы, пока сумма не превышает cap; как только очередной не влезает — начинаем новую часть. Результат — минимальное число частей. Здесь элементы положительные, массив непустой и cap >= max(a). Объясните, почему максимально длинная допустимая первая часть не увеличивает необходимое число частей.

Обе проверки монотонны: если справились при $t$, то справимся и при любом большем $t$. Проговорите это, прежде чем писать цикл: на неверной монотонности бинпоиск молча врёт.

Стоимость: одна проверка $O(n)$, проверок $O(\log M)$, где $M$ — число значений на шкале поиска ($M \ge 2$). Всего $O(n \log M)$. Линейный перебор всех $t$ вместо бинпоиска — типичный TLE.

In [ ]:
def hours_needed(piles, v):
    """Сколько часов уйдёт на кучки piles при скорости v > 0 (одна кучка за раз)."""
    return -1


def parts_needed(a, cap):
    """Минимум частей с суммой <= cap; a непустой, элементы > 0, cap >= max(a)."""
    return -1


print(hours_needed([3, 6, 7, 11], 4))    # ожидается 8 = 1 + 2 + 2 + 3
print(hours_needed([3, 6, 7, 11], 11))   # ожидается 4 — по часу на кучку
print(parts_needed([1, 2, 3, 4, 5], 5))  # ожидается 4: [1,2] [3] [4] [5]
print(parts_needed([1, 2, 3, 4, 5], 15)) # ожидается 1
In [ ]:
# Соберите поиск по ответу из своих first_true и hours_needed:
# минимальная целая скорость, при которой хватает h часов.
piles = [3, 6, 7, 11]
h = 8

print(first_true(lambda v: hours_needed(piles, v) <= h, 1, max(piles) + 1))  # ожидается 4

# Ваш эксперимент: то же для parts_needed — минимальная вместимость,
# при которой частей не больше заданного числа. Где начинается шкала?

Повышенная сложность: поиск пика

Это упражнение к необязательной задаче № 7 (162). Его можно оставить до выполнения обязательных задач контеста.

В непустом массиве, где соседи не равны, найдите любой локальный максимум: элемент больше обоих соседей; за краями считаем $-\infty$.

Здесь другое обоснование деления пополам: сравнение $a[m] > a[m+1]$ не обязано быть монотонным. Например, для [1, 3, 2, 4, 1] результаты сравнений соседей — False, True, False, True. Готовый first_true к этому предикату применять нельзя.

Для отдельного цикла поддерживаем непустой полуинтервал $[l, r)$ и инвариант: на его левой границе подъём ($a[l] > a[l-1]$), на правой — спуск ($a[r-1] > a[r]$), с условными $-\infty$ за краями массива. Поэтому внутри есть пик. Пока элементов больше одного, выбираем $m$ так, чтобы и $m$, и $m+1$ лежали внутри диапазона. При спуске оставляем $[l, m+1)$, при подъёме — $[m+1, r)$. Объясните, почему инвариант сохраняется.

Сначала обоснуйте существование пика, затем напишите цикл. Это поиск половины, содержащей ответ, а не поиск первого истинного монотонного предиката.

In [ ]:
def find_peak(a):
    """Индекс любого локального максимума; соседи не равны, за краями -inf."""
    return -1


print(find_peak([1, 2, 3, 1]))           # ожидается 2
print(find_peak([1, 2, 1, 3, 5, 6, 4]))  # ожидается 1 или 5
print(find_peak([5]))                    # ожидается 0
print(find_peak([1, 2]))                 # ожидается 1

Контест: что обязательно, а что по желанию

Задачи сдавайте в контест «Бинарный поиск» на algo.ai.msu.ru. Номера ниже соответствуют списку из семи задач; номера LeetCode помогают найти нужное условие.

Для зачёта семинара обязательны № 4 (278. First Bad Version) и № 5 (875. Koko Eating Bananas). Разминка и задачи повышенной сложности не обязательны и не заменяют эти две задачи.

№ЗадачаСтатус на семинареЧто из ноутбука
1704. Binary SearchРазминка, по необходимостиlower_bound, затем проверка границы массива и равенства ключу
235. Search Insert PositionРазминка, по необходимостиlower_bound
334. Find First and Last Position of Element in Sorted ArrayПовышенная сложность, по желаниюДве границы; последний равный — upper_bound - 1; если ключа нет, вернуть [-1, -1]
4278. First Bad VersionОбязательнаяfirst_true, где ok — готовая функция isBadVersion
5875. Koko Eating BananasОбязательнаяhours_needed и поиск минимальной скорости
61011. Capacity To Ship Packages Within D DaysПовышенная сложность, по желаниюparts_needed, обоснование жадной проверки и поиск минимальной вместимости
7162. Find Peak ElementПовышенная сложность ★, по желаниюОтдельный инвариант: выбранная половина содержит пик; предикат на соседях не монотонен

Категории обозначают роль задач на этом занятии, а не рейтинг Easy / Medium на LeetCode.

Порядок работы: если нужно закрепить поиск в массиве, начните с № 1 или № 2. Если цикл уже получается, переходите сразу к № 4, затем № 5. После обязательных выбирайте № 3 или № 6; № 7 требует отдельного рассуждения. Решать все семь задач за пару не требуется. Недорешённые обязательные задачи завершите в том же контесте после занятия; остальные — по желанию.

Типичный WA: l = m вместо m + 1; перепутали первый допустимый и последний недопустимый ответ; перевёрнутый предикат; диапазон не охватывает нужный ответ; float и sqrt вместо точной целочисленной проверки. В нашем first_true после остановки l == r, поэтому вернуть l или r — одно и то же.

Типичный TLE: перебор всех значений ответа вместо бинпоиска; вложенные проходы по входу внутри ok(t). Один линейный проход при каждой проверке в задачах № 5 и № 6 — нормальная часть решения.

Шпаргалка

Рекурсия:

  • база без нового вызова, шаг к меньшему аргументу, параметр двигается к базе;
  • печать до вызова и после вызова дают разный порядок вывода;
  • глубина и число вызовов — разные величины; два вызова на шаг дают дерево;
  • уменьшать вдвое вместо единицы — это $\log_2 n$ шагов вместо $n$.

Бинпоиск:

  • полуинтервал $[l, r)$: $l$ входит, $r$ нет. Цикл while l < r;
  • предикат истинен на $m$ → $r = m$; иначе $l = m + 1$; ответ — $l$;
  • шкала — индексы массива или значения ответа $t$;
  • для first_true предикат должен быть монотонным; поиск пика — отдельный алгоритм с инвариантом существования пика в выбранном диапазоне;
  • сначала ok(t), потом цикл; считайте, сколько стоит одна проверка;
  • bisect в жизни удобен; на паре цель — свой цикл.

Сдача

  • Этот .ipynb семинаристу отправлять не нужно.
  • Для зачёта выполните № 4 — 278. First Bad Version и № 5 — 875. Koko Eating Bananas в контесте на algo.ai.msu.ru.
  • № 1–2 — разминка, № 3, 6 и 7 — повышенная сложность: выполняются по желанию, для зачёта не требуются.
  • Если обязательные задачи не закончены на паре, дорешайте их в том же контесте после занятия.
  • Домашнее задание к лекции 4, если появится отдельным слотом, — не этот ноутбук.

Запас: повтор прошлых недель

Этот блок разбираем, только если контест пошёл быстро или группа просит. Эталоны не копируем: идея и крайний случай, код дописываем вместе с залом.

Домашку семинара 3 на паре не разбираем: дедлайн ещё не вышел. С семинара 3 — только то, что уже было на паре.

Семинар 2. Пара с ближайшей суммой

Массив уже неубывает. Нужна сумма двух элементов с разными индексами, ближайшая к заданному $S$. Если таких сумм несколько — любая из лучших. На $n \sim 10^5$ двойной цикл не успеет.

Край: отрицательные числа; две разные суммы на одном расстоянии до $S$.

In [ ]:
def closest_pair_sum(a, s):
    # a уже неубывает
    return 0


print(closest_pair_sum([2, 7, 11, 15], 9))   # ожидается 9
print(closest_pair_sum([2, 7, 11, 15], 18))  # ожидается 18
print(closest_pair_sum([-10, 0, 0, 10], 0))  # ожидается 0

Семинар 2. Максимальная сумма пары на расстоянии

Даны $a$ и $K$. Среди пар с разницей индексов не меньше $K$ найдите наибольшую сумму. Числа могут быть отрицательными. Два вложенных цикла на большом $n$ не живут.

Край: все отрицательные; $K = 1$ (подходит любая пара с разными индексами).

In [ ]:
def max_pair_sum_distance(a, k):
    return 0


print(max_pair_sum_distance([5, 2, -1, 0, 3], 2))   # ожидается 8: 5 + 3, расстояние между индексами 4 >= 2
print(max_pair_sum_distance([1, 100, -50, 2, 3, -7], 3))  # ожидается 103
print(max_pair_sum_distance([-1, -2, -3, -4], 1))    # ожидается -3

Семинар 3. Пары (ключ, нагрузка)

Упорядочить пары $(k, p)$ по неубыванию только ключа $k$. При равных ключах относительный порядок пар как во входе. Если сравнить пару целиком, нагрузка $p$ может переставить равные ключи.

Это не бинпоиск. Разбираем, потому что на той паре на этом часто ломались, а домашку недели 3 ещё рано вскрывать.

In [ ]:
def stable_by_key(pairs):
    # pairs — список кортежей (k, p)
    return pairs


print(stable_by_key([(2, 9), (1, 5), (2, 3)]))
# ожидается [(1, 5), (2, 9), (2, 3)] — при ключе 2 сначала 9, потом 3

Семинар 3. Ключи из малого диапазона

Массив целых из $0..1000$, длина до $10^5$ и больше. Выписать в неубывающем порядке. Квадратичная сортировка получит TLE.

Индекс массива снова может значить значение, не позицию — как частоты на семинаре 2.

Мост к сегодняшней теме: если бы диапазон значений был большим, функция $F(t) = \#\{a_i \le t\}$ неубывает по $t$. Первый $t$ с $F(t) \ge k$ ищут тем же бинпоиском по функции, не проходом по всем $t$. Это уже не условие той задачи, а задел.

In [ ]:
def counting_sort(a):
    # 0 <= a[i] <= 1000
    return a


print(counting_sort([3, 1, 3, 2, 1, 3]))  # ожидается [1, 1, 2, 3, 3, 3]
print(counting_sort([7, 7, 7]))            # ожидается [7, 7, 7]