{
  "cells": [
    {
      "cell_type": "markdown",
      "id": "intro",
      "metadata": {},
      "source": [
        "# Семинар 4. Рекурсия и бинарный поиск\n",
        "\n",
        "Лекция 4 дала рекурсию (репка, матрёшка, фракталы, генерация) и бинарный поиск. На паре сначала короткая разминка на простую рекурсию, потом бинпоиск по **полуинтервалу** $[l, r)$ на примерах, и только затем контест.\n",
        "\n",
        "Ноутбук — тетрадь пары. **Его семинаристу не отправляйте.** Зачёт пары — выполнение обязательных задач № 4 (278) и № 5 (875) из контеста на [algo.ai.msu.ru](https://algo.ai.msu.ru) (задачи с LeetCode).\n",
        "\n",
        "Заглушки печатают неверный ответ — так и задумано, их надо переписать.\n",
        "\n",
        "Можно спрашивать соседа и семинариста. Готовое решение копировать не стоит: на зачёте рядом никого не будет."
      ]
    },
    {
      "cell_type": "markdown",
      "id": "jupyter",
      "metadata": {},
      "source": [
        "## Как устроен ноутбук\n",
        "\n",
        "Как на семинарах 1–3: ячейки **Markdown** и **Code**; командный режим — `Esc`, правка — `Enter`; `Shift+Enter` выполняет ячейку.\n",
        "\n",
        "Скачайте с сайта курса [этот файл `.ipynb`](https://learn.ai.msu.ru/algo/1/04/seminar.ipynb). Отдельного файла тестов на этой неделе нет: упражнения смотрите по выводу, сдаёте контест на платформе.\n",
        "\n",
        "Ячейки с комментарием «Ваш эксперимент» никто автоматически не проверяет."
      ]
    },
    {
      "cell_type": "markdown",
      "id": "roadmap",
      "metadata": {},
      "source": [
        "## Порядок работы\n",
        "\n",
        "1. Разминка: простая рекурсия — база, шаг, глубина.\n",
        "2. Почему «пополам» быстро, и мост от рекурсии к поиску.\n",
        "3. Полуинтервал $[l, r)$ на примерах.\n",
        "4. Массив: `lower_bound`, `upper_bound`, диапазон равных.\n",
        "5. Шкала без массива: `first_true` и монотонный предикат.\n",
        "6. Поиск по ответу: проверка `ok(t)`, которая сама стоит линейное время.\n",
        "7. Контест на [algo.ai.msu.ru](https://algo.ai.msu.ru) — две обязательные задачи, разминка и задачи повышенной сложности.\n",
        "\n",
        "Повтор задач прошлых недель — в конце ноутбука, как запас. Merge sort и quick sort на этой паре не пишем: это семинар 5."
      ]
    },
    {
      "cell_type": "markdown",
      "id": "rec_md",
      "metadata": {},
      "source": [
        "## Разминка: простая рекурсия\n",
        "\n",
        "На лекции рекурсия была на матрёшке и фракталах. Здесь несколько коротких функций, чтобы база и шаг стали привычными.\n",
        "\n",
        "В каждой задаче проверяйте три вещи:\n",
        "\n",
        "- **база** — случай, который решается без нового вызова;\n",
        "- **шаг** — сведение к меньшему аргументу;\n",
        "- **уменьшение** — параметр обязан двигаться к базе, иначе получите `RecursionError`."
      ]
    },
    {
      "cell_type": "markdown",
      "id": "rec_count_md",
      "metadata": {},
      "source": [
        "### Обратный отсчёт и прямой\n",
        "\n",
        "`countdown(n)` печатает $n, n-1, \\ldots, 1$, затем строку `Пуск!`. `countup(n)` печатает $1, 2, \\ldots, n$. Циклы не используем, только рекурсия.\n",
        "\n",
        "Две функции отличаются **местом** печати: до рекурсивного вызова или после него. Это та же разница, что «открываем матрёшку» и «закрываем матрёшку» на лекции."
      ]
    },
    {
      "cell_type": "code",
      "id": "rec_count_code",
      "metadata": {},
      "execution_count": null,
      "outputs": [],
      "source": [
        "def countdown(n):\n",
        "    \"\"\"Печатает n, n-1, ..., 1, затем 'Пуск!'; n — целое, n >= 0.\"\"\"\n",
        "    print(\"заглушка\")\n",
        "\n",
        "\n",
        "def countup(n):\n",
        "    \"\"\"Печатает 1, 2, ..., n; n — целое, n >= 0.\"\"\"\n",
        "    print(\"заглушка\")\n",
        "\n",
        "\n",
        "countdown(3)  # ожидается 3, 2, 1, Пуск!\n",
        "print(\"---\")\n",
        "countup(3)    # ожидается 1, 2, 3"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "rec_fact_md",
      "metadata": {},
      "source": [
        "### Факториал и сумма цифр\n",
        "\n",
        "$$F(0)=1,\\qquad F(n)=n\\cdot F(n-1),\\quad n\\ge 1.$$\n",
        "\n",
        "Здесь функция **возвращает** значение, а не печатает: базовый случай тоже обязан вернуть число.\n",
        "\n",
        "Затем напишите `digit_sum(n)`: отделите последнюю цифру с помощью `n % 10`, а сумму остальных найдите рекурсивно для `n // 10`. Продумайте базу для `n = 0`."
      ]
    },
    {
      "cell_type": "code",
      "id": "rec_fact_code",
      "metadata": {},
      "execution_count": null,
      "outputs": [],
      "source": [
        "def factorial(n):\n",
        "    \"\"\"n! по рекуррентной формуле; n — целое, n >= 0.\"\"\"\n",
        "    return 0\n",
        "\n",
        "\n",
        "def digit_sum(n):\n",
        "    \"\"\"Сумма десятичных цифр; n — целое, n >= 0. Подсказка: n % 10 и n // 10.\"\"\"\n",
        "    return -1\n",
        "\n",
        "\n",
        "print(factorial(0), factorial(1), factorial(5))  # ожидается 1 1 120\n",
        "print(digit_sum(0), digit_sum(7), digit_sum(1234))  # ожидается 0 7 10"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "rec_depth_md",
      "metadata": {},
      "source": [
        "### Глубина рекурсии и число вызовов\n",
        "\n",
        "Это две разные величины. У `countdown(n)` каждый вызов делает ровно один вложенный: вызовов $n+1$ и глубина $n+1$ — «палка». Если вызовов два, получается **дерево**: число вызовов растёт гораздо быстрее, чем глубина.\n",
        "\n",
        "Посмотрите на числах Фибоначчи: `fib(0) = 0`, `fib(1) = 1`, `fib(n) = fib(n-1) + fib(n-2)`. Счётчик уже встроен, вам нужно только тело функции."
      ]
    },
    {
      "cell_type": "code",
      "id": "rec_depth_code",
      "metadata": {},
      "execution_count": null,
      "outputs": [],
      "source": [
        "calls = 0\n",
        "\n",
        "\n",
        "def fib(n):\n",
        "    \"\"\"n-е число Фибоначчи; n — целое, n >= 0.\"\"\"\n",
        "    global calls\n",
        "    calls += 1\n",
        "    return 0\n",
        "\n",
        "\n",
        "for n in (5, 10, 20):\n",
        "    calls = 0\n",
        "    value = fib(n)\n",
        "    print(f\"n={n}: fib={value}, вызовов={calls}\")\n",
        "\n",
        "# ожидается fib(5)=5, fib(10)=55, fib(20)=6765\n",
        "# глубина при этом всего n: число вызовов и глубина — не одно и то же"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "rec_pow_md",
      "metadata": {},
      "source": [
        "### Мост к бинпоиску: уменьшать вдвое, а не на единицу\n",
        "\n",
        "Рекурсия уменьшает аргумент. Если вычитать единицу, шагов будет $n$. Если **делить пополам**, шагов будет около $\\log_2 n$. На этом стоит весь бинарный поиск.\n",
        "\n",
        "Возведение в степень двумя способами:\n",
        "\n",
        "$$a^n = a\\cdot a^{n-1} \\quad\\text{— около } n \\text{ умножений};$$\n",
        "\n",
        "$$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.$$\n",
        "\n",
        "В чётном случае вычислите половинную степень один раз, сохраните результат и умножьте его на себя. Два одинаковых рекурсивных вызова уничтожат выигрыш."
      ]
    },
    {
      "cell_type": "code",
      "id": "rec_pow_code",
      "metadata": {},
      "execution_count": null,
      "outputs": [],
      "source": [
        "def power_slow(a, n):\n",
        "    \"\"\"a ** n за n умножений; n — целое, n >= 0.\"\"\"\n",
        "    return 0\n",
        "\n",
        "\n",
        "def power_fast(a, n):\n",
        "    \"\"\"a ** n делением степени пополам; n — целое, n >= 0.\"\"\"\n",
        "    return 0\n",
        "\n",
        "\n",
        "print(power_slow(2, 10), power_fast(2, 10))  # ожидается 1024 1024\n",
        "print(power_fast(3, 0), power_fast(3, 1))    # ожидается 1 3\n",
        "print(power_fast(2, 100) == 2 ** 100)        # ожидается True"
      ]
    },
    {
      "cell_type": "code",
      "id": "rec_exp",
      "metadata": {},
      "execution_count": null,
      "outputs": [],
      "source": [
        "# Ваш эксперимент: добавьте в обе функции счётчик умножений\n",
        "# и сравните его при n = 100. Во сколько раз разница?\n",
        "# При n = 1000 медленная версия может превысить лимит глубины рекурсии Python."
      ]
    },
    {
      "cell_type": "markdown",
      "id": "why_md",
      "metadata": {},
      "source": [
        "## Почему «пополам» — это быстро\n",
        "\n",
        "Линейный просмотр упорядоченного массива из $10^9$ элементов — миллиард сравнений. Деление пополам сводит задачу к десяткам шагов: сосчитайте, сколько раз миллиард делится пополам до единицы."
      ]
    },
    {
      "cell_type": "code",
      "id": "why_code",
      "metadata": {},
      "execution_count": null,
      "outputs": [],
      "source": [
        "n = 10 ** 9\n",
        "steps = 0\n",
        "while n > 1:\n",
        "    n //= 2\n",
        "    steps += 1\n",
        "\n",
        "print(\"шагов деления пополам для 10**9:\", steps)\n",
        "print(\"линейный проход сделал бы 10**9 сравнений\")"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "halfopen",
      "metadata": {},
      "source": [
        "## Полуинтервал $[l, r)$\n",
        "\n",
        "На этой неделе один договор, его не меняем.\n",
        "\n",
        "Держим целые $l$ и $r$, непроверенные значения — $l, l+1, \\ldots, r-1$. **$l$ входит, $r$ не входит.** При этом граница ответа лежит в замкнутом диапазоне $[l, r]$: сам $r$ тоже может быть ответом.\n",
        "\n",
        "Ищем **первый** $t$ на шкале, где предикат стал истинным (и дальше не становится ложным):\n",
        "\n",
        "- все значения строго левее $l$ — предикат ложен;\n",
        "- все значения с $r$ и правее — предикат истинен, либо шкала уже кончилась.\n",
        "\n",
        "Пока $l < r$:\n",
        "\n",
        "- середина $m = (l + r) // 2$ попадает в $[l, r)$;\n",
        "- если предикат на $m$ истинен — ответ не правее $m$, поэтому $r = m$;\n",
        "- иначе $l = m + 1$.\n",
        "\n",
        "Когда цикл остановился, $l = r$, и $l$ — первый истинный (если истинных не было, вернётся исходный правый конец).\n",
        "\n",
        "После каждой итерации полуинтервал **строго короче**. Если оставить $m$ в диапазоне ($l = m$ при ложном предикате), цикл может не сузиться."
      ]
    },
    {
      "cell_type": "markdown",
      "id": "trace_md",
      "metadata": {},
      "source": [
        "### Тот же поиск на двух примерах\n",
        "\n",
        "$a = [1, 2, 4, 4, 7]$, ищем первый индекс с $a[i] \\ge 4$. Шкала — индексы, полуинтервал $[0, 5)$.\n",
        "\n",
        "| Шаг | $l$ | $r$ | $m$ | $a[m]$ | $a[m] \\ge 4$ | Что делаем |\n",
        "| --- | --- | --- | --- | ------ | ------------ | ---------- |\n",
        "| 1 | 0 | 5 | 2 | 4 | истина | $r = m = 2$ |\n",
        "| 2 | 0 | 2 | 1 | 2 | ложь | $l = m + 1 = 2$ |\n",
        "| 3 | 2 | 2 | — | — | — | $l = r$, стоп |\n",
        "\n",
        "Ответ $l = 2$. При истинном предикате элемент на $m$ **остаётся** кандидатом ($r = m$, а не $m - 1$); при ложном — выбрасывается ($l = m + 1$).\n",
        "\n",
        "Теперь тот же массив и $x = 3$, которого в массиве нет:\n",
        "\n",
        "| Шаг | $l$ | $r$ | $m$ | $a[m]$ | $a[m] \\ge 3$ | Что делаем |\n",
        "| --- | --- | --- | --- | ------ | ------------ | ---------- |\n",
        "| 1 | 0 | 5 | 2 | 4 | истина | $r = 2$ |\n",
        "| 2 | 0 | 2 | 1 | 2 | ложь | $l = 2$ |\n",
        "| 3 | 2 | 2 | — | — | — | стоп |\n",
        "\n",
        "Ответ снова $2$ — это место, **куда вставить** тройку, чтобы массив остался упорядоченным. Цикл находит место вставки. Чтобы ответить «где ключ», дополнительно проверьте `i < len(a)` и `a[i] == x`; иначе ключа нет.\n",
        "\n",
        "Проследите третий пример сами: $x = 8$ на том же массиве. Ответ должен получиться $5$, то есть за концом."
      ]
    },
    {
      "cell_type": "markdown",
      "id": "arr_md",
      "metadata": {},
      "source": [
        "## Массив: `lower_bound` и `upper_bound`\n",
        "\n",
        "Неубывающий массив — частный случай шкалы: предикат на середине — это сравнение `a[m] >= x`.\n",
        "\n",
        "- **`lower_bound`** — первый индекс с $a[i] \\ge x$. Если все элементы меньше $x$, ответ $n$.\n",
        "- **`upper_bound`** — первый индекс с $a[i] > x$.\n",
        "\n",
        "Равные $x$ занимают полуинтервал $[\\texttt{lower\\_bound}, \\texttt{upper\\_bound})$, а их количество — разность концов. Пустой массив: $[0, 0)$, цикл сразу останавливается, ответ $0$."
      ]
    },
    {
      "cell_type": "code",
      "id": "lb_code",
      "metadata": {},
      "execution_count": null,
      "outputs": [],
      "source": [
        "def lower_bound(a, x):\n",
        "    \"\"\"Первый индекс i с a[i] >= x; если такого нет — len(a).\"\"\"\n",
        "    return -1\n",
        "\n",
        "\n",
        "print(lower_bound([1, 2, 4, 4, 7], 4))  # ожидается 2\n",
        "print(lower_bound([1, 2, 4, 4, 7], 3))  # ожидается 2\n",
        "print(lower_bound([1, 2, 4, 4, 7], 8))  # ожидается 5\n",
        "print(lower_bound([7, 7, 7], 7))        # ожидается 0\n",
        "print(lower_bound([], 1))               # ожидается 0"
      ]
    },
    {
      "cell_type": "code",
      "id": "ub_code",
      "metadata": {},
      "execution_count": null,
      "outputs": [],
      "source": [
        "def upper_bound(a, x):\n",
        "    \"\"\"Первый индекс i с a[i] > x; если такого нет — len(a).\"\"\"\n",
        "    return -1\n",
        "\n",
        "\n",
        "def equal_range(a, x):\n",
        "    \"\"\"Полуинтервал (первый равный, за последним равным).\"\"\"\n",
        "    return (-1, -1)\n",
        "\n",
        "\n",
        "print(upper_bound([1, 2, 4, 4, 7], 4))  # ожидается 4\n",
        "print(upper_bound([1, 2, 4, 4, 7], 7))  # ожидается 5\n",
        "print(equal_range([1, 2, 4, 4, 7], 4))  # ожидается (2, 4): две четвёрки\n",
        "print(equal_range([1, 2, 4, 4, 7], 3))  # ожидается (2, 2): равных нет"
      ]
    },
    {
      "cell_type": "code",
      "id": "arr_exp",
      "metadata": {},
      "execution_count": null,
      "outputs": [],
      "source": [
        "# Ваш эксперимент: все элементы больше x; массив из одного элемента;\n",
        "# ключ меньше всех. Что должен вернуть каждый из двух поисков?"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "stuck_md",
      "metadata": {},
      "source": [
        "### Когда цикл не сужается\n",
        "\n",
        "Нарочно оставим $m$ в диапазоне при ложном предикате. Ограничьте число итераций, иначе ячейка зависнет."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {},
      "source": [
        "def stuck_lower_bound(a, x, max_steps=20):\n",
        "    l, r = 0, len(a)\n",
        "    for step in range(max_steps):\n",
        "        if l >= r:\n",
        "            return l\n",
        "        m = (l + r) // 2\n",
        "        print(f\"шаг {step}: l={l}, r={r}, m={m}\")\n",
        "        if a[m] >= x:\n",
        "            r = m\n",
        "        else:\n",
        "            l = m  # ошибка: должно быть m + 1\n",
        "    print(\"полуинтервал не сжался\")\n",
        "    return None\n",
        "\n",
        "\n",
        "stuck_lower_bound([1, 2, 4, 4, 7], 4)"
      ],
      "execution_count": null,
      "outputs": [],
      "id": "stuck_code"
    },
    {
      "cell_type": "markdown",
      "id": "gen_md",
      "metadata": {},
      "source": [
        "## Шкала без массива: `first_true`\n",
        "\n",
        "В `lower_bound` предикат — это `a[m] >= x`. Но самому циклу неважно, откуда берётся ответ «да / нет». Вынесем предикат в функцию `ok(t)` — получится универсальный `first_true`, который ищет первое `True` на шкале $[l, r)$.\n",
        "\n",
        "Так решают задачи, где массива значений нет вообще: есть только «уже можно / ещё нельзя» при данном $t$. Договоримся: если истинных нет, ответ равен исходному $r$."
      ]
    },
    {
      "cell_type": "code",
      "id": "first_code",
      "metadata": {},
      "execution_count": null,
      "outputs": [],
      "source": [
        "def first_true(ok, l, r):\n",
        "    \"\"\"Первый t в [l, r), где ok(t) истинно; если таких нет — вернуть r.\"\"\"\n",
        "    return -1\n",
        "\n",
        "\n",
        "print(first_true(lambda t: t >= 4, 0, 10))  # ожидается 4\n",
        "print(first_true(lambda t: t >= 0, 0, 5))   # ожидается 0\n",
        "print(first_true(lambda t: False, 0, 5))    # ожидается 5"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "slow_md",
      "metadata": {},
      "source": [
        "### Медленный эталон для сверки\n",
        "\n",
        "Пока свой цикл не отлажен, держите рядом заведомо правильную, но медленную версию: перебрать все $t$ слева направо. На контесте она получит TLE, а для сверки на маленькой шкале годится."
      ]
    },
    {
      "cell_type": "code",
      "id": "slow_code",
      "metadata": {},
      "execution_count": null,
      "outputs": [],
      "source": [
        "import random\n",
        "\n",
        "\n",
        "def first_true_slow(ok, l, r):\n",
        "    \"\"\"Перебор всех t: медленно, зато очевидно правильно.\"\"\"\n",
        "    for t in range(l, r):\n",
        "        if ok(t):\n",
        "            return t\n",
        "    return r\n",
        "\n",
        "\n",
        "for _ in range(5):\n",
        "    threshold = random.randint(0, 25)\n",
        "    ok = lambda t: t >= threshold\n",
        "    fast, slow = first_true(ok, 0, 20), first_true_slow(ok, 0, 20)\n",
        "    print(f\"порог {threshold:2}: быстро {fast:2}, медленно {slow:2}\", \"ok\" if fast == slow else \"РАСХОЖДЕНИЕ\")"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "broken_md",
      "metadata": {},
      "source": [
        "Предикат обязан быть монотонным: один переход с «ещё нельзя» на «уже можно». Если в середине дырка, тот же цикл имеет право соврать."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {},
      "source": [
        "def not_monotonic(t):\n",
        "    return t in (2, 5)\n",
        "\n",
        "\n",
        "# Запустите после того, как напишете first_true.\n",
        "print(first_true(not_monotonic, 0, 8))\n",
        "print([not_monotonic(t) for t in range(8)])\n",
        "# цикл ищет «первый истинный на монотонной шкале» — здесь шкалы такой нет"
      ],
      "execution_count": null,
      "outputs": [],
      "id": "broken_code"
    },
    {
      "cell_type": "markdown",
      "id": "answer_md",
      "metadata": {},
      "source": [
        "## Поиск по ответу\n",
        "\n",
        "Шкала — не индексы, а сами возможные ответы: скорость, вместимость, длина, порог. Схема из двух шагов:\n",
        "\n",
        "1. написать `ok(t)` — «при этом $t$ уже получается?»;\n",
        "2. пустить `first_true` по шкале $t$.\n",
        "\n",
        "Почти вся работа — в `ok`. Начнём с разминки, где `ok` дешёвый: целый квадратный корень.\n",
        "\n",
        "Максимальное целое $x \\ge 0$ с $x^2 \\le n$. Предикат «$t^2 > n$» ложен на префиксе шкалы и истинен после; первый такой $t$ минус единица — ответ. Правый конец берите заведомо истинным: подойдёт $[0, n+2)$. Никаких `sqrt` и `float` — на больших числах вещественная арифметика врёт."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {},
      "source": [
        "def isqrt(n):\n",
        "    # максимальное x >= 0 с x * x <= n; полуинтервал [l, r)\n",
        "    return -1\n",
        "\n",
        "\n",
        "print(isqrt(0))   # ожидается 0\n",
        "print(isqrt(1))   # ожидается 1\n",
        "print(isqrt(8))   # ожидается 2\n",
        "print(isqrt(9))   # ожидается 3\n",
        "print(isqrt(10))  # ожидается 3"
      ],
      "execution_count": null,
      "outputs": [],
      "id": "sqrt_code"
    },
    {
      "cell_type": "markdown",
      "id": "check_md",
      "metadata": {},
      "source": [
        "### Когда одна проверка стоит линейное время\n",
        "\n",
        "Дальше `ok(t)` сам проходит по входу. Два типовых вида проверки:\n",
        "\n",
        "1. **Сумма с округлением вверх.** Кучки размеров $a_i$, скорость $v$ за час, за час берут только одну кучку: нужно $\\sum_i \\lceil a_i / v \\rceil$ часов. Округление вверх целыми числами — `(x + v - 1) // v`, без `math.ceil`.\n",
        "2. **Жадное разрезание.** Идём слева направо и набираем подряд идущие элементы, пока сумма не превышает `cap`; как только очередной не влезает — начинаем новую часть. Результат — минимальное число частей. Здесь элементы положительные, массив непустой и `cap >= max(a)`. Объясните, почему максимально длинная допустимая первая часть не увеличивает необходимое число частей.\n",
        "\n",
        "Обе проверки монотонны: если справились при $t$, то справимся и при любом большем $t$. Проговорите это, **прежде чем** писать цикл: на неверной монотонности бинпоиск молча врёт.\n",
        "\n",
        "Стоимость: одна проверка $O(n)$, проверок $O(\\log M)$, где $M$ — число значений на шкале поиска ($M \\ge 2$). Всего $O(n \\log M)$. Линейный перебор всех $t$ вместо бинпоиска — типичный TLE."
      ]
    },
    {
      "cell_type": "code",
      "id": "check_code",
      "metadata": {},
      "execution_count": null,
      "outputs": [],
      "source": [
        "def hours_needed(piles, v):\n",
        "    \"\"\"Сколько часов уйдёт на кучки piles при скорости v > 0 (одна кучка за раз).\"\"\"\n",
        "    return -1\n",
        "\n",
        "\n",
        "def parts_needed(a, cap):\n",
        "    \"\"\"Минимум частей с суммой <= cap; a непустой, элементы > 0, cap >= max(a).\"\"\"\n",
        "    return -1\n",
        "\n",
        "\n",
        "print(hours_needed([3, 6, 7, 11], 4))    # ожидается 8 = 1 + 2 + 2 + 3\n",
        "print(hours_needed([3, 6, 7, 11], 11))   # ожидается 4 — по часу на кучку\n",
        "print(parts_needed([1, 2, 3, 4, 5], 5))  # ожидается 4: [1,2] [3] [4] [5]\n",
        "print(parts_needed([1, 2, 3, 4, 5], 15)) # ожидается 1"
      ]
    },
    {
      "cell_type": "code",
      "id": "check_bs_code",
      "metadata": {},
      "execution_count": null,
      "outputs": [],
      "source": [
        "# Соберите поиск по ответу из своих first_true и hours_needed:\n",
        "# минимальная целая скорость, при которой хватает h часов.\n",
        "piles = [3, 6, 7, 11]\n",
        "h = 8\n",
        "\n",
        "print(first_true(lambda v: hours_needed(piles, v) <= h, 1, max(piles) + 1))  # ожидается 4\n",
        "\n",
        "# Ваш эксперимент: то же для parts_needed — минимальная вместимость,\n",
        "# при которой частей не больше заданного числа. Где начинается шкала?"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "peak_md",
      "metadata": {},
      "source": [
        "### Повышенная сложность: поиск пика\n",
        "\n",
        "Это упражнение к необязательной задаче № 7 (162). Его можно оставить до выполнения обязательных задач контеста.\n",
        "\n",
        "В непустом массиве, где соседи не равны, найдите **любой** локальный максимум: элемент больше обоих соседей; за краями считаем $-\\infty$.\n",
        "\n",
        "Здесь другое обоснование деления пополам: сравнение $a[m] > a[m+1]$ **не обязано быть монотонным**. Например, для `[1, 3, 2, 4, 1]` результаты сравнений соседей — `False, True, False, True`. Готовый `first_true` к этому предикату применять нельзя.\n",
        "\n",
        "Для отдельного цикла поддерживаем непустой полуинтервал $[l, r)$ и инвариант: на его левой границе подъём ($a[l] > a[l-1]$), на правой — спуск ($a[r-1] > a[r]$), с условными $-\\infty$ за краями массива. Поэтому внутри есть пик. Пока элементов больше одного, выбираем $m$ так, чтобы и $m$, и $m+1$ лежали внутри диапазона. При спуске оставляем $[l, m+1)$, при подъёме — $[m+1, r)$. Объясните, почему инвариант сохраняется.\n",
        "\n",
        "Сначала обоснуйте существование пика, затем напишите цикл. Это поиск половины, содержащей ответ, а не поиск первого истинного монотонного предиката."
      ]
    },
    {
      "cell_type": "code",
      "id": "peak_code",
      "metadata": {},
      "execution_count": null,
      "outputs": [],
      "source": [
        "def find_peak(a):\n",
        "    \"\"\"Индекс любого локального максимума; соседи не равны, за краями -inf.\"\"\"\n",
        "    return -1\n",
        "\n",
        "\n",
        "print(find_peak([1, 2, 3, 1]))           # ожидается 2\n",
        "print(find_peak([1, 2, 1, 3, 5, 6, 4]))  # ожидается 1 или 5\n",
        "print(find_peak([5]))                    # ожидается 0\n",
        "print(find_peak([1, 2]))                 # ожидается 1"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "contest",
      "metadata": {},
      "source": [
        "## Контест: что обязательно, а что по желанию\n",
        "\n",
        "Задачи сдавайте в контест «Бинарный поиск» на [algo.ai.msu.ru](https://algo.ai.msu.ru). Номера ниже соответствуют списку из семи задач; номера LeetCode помогают найти нужное условие.\n",
        "\n",
        "**Для зачёта семинара обязательны № 4 (278. First Bad Version) и № 5 (875. Koko Eating Bananas).** Разминка и задачи повышенной сложности не обязательны и не заменяют эти две задачи.\n",
        "\n",
        "| № | Задача | Статус на семинаре | Что из ноутбука |\n",
        "| --- | --- | --- | --- |\n",
        "| 1 | 704. Binary Search | Разминка, по необходимости | `lower_bound`, затем проверка границы массива и равенства ключу |\n",
        "| 2 | 35. Search Insert Position | Разминка, по необходимости | `lower_bound` |\n",
        "| 3 | 34. Find First and Last Position of Element in Sorted Array | Повышенная сложность, по желанию | Две границы; последний равный — `upper_bound - 1`; если ключа нет, вернуть `[-1, -1]` |\n",
        "| 4 | 278. First Bad Version | **Обязательная** | `first_true`, где `ok` — готовая функция `isBadVersion` |\n",
        "| 5 | 875. Koko Eating Bananas | **Обязательная** | `hours_needed` и поиск минимальной скорости |\n",
        "| 6 | 1011. Capacity To Ship Packages Within D Days | Повышенная сложность, по желанию | `parts_needed`, обоснование жадной проверки и поиск минимальной вместимости |\n",
        "| 7 | 162. Find Peak Element | Повышенная сложность ★, по желанию | Отдельный инвариант: выбранная половина содержит пик; предикат на соседях не монотонен |\n",
        "\n",
        "Категории обозначают роль задач на этом занятии, а не рейтинг Easy / Medium на LeetCode.\n",
        "\n",
        "**Порядок работы:** если нужно закрепить поиск в массиве, начните с № 1 или № 2. Если цикл уже получается, переходите сразу к № 4, затем № 5. После обязательных выбирайте № 3 или № 6; № 7 требует отдельного рассуждения. Решать все семь задач за пару не требуется. Недорешённые обязательные задачи завершите в том же контесте после занятия; остальные — по желанию.\n",
        "\n",
        "Типичный **WA**: `l = m` вместо `m + 1`; перепутали первый допустимый и последний недопустимый ответ; перевёрнутый предикат; диапазон не охватывает нужный ответ; `float` и `sqrt` вместо точной целочисленной проверки. В нашем `first_true` после остановки `l == r`, поэтому вернуть `l` или `r` — одно и то же.\n",
        "\n",
        "Типичный **TLE**: перебор всех значений ответа вместо бинпоиска; вложенные проходы по входу внутри `ok(t)`. Один линейный проход при каждой проверке в задачах № 5 и № 6 — нормальная часть решения."
      ]
    },
    {
      "cell_type": "markdown",
      "id": "cheatsheet",
      "metadata": {},
      "source": [
        "## Шпаргалка\n",
        "\n",
        "Рекурсия:\n",
        "\n",
        "- база без нового вызова, шаг к меньшему аргументу, параметр двигается к базе;\n",
        "- печать до вызова и после вызова дают разный порядок вывода;\n",
        "- глубина и число вызовов — разные величины; два вызова на шаг дают дерево;\n",
        "- уменьшать вдвое вместо единицы — это $\\log_2 n$ шагов вместо $n$.\n",
        "\n",
        "Бинпоиск:\n",
        "\n",
        "- полуинтервал $[l, r)$: $l$ входит, $r$ нет. Цикл `while l < r`;\n",
        "- предикат истинен на $m$ → $r = m$; иначе $l = m + 1$; ответ — $l$;\n",
        "- шкала — индексы массива **или** значения ответа $t$;\n",
        "- для `first_true` предикат должен быть монотонным; поиск пика — отдельный алгоритм с инвариантом существования пика в выбранном диапазоне;\n",
        "- сначала `ok(t)`, потом цикл; считайте, сколько стоит одна проверка;\n",
        "- `bisect` в жизни удобен; на паре цель — свой цикл."
      ]
    },
    {
      "cell_type": "markdown",
      "id": "submit",
      "metadata": {},
      "source": [
        "## Сдача\n",
        "\n",
        "- **Этот** `.ipynb` семинаристу отправлять не нужно.\n",
        "- Для зачёта выполните **№ 4 — 278. First Bad Version** и **№ 5 — 875. Koko Eating Bananas** в контесте на [algo.ai.msu.ru](https://algo.ai.msu.ru).\n",
        "- **№ 1–2 — разминка**, **№ 3, 6 и 7 — повышенная сложность**: выполняются по желанию, для зачёта не требуются.\n",
        "- Если обязательные задачи не закончены на паре, дорешайте их в том же контесте после занятия.\n",
        "- Домашнее задание к лекции 4, если появится отдельным слотом, — не этот ноутбук."
      ]
    },
    {
      "cell_type": "markdown",
      "id": "review_h",
      "metadata": {},
      "source": [
        "## Запас: повтор прошлых недель\n",
        "\n",
        "Этот блок разбираем, только если контест пошёл быстро или группа просит. Эталоны не копируем: идея и крайний случай, код дописываем вместе с залом.\n",
        "\n",
        "Домашку семинара 3 на паре не разбираем: дедлайн ещё не вышел. С семинара 3 — только то, что уже было **на паре**."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Семинар 2. Пара с ближайшей суммой\n",
        "\n",
        "Массив уже **неубывает**. Нужна сумма двух элементов с разными индексами, ближайшая к заданному $S$. Если таких сумм несколько — любая из лучших. На $n \\sim 10^5$ двойной цикл не успеет.\n",
        "\n",
        "Край: отрицательные числа; две разные суммы на одном расстоянии до $S$."
      ],
      "id": "rev_sum_md"
    },
    {
      "cell_type": "code",
      "metadata": {},
      "source": [
        "def closest_pair_sum(a, s):\n",
        "    # a уже неубывает\n",
        "    return 0\n",
        "\n",
        "\n",
        "print(closest_pair_sum([2, 7, 11, 15], 9))   # ожидается 9\n",
        "print(closest_pair_sum([2, 7, 11, 15], 18))  # ожидается 18\n",
        "print(closest_pair_sum([-10, 0, 0, 10], 0))  # ожидается 0"
      ],
      "execution_count": null,
      "outputs": [],
      "id": "rev_sum_code"
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Семинар 2. Максимальная сумма пары на расстоянии\n",
        "\n",
        "Даны $a$ и $K$. Среди пар с разницей индексов **не меньше** $K$ найдите наибольшую сумму. Числа могут быть отрицательными. Два вложенных цикла на большом $n$ не живут.\n",
        "\n",
        "Край: все отрицательные; $K = 1$ (подходит любая пара с разными индексами)."
      ],
      "id": "rev_dist_md"
    },
    {
      "cell_type": "code",
      "metadata": {},
      "source": [
        "def max_pair_sum_distance(a, k):\n",
        "    return 0\n",
        "\n",
        "\n",
        "print(max_pair_sum_distance([5, 2, -1, 0, 3], 2))   # ожидается 8: 5 + 3, расстояние между индексами 4 >= 2\n",
        "print(max_pair_sum_distance([1, 100, -50, 2, 3, -7], 3))  # ожидается 103\n",
        "print(max_pair_sum_distance([-1, -2, -3, -4], 1))    # ожидается -3"
      ],
      "execution_count": null,
      "outputs": [],
      "id": "rev_dist_code"
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Семинар 3. Пары (ключ, нагрузка)\n",
        "\n",
        "Упорядочить пары $(k, p)$ по неубыванию **только ключа** $k$. При равных ключах относительный порядок пар как во входе. Если сравнить пару целиком, нагрузка $p$ может переставить равные ключи.\n",
        "\n",
        "Это не бинпоиск. Разбираем, потому что на той паре на этом часто ломались, а домашку недели 3 ещё рано вскрывать."
      ],
      "id": "rev_stable_md"
    },
    {
      "cell_type": "code",
      "metadata": {},
      "source": [
        "def stable_by_key(pairs):\n",
        "    # pairs — список кортежей (k, p)\n",
        "    return pairs\n",
        "\n",
        "\n",
        "print(stable_by_key([(2, 9), (1, 5), (2, 3)]))\n",
        "# ожидается [(1, 5), (2, 9), (2, 3)] — при ключе 2 сначала 9, потом 3"
      ],
      "execution_count": null,
      "outputs": [],
      "id": "rev_stable_code"
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Семинар 3. Ключи из малого диапазона\n",
        "\n",
        "Массив целых из $0..1000$, длина до $10^5$ и больше. Выписать в неубывающем порядке. Квадратичная сортировка получит TLE.\n",
        "\n",
        "Индекс массива снова может значить **значение**, не позицию — как частоты на семинаре 2.\n",
        "\n",
        "Мост к сегодняшней теме: если бы диапазон значений был большим, функция $F(t) = \\#\\{a_i \\le t\\}$ неубывает по $t$. Первый $t$ с $F(t) \\ge k$ ищут тем же бинпоиском по **функции**, не проходом по всем $t$. Это уже не условие той задачи, а задел."
      ],
      "id": "rev_cnt_md"
    },
    {
      "cell_type": "code",
      "metadata": {},
      "source": [
        "def counting_sort(a):\n",
        "    # 0 <= a[i] <= 1000\n",
        "    return a\n",
        "\n",
        "\n",
        "print(counting_sort([3, 1, 3, 2, 1, 3]))  # ожидается [1, 1, 2, 3, 3, 3]\n",
        "print(counting_sort([7, 7, 7]))            # ожидается [7, 7, 7]"
      ],
      "execution_count": null,
      "outputs": [],
      "id": "rev_cnt_code"
    }
  ],
  "metadata": {
    "kernelspec": {
      "display_name": "Python 3",
      "language": "python",
      "name": "python3"
    },
    "language_info": {
      "name": "python",
      "pygments_lexer": "ipython3"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 5
}