{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Лекция 3. Сортировки. Инварианты циклов\n", "\n", "На лекции 2 мы оценивали время как функцию от размера входа. Сегодня другой вопрос: **что значит «упорядочить»** и как доказать, что цикл сортировки делает именно это.\n", "\n", "Вставки, выбор, подсчёт и LSD в полный цикл соберёте на семинаре 3. Здесь — постановка, флаг и замер наивных циклов, картинки инвариантов и почему сравнениями быстрее $n\\log n$ нельзя.\n", "\n", "## План\n", "\n", "1. Отношение порядка. Камень-ножницы-бумага. Чем сортировка отличается от раскладывания по корзинам.\n", "2. Проверка флагом, обезьяна, один прогон, Fool.\n", "3. Пузырёк: тот же обмен, но прогон до конца; инвариант как `assert`.\n", "4. Вставки и выбор — две картинки.\n", "5. Нижняя оценка $\\Omega(n\\log n)$ и сортировка подсчётом. Устойчивость и ключ.\n", "6. Поразрядная LSD (карточки).\n", "7. [Домашнее задание](https://learn.ai.msu.ru/algo/1/03/hw-lecture/): короткий текст в LaTeX.\n", "\n", "" ], "id": "intro" }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Отношение порядка\n", "\n", "Говорят, что на множестве задано **отношение порядка**, если для любой пары элементов $a$, $b$ истинно **ровно одно** из трёх:\n", "\n", "$$\n", "a > b,\\qquad a < b,\\qquad a = b,\n", "$$\n", "\n", "и сравнение **транзитивно**: если $a > b$ и $b > c$, то $a > c$.\n", "\n", "Тогда у конечного непустого множества есть наибольший элемент, «пройтись по возрастанию» осмысленно, а алгоритм может опираться на сравнения.\n", "\n", "Если хотя бы одно из условий ломается, слово «максимум» уже не означает то, что мы привыкли.\n", "\n" ], "id": "order" }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Камень, ножницы, бумага\n", "\n", "Массив `[Камень, Ножницы, Бумага]`. Можно ли найти «максимум» по обычным правилам игры?\n", "\n", "Камень бьёт ножницы, ножницы — бумагу, бумага — камень. Получается **цикл**, а не порядок: транзитивность не выполняется, «самого сильного» нет.\n", "\n", "Это про правила игры, не про числа с плавающей точкой. Сломанное сравнение `float('nan')` — другая история, её разберёте на семинаре.\n", "\n" ], "id": "rps" }, { "cell_type": "code", "metadata": {}, "source": [ "beats = {\n", " \"камень\": \"ножницы\",\n", " \"ножницы\": \"бумага\",\n", " \"бумага\": \"камень\",\n", "}\n", "\n", "\n", "def wins(a, b):\n", " return beats[a] == b\n", "\n", "\n", "print(\"камень бьёт ножницы:\", wins(\"камень\", \"ножницы\"))\n", "print(\"ножницы бьют бумагу:\", wins(\"ножницы\", \"бумага\"))\n", "print(\"транзитивность требовала бы, что камень бьёт бумагу:\",\n", " wins(\"камень\", \"бумага\"))\n", "print(\"наоборот, бумага бьёт камень:\", wins(\"бумага\", \"камень\"))\n", "\n" ], "execution_count": 1, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "камень бьёт ножницы: True\n", "ножницы бьют бумагу: True\n", "транзитивность требовала бы, что камень бьёт бумагу: False\n", "наоборот, бумага бьёт камень: True\n" ] } ], "id": "rps_code" }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Сортировка — не корзины\n", "\n", "В быту «посортировать бельё» часто значит *разложить по корзинам*: белое отдельно, цветное отдельно. Это **группировка**. Внутри корзины порядок позиций не задан.\n", "\n", "В курсе **сортировка** — получить **неубывающий** или **невозрастающий** порядок позиций: каждый следующий элемент не меньше (или не больше) предыдущего.\n", "\n", "Группировку мы уже встречали как частотный массив: индекс — значение. Сортировка подсчётом позже *воспользуется* такой сводкой, но цель всё равно — порядок позиций, не просто кучки.\n", "\n" ], "id": "bins" }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Что можно упорядочить\n", "\n", "Нужны две вещи.\n", "\n", "1. Элементы лежат во множестве, на котором сравнение **осмысленно и согласовано** (как в начале лекции). Строки — да, если фиксирован алфавитный порядок. Камень-ножницы-бумага — нет.\n", "2. Есть **изменяемая** структура с позициями, куда этот порядок можно записать. Обычно это массив (`list`).\n", "\n", "Неизменяемый кортеж «сортировать на месте» нельзя: позиций не переставить. Можно построить *новый* список — это уже другая структура.\n", "\n" ], "id": "what" }, { "cell_type": "code", "metadata": {}, "source": [ "a = [3, 1, 2]\n", "a[0], a[1] = a[1], a[0]\n", "print(\"список после обмена:\", a)\n", "\n", "t = (3, 1, 2)\n", "t[0], t[1] = t[1], t[0]" ], "execution_count": 3, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "список после обмена: [1, 3, 2]\n" ] }, { "output_type": "error", "ename": "TypeError", "evalue": "'tuple' object does not support item assignment", "traceback": [ "\u001b[31m---------------------------------------------------------------------------\u001b[39m", "\u001b[31mTypeError\u001b[39m Traceback (most recent call last)", "\u001b[36mCell\u001b[39m\u001b[36m \u001b[39m\u001b[32mIn[3]\u001b[39m\u001b[32m, line 6\u001b[39m\n\u001b[32m 2\u001b[39m a[\u001b[32m0\u001b[39m], a[\u001b[32m1\u001b[39m] = a[\u001b[32m1\u001b[39m], a[\u001b[32m0\u001b[39m]\n\u001b[32m 3\u001b[39m print(\u001b[33m\"список после обмена:\"\u001b[39m, a)\n\u001b[32m 4\u001b[39m \n\u001b[32m 5\u001b[39m t = (\u001b[32m3\u001b[39m, \u001b[32m1\u001b[39m, \u001b[32m2\u001b[39m)\n\u001b[32m----> \u001b[39m\u001b[32m6\u001b[39m t[\u001b[32m0\u001b[39m], t[\u001b[32m1\u001b[39m] = t[\u001b[32m1\u001b[39m], t[\u001b[32m0\u001b[39m]\n", "\u001b[31mTypeError\u001b[39m: 'tuple' object does not support item assignment" ] } ], "id": "tuple_list" }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Проверка за один проход\n", "\n", "Достаточно соседних пар. Если хоть одна пара нарушает неубывание, массив не упорядочен.\n", "\n", "Идея: флаг (`is_ascending`), один проход слева направо. Пока всё в порядке, флаг истинный; нашли инверсию — флаг ложный. Даже если цикл доходит до конца, ответ уже есть: предикат «упорядочен?» готов для `while not …`.\n", "\n", "Пар $n-1$, время $\\Theta(n)$. Пустой массив и массив из одного элемента соседних пар не дают: нарушать нечему. Знак сравнения важен: $a_i \\le a_{i+1}$ — неубывание, $a_i < a_{i+1}$ — строгий рост.\n", "\n", "" ], "id": "check" }, { "cell_type": "code", "metadata": {}, "source": [ "def is_ascending(a):\n", " flag = True\n", " for i in range(0, len(a) - 1):\n", " if a[i] > a[i + 1]:\n", " flag = False\n", " return flag\n", "\n", "\n", "print([1, 2, 2, 4], is_ascending([1, 2, 2, 4]))\n", "print([1, 3, 2, 4], is_ascending([1, 3, 2, 4]))\n", "\n" ], "execution_count": 5, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[1, 2, 2, 4] True\n", "[1, 3, 2, 4] False\n" ] } ], "id": "check_code" }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Обезьяна и комбинаторный взрыв\n", "\n", "**Monkey sort:** пока флаг не сказал «готово» — перемешать массив наугад.\n", "\n", "Цикл пишется в несколько строк, и сразу видно, зачем это ярлык, а не метод курса. Ожидаемое число попыток растёт как $n!$: **комбинаторный взрыв**. На $n = 10$ уже миллионы перемешиваний, дальше ждать бессмысленно. Таблица факториалов ниже — объяснение тех же чисел, не отдельная теория.\n", "\n", "Полный перебор перестановок мёртв так же, как полный перебор кандидатов-делителей на $x \\sim 10^9$ с лекции 2: пространство ответов слишком велико.\n", "\n", "" ], "id": "monkey" }, { "cell_type": "code", "metadata": {}, "source": [ "import random" ], "execution_count": 7, "outputs": [], "id": "76b3adec-a83c-43ad-a519-0d8c3529b8db" }, { "cell_type": "code", "metadata": {}, "source": [ "n = 10\n", "A = list(range(n))\n", "random.shuffle(A)\n", "print(A)" ], "execution_count": 36, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[4, 9, 2, 5, 3, 7, 1, 6, 8, 0]\n" ] } ], "id": "c18aa1fe-c37f-4031-b239-dfc3aebbacf6" }, { "cell_type": "code", "metadata": {}, "source": [ "def monkey_sort(A: list):\n", " n = 0\n", " while not is_ascending(A):\n", " random.shuffle(A)\n", " n += 1\n", " print(n)" ], "execution_count": 37, "outputs": [], "id": "a9e3b326-1d7c-4cd5-8208-f6027b8e7da7" }, { "cell_type": "code", "metadata": {}, "source": [ "monkey_sort(A)\n", "print(A)" ], "execution_count": 38, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1210025\n", "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n" ] } ], "id": "8efd8f0c-bb84-4fb4-b597-b4d038a7cb69" }, { "cell_type": "code", "metadata": {}, "source": [ "from time import perf_counter\n", "for n in range(1, 15):\n", " t = perf_counter()\n", " A = list(range(n, 0, -1))\n", " monkey_sort(A)\n", " print('\\t', perf_counter() - t)" ], "execution_count": null, "outputs": [], "id": "00b1de75-b1c5-485d-bd4d-a321703afef5" }, { "cell_type": "code", "metadata": {}, "source": [ "from math import factorial\n", "\n", "for n in (5, 8, 10, 12):\n", " print(n, factorial(n))\n", "\n" ], "execution_count": 44, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "5 120\n", "8 40320\n", "10 3628800\n", "12 479001600\n" ] } ], "id": "monkey_code" }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Один прогон не сортирует\n", "\n", "Та же петля, что у проверки, но в `if a[i] > a[i+1]` меняем соседей местами.\n", "\n", "На обратно упорядоченном массиве после **одного** прохода максимум оказывается в конце, а префикс остаётся перевёрнутым: `[12, …, 1]` становится `[11, …, 1, 12]`. Что-то всплыло, массив целиком не собрался. На трёх числах то же самое: `[2, 3, 1]` → `[2, 1, 3]`.\n", "\n", "Один прогон — это ещё не сортировка.\n", "\n", "" ], "id": "onepass" }, { "cell_type": "code", "metadata": {}, "source": [ "a = list(range(n, 0, -1))\n", "print(\"до: \", a)\n", "for i in range(len(a) - 1):\n", " if a[i] > a[i + 1]:\n", " a[i], a[i + 1] = a[i + 1], a[i]\n", "print(\"после:\", a)\n", "\n" ], "execution_count": 46, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "до: [12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]\n", "после: [11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 12]\n" ] } ], "id": "onepass_code" }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Fool: повторять прогон\n", "\n", "**Fool sort** — чинить соседнюю инверсию и не усложнять себе жизнь. В записи ниже один индекс: идём вправо, на обмене возвращаемся в **начало**. Вложенного `for` нет.\n", "\n", "За это приходится платить. Каждый обмен заставляет заново просмотреть префикс, и на обратно упорядоченном входе число сравнений растёт уже как куб — отсюда кривая рядом с $n^3$. Отсутствие вложенных циклов не гарантия даже квадрата, тем более линейности.\n", "\n", "**Вывод, мост к лекции 2:** смотрите на число операций, не на «сколько `for` в тексте». На больших $n$ такая наивность даёт TLE.\n", "\n", "" ], "id": "fool" }, { "cell_type": "code", "metadata": {}, "source": [], "execution_count": null, "outputs": [], "id": "315fd9a1-696e-4229-923d-a5614305c96e" }, { "cell_type": "code", "metadata": {}, "source": [ "def fool_sort(a: list):\n", " i = 0\n", " n = 0\n", " while i < len(a) - 1:\n", " n += 1\n", " if a[i] > a[i + 1]:\n", " a[i], a[i + 1] = a[i + 1], a[i]\n", " i = 0\n", " else:\n", " i += 1\n", " return n" ], "execution_count": 55, "outputs": [], "id": "03561e55-535b-4f2b-a177-45c93c17cca4" }, { "cell_type": "code", "metadata": {}, "source": [ "num_op = []\n", "for n in range(1, 40):\n", " a = list(range(n, 0, -1))\n", " num_op.append(fool_sort(a))\n", "print(*range(1, 40), sep='\\t')\n", "print(*num_op, sep='\\t')" ], "execution_count": 56, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1\t2\t3\t4\t5\t6\t7\t8\t9\t10\t11\t12\t13\t14\t15\t16\t17\t18\t19\t20\t21\t22\t23\t24\t25\t26\t27\t28\t29\t30\t31\t32\t33\t34\t35\t36\t37\t38\t39\n", "0\t2\t6\t13\t24\t40\t62\t91\t128\t174\t230\t297\t376\t468\t574\t695\t832\t986\t1158\t1349\t1560\t1792\t2046\t2323\t2624\t2950\t3302\t3681\t4088\t4524\t4990\t5487\t6016\t6578\t7174\t7805\t8472\t9176\t9918\n" ] } ], "id": "fool_code" }, { "cell_type": "code", "metadata": {}, "source": [ "import matplotlib.pyplot as plt\n", "x = range(1, 40)\n", "x3 = [0.18*i**3 for i in x]\n", "plt.plot(x, num_op, x, x3)" ], "execution_count": 65, "outputs": [ { "output_type": "execute_result", "data": { "text/plain": [ "[,\n", " ]" ] }, "metadata": {}, "execution_count": 65 }, { "output_type": "display_data", "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAjoAAAGdCAYAAAAbudkLAAAAOnRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjExLjIsIGh0dHBzOi8vbWF0cGxvdGxpYi5vcmcvgI3uAAAAAAlwSFlzAAAPYQAAD2EBqD+naQAAVQxJREFUeJzt3Xd8U/X+x/FX0t3SAS2FUsooq+y9QRAEERARcYHbq/fiuDiv4lVxAXrdOH9uBRQVBUVQEZAle8qUvaGlBbpXku/vj0C1drDSpE3fz4d99OScT9NPTNu8Ofme79dijDGIiIiIeCGrpxsQERERKSsKOiIiIuK1FHRERETEaynoiIiIiNdS0BERERGvpaAjIiIiXktBR0RERLyWgo6IiIh4LV9PN+BpDoeDw4cPExoaisVi8XQ7IiIichaMMaSnp1OrVi2s1pLP21T6oHP48GHi4uI83YaIiIichwMHDlC7du0Sj1f6oBMaGgo4/0eFhYV5uBsRERE5G2lpacTFxRW8jpek0ged029XhYWFKeiIiIhUMGcadqLByCIiIuK1FHRERETEaynoiIiIiNdS0BERERGvpaAjIiIiXktBR0RERLyWgo6IiIh4LQUdERER8VoKOiIiIuK1FHRERETEaynoiIiIiNdS0BERERGvVekX9RQREZEysnYS2HKg7Q3gF+SRFhR0RERExPXyc2DeM5CZBAFh0Ppaj7Sht65ERETE9dZPcYac8DhoMcxjbSjoiIiIiGvZbfDb687tbveCj5/HWlHQEREREdfaMgNO7oPgSGh7o0dbUdARERER1zEGlrzq3O48CvyDPdqOgo6IiIi4zo5fIHET+FeBTv/wdDcKOiIiIuJCS15xfu5wKwRV9WwvKOiIiIiIq+xbBvuXgY8/dLnb090ACjoiIiLiKqfH5rS+HsJiPNvLKQo6IiIicuGOboIdP4PFCt1He7qbAgo6IiIicuFOn81pdgVENvBsL3+hoCMiIiIX5vge2Pytc7vH/Z7t5W8UdEREROTCLJ0IxgENL4GY1p7uphAFHRERETl/6Ymwbopzu5ydzQEFHREREbkQy98Gey7U7gR1u3u6myIUdEREROT8ZJ+EVR86t3vcDxaLR9spjoKOiIiInJ/VH0JeOlRvCo0HeLqbYp1z0Fm1ahW33XYbbdq0Yfbs2cXWrFy5kmuuuYbOnTtzww03sHXrVo/WiIiIiIvlZ8Pyd5zbPe4Ha/k8d3JOXb3xxhuMGjWKbt26sWHDBo4fP16kZsOGDfTq1YvatWvz/PPP4+vrS/fu3dm3b59HakRERKQMrJsMmccgvA60GObpbkpkMcaYsy3OzMwkJCTE+YUWC5MmTeKGG24oVHP11Vdz7NgxFixYAIDD4SAhIYEBAwYwceJEt9ecSVpaGuHh4aSmphIWFna2/ytEREQqL3s+TGwHqfth4EvQ6Q63t3C2r9/ndEbndMgpzfz58xk4cOCf38BqZeDAgcybN88jNSIiIuJim751hpzgKGgz0tPdlMrXlXeWmZnJ8ePHiYkpvJBXrVq1OHDggNtripObm0tubm7B7bS0tHN8lCIiIpWYw/Hncg9dRoF/sGf7OQOXjhzKz88HICAgoND+gICAgmPurCnOhAkTCA8PL/iIi4s7+wcoIiJS2e34GY5tBf9Q6PgPT3dzRi4NOqGhofj7+5OSklJof0pKCpGRkW6vKc6YMWNITU0t+Cjt7I+IiIj8hTGw+BXndsfbICii1PL3Fu3ixZ+3cTIrr+x7K4FLg46Pjw+tW7dm5cqVhfYvW7aM9u3bu72mOAEBAYSFhRX6EBERkbOwbykcXAk+AdDlrlJLU7PyeWP+Tt76dReLdyS7qcGiXH7R+5133sm0adNYv3494Bww/Ouvv3LHHXd4pEZERERcZPHLzs9tRkBozVJLP1iym/QcG01qhDKoZUyptWXKnIPly5eb1q1bm9atWxvA1KlTx7Ru3do8/fTTBTUOh8M88MADxt/f39SpU8cEBgaa8ePHF7ofd9acSWpqqgFMamrqOX2diIhIpXJglTFjw4x5qqoxKbtLLT2ekWuaPfGjqfvID+bHjYfLpJ2zff0+p3l0MjIy2LlzZ5H9kZGRRQb1njx5kiNHjhAXF0eVKlWKvT931pRE8+iIiIichcnDYecvzsvJh75daukLP23jnQW7aBYTxg/39sBqdf0aWGf7+n1Ol5dXqVKFNm3anFVtREQEERER5aZGREREztPBNc6QY/GBng+WWpqckcunS/cCcH+/xmUScs5F+VyYQkRERMqPhc87P7e6FiIblFr63qLdZOXZaRkbziVNo93QXOkUdERERKRkh9bAjjlgscJFD5VampSew2fL9gLwQL/GWCyePZsDCjoiIiJSmoX/c35uec0Zz+a8u2A3OfkO2sRF0LtJdTc0d2YKOiIiIlK8w+tg+0+nzuY8XGppYloOk1fsA8rP2RxQ0BEREZGSnD6b02I4RDUstfTtX3eSZ3PQsV5VejaKckNzZ0dBR0RERIo6sgH+mA1Yzng25/DJbL5Y6VxS6f5ydDYHFHRERESkOAVjc4ZD9callr71607y7A66xFejW4PyczYHFHRERETk745uhG0/cDZncw4cz+Kr1afO5lxSeiDyBAUdERERKWzhC87PLYZB9Sallr45fyf5dkOPhlF0jo90Q3PnRkFHRERE/nR0E2ydifNszn9KLd2Xksm0tQcBuL9fIzc0d+4UdERERORPp8/mNB8K0Qmllk6ctxO7w9CrcXXa161W9r2dBwUdERERcUrcDFu/d26f4WzO7mMZTF93+mxO+Rubc5qCjoiIiDidvtKq2RVQo1mppRPn7cBhoG9CNG3iIsq+t/OkoCMiIiKQtBW2fOfc7vVIqaU7k9L5bsNhoHyfzQEFHREREYFTZ3MMNB0CNZqXWvra3B0YA5c2r0GL2HD39HeeFHREREQqu6RtsHm6c/sMZ3O2HU1j1sYjANxXDufN+TsFHRERkcpu0YuAgYTBULNFqaWvnzqbM6hlDE1jwtzT3wVQ0BEREanMjm2HTd84t89wNmfz4VR+3HQUiwVGX1I+5835OwUdERGRyuz02ZwmgyCmVamlr/6yHYDLW9WicY1QNzR34RR0REREKqvkHbBpmnO7V+nz5qzae5y5W5PwsVoqzNkcUNARERGpvBa+AMYBTQZCrTYllhljeOHHbQBc06E2DapXcVODF05BR0REpDJK3AwbT53N6f1oqaXztiaxet8JAv2sjO5b/q+0+isFHRERkcpo/nOAgeZXQkzrEsvsDsP/fnaezbm1e31qhge6qUHXUNARERGpbA6sgj9mg8UKF/+31NLp6w6xPTGD8CA//tWrgZsadB0FHRERkcpm/jPOz21GQFTJA4tz8u28MucPAO7q3YDwID93dOdSCjoiIiKVye4FsGcR+Pifcd6cycv3cTg1h5jwQG7uVs8t7bmago6IiEhlYQzMO3U2p8NtEFGnxNK0nHze/HUnAPdd0ohAPx93dOhyCjoiIiKVxbZZcGgN+IVAzwdLLX1v4W5OZuXToHoIV7Wr7aYGXU9BR0REpDJw2E9daQV0GQVVokssTUrL4cMlewB4+NIEfH0qblyouJ2LiIjI2ds4DY5thcBw6HZvqaUT5+8gO99O2zoRXNq8hpsaLBsKOiIiIt7OlgcLxju3u98HQREllu5NzmTqygMAPDogAYvFUvb9lSEFHREREW+37jM4sRdCoqHzP0stfWnOH9gchoubVKdzfKR7+itDCjoiIiLeLC8LFr7o3L7oYfAPKbF048FUfvj9CBYL/GdAgpsaLFsKOiIiIt5s1fuQcRTC60D7m0stfeEn51IPQ9vE0jQmzB3dlTkFHREREW+VkwpLXnVuXzwGfANKLF2yI5klO5Px87HwQL+KtXBnaRR0REREvNWytyD7BEQ1gVbXlljmcJiCszkjO9clrlqwuzoscwo6IiIi3igz2Rl0APr8F6wlz2w8e9MRNh5KJcTfh3v6NHRTg+6hoCMiIuKNFr8CeRkQ0waaDimxLN/u4KWfnQt33nlRA6KqlPz2VkWkoCMiIuJtUg/Cqg+c232fgFLmwvly1QH2pmQRVcWff/Ss76YG3UdBR0RExNss/B/Yc6Fud2jQt8SyrDwbr8/bAcC9fRoREuDrrg7dRkFHRETEm6TsgnWTndt9nyz1bM6Hi/dwLD2XOtWCub5TySuZV2QKOiIiIt7k1/Fg7NDoUqjTpcSypPQc3lm4C4AH+zfG39c7I4F3PioREZHK6OhG2DTNud3n8VJLX/55O1l5dtrERTCkdS03NOcZCjoiIiLe4pexzs/Nh0FMqxLLNh9O5as1zoU7nxjcrMIv3FkaBR0RERFvsHMu7JoHVj/nlVYlMMYwbtZWjIHBrWJoX7eqG5t0PwUdERGRis5hhzlPOrc73QHV4kssnbs1iaW7UvD3tfLoZd6xcGdpFHREREQqug1fQNJmCAx3rlBegjybg/GztwLwjx71qV3Ve5Z6KImCjoiISEWWlwnzn3NuX/QwBFcrsXTy8n3sSc4kqoo/o3o3cFODnqWgIyIiUpEtewvSj0BEHeh0Z4llJ7PyCiYHfLB/E0ID/dzVoUcp6IiIiFRU6Ymw5DXn9iVPgW/J61S9NncHqdn5JNQM5ZoOcW5przxQ0BEREamoFoyH/EyIbe+8pLwEu45lMHn5PgAeH9QMH6v3Xk7+dy4POg6Hg9dff52LLrqIhIQE+vTpw4cfflikbv78+fTv358mTZowePBgVq9eXWY1IiIiXidpG6z9zLnd/7lSl3qYMHsrNoehb0I0PRpFuanB8sHlQeeZZ57hqaeeYvTo0cyYMYObbrqJu+++m3fffbegZsWKFQwYMIAePXowdepUGjRoQO/evdmxY4fLa0RERLzSL0+CcUDCYKjbrcSy33YmM3drEr5WC48NaurGBssHizHGuPIOe/bsSZMmTfjggw8K9g0cOJCQkBC+/vprAK644gqys7OZM2dOQU3z5s3p2bNnQSByVc2ZpKWlER4eTmpqKmFhYef/wEVERNxl9wL47Aqw+sJdKyCqYbFldodh0MTFbDuazi3d6vHUkObu7bMMne3rt8vP6PTp04clS5aQlJQEwJ49e1i7di39+vUrqFm4cCGXXnppoa8bMGAACxYscHmNiIiIV3E4YM6pdaw63F5iyAH4evUBth1NJzzIj9F9G7mpwfLF19V3+NRTT5GWlkZsbCxRUVGkpKTwzDPPcOedzkve0tPTSU1NpWbNmoW+rmbNmhw6dMilNcXJzc0lNze34HZaWtr5P1gRERF3+/1L5+KdAWHQ65ESyzJybbw0ZzsA/+7biKoh/u7qsFxx+RmdiRMnMmnSJCZPnsy8efN49913GT9+PF9++SXgHKwM4OtbOGP5+flht9tdWlOcCRMmEB4eXvARF1d5LrETEZEKLj8b5j/r3O75AIREllj69q87Sc7IpX5UCDd2qeumBssflwedsWPH8tBDD3HttdfSrFkzbrvtNm677TbGjnWuqBoaGkpAQAApKSmFvi45OZnq1au7tKY4Y8aMITU1teDjwIEDF/yYRURE3GL525B2CMLjoPO/Siw7eCKLD5bsAWDMZQn4+1be2WRc+sgdDge5ublEREQU2h8eHk52drbzG1qttG/fnqVLlxaqWbJkCR07dnRpTXECAgIICwsr9CEiIlLuZRyDxa86t/s+CX5BJZa+8NMf5NkcdI2PpF+zGm5qsHxyadCxWq307duXt99+m8OHDwOwa9cuPv74Y/r3719Qd9ddd/Htt9+yaNEiAKZPn87ixYsZNWqUy2tERES8wsLnIS8dYtpAi+Ellq3Zd4KZGw5jscDjg5tiKWV+ncrA5YORP/jgA0aNGkX9+vWJiIggNTWVq6++mpdeeqmgZuTIkezevZuBAwfi4+ODxWLhjTfeoG/fvi6vERERqfCObYfVHzu3+z8H1uLPUxhjePaHLQBc3b42zWuFu6vDcsvl8+icZrPZSElJoXr16lhLeELy8vIKav4+qNjVNSXRPDoiIlLufXE9/DEbmgyE678osey79YcYPXU9wf4+LHioN9FhgW5s0r3O9vXb5Wd0Cu7Y15caNUp/X9Df35+YmBi31IiIiFRIe5c4Q47FBy55usSy9Jx8xs3aCsBdvRt4dcg5F5V3GLaIiEh599fJAdvfAtUbl1g6cd4OktJzqRsZzD96xrunvwpAQUdERKS82vgVHF4H/qHQe0yJZTsS0/n4t70APHV5cwL9fNzUYPmnoCMiIlIe5abDL8456Oj5AFQpfo44YwxPfrcZm8NwSdMaXJwQ7cYmyz8FHRERkfJo0YuQcRSq1oeud5dY9sPvR1i2O4UAXytjL2/mxgYrBgUdERGR8iZ5Jyx727k94HnwDSi2LDPXVjAAeVTvBsRVC3ZXhxWGgo6IiEh58/MYcORDw37Q+NISyybO38HRtBziqgXxr14N3NhgxaGgIyIiUp5s/xl2zAGrn/NsTgkzG+9MyuDDxc71rMYO1gDkkijoiIiIlBe2XPjpUed217sgqmGxZcYYnvreOQC5T0I0l1Ty9axKo6AjIiJSXix7C47vhio14KKHSyz7cdNRluxMxl8DkM9IQUdERKQ8SDsMi06tC9nvGQgILbYsK8/Gc6fWs/rXRfHUjQxxV4cVkoKOiIhIefDLWMjPhNqdoOU1JZa9OX8nh1NziI0IYlTv4t/akj8p6IiIiHja/uXOWZCxwMD/lbg6+e5jGby/eDcAT17ejCB/DUA+EwUdERERT3LYYfZDzu12N0GttsWWGWN4auYW8u2GXo2r018DkM+Kgo6IiIgnrf0Ujm6EgHDo+2SJZT9vTmTR9mP4+1h5akhzLCVcdi6FKeiIiIh4StZxmPesc/vixyAkqtiy7Dw7z54agHzHRfWpH6UByGdLQUdERMRTFkyA7ONQvSl0vL3EsrcX7OTQyWxqhQdy98UagHwuFHREREQ8IXEzrPrAuX3ZC+DjV2zZ3uRM/m+hcwDyE4ObEezv664OvYKCjoiIiLsZA7P/A8YBza6A+F4llBmenrmZPLuDno2iGNCippsbrfgUdERERNxt83TYtwR8A6H/cyWWzdmSyK9/HMPPx6IByOdJQUdERMSd8jJhzhPO7R73Q0SdYsvSc/J58rtNAPyjZzwNqldxV4deRUFHRETEnZa8BmkHIbwOdB9dYtmLP/9BYloudSODGd23kfv68zIKOiIiIu5yfDf89rpz+9LnwC+o2LI1+04wafk+AMYNbUmgn2ZAPl8KOiIiIu5gDMx6EOy5UL8XNB1SbFm+3cFj327EGBjWLpYejYqfW0fOjoKOiIiIO2z6BnbNBx9/GPQKlDCw+L1Fu/kjMZ1qIf48PqiZm5v0Pgo6IiIiZS37JPw0xrnd8yGIKn7Svz3Jmbw+bwcATwxuSrUQfzc16L0UdERERMravGcgMwkiG0GP+4otMcbw3+kbybM558wZ2ibWvT16KQUdERGRsnRgFaz+yLk9+BXwDSi27Ju1h1i6K4VAPyvjhrbUnDkuoqAjIiJSVuz58MN9gIHW10P9i4otS8nI5blZzkU777ukMXUig93Xo5dT0BERESkry9+BxE0QVLXUGZCfm7WVk1n5NI0J4/Ye9d3YoPdT0BERESkLJ/c7VycH6PcshBR/mfii7ceYvu4QFgs8P6wlfj56aXYl/d8UERFxNWNg9sOQnwV1ukHbG4oty86z898ZGwG4pVs9WsdFuLHJykFBR0RExNW2zoTtP4HVDwa/WuKcOa/N286B49nUCg/kwf5N3Nxk5aCgIyIi4kq56fDjI87t7qMhOqHYss2HU/lg8R4AnrmiBVUCfN3VYaWioCMiIuJK88dB+mGoWh8ueqjYErvDMObbjdgdhkEtY7ikWQ03N1l5KOiIiIi4yuF1sPL/nNuDXi5x0c5Pl+7l94OphAb6MvZyLfNQlhR0REREXMFhh5n3gXFAi+HQsG+xZYdOZvPSnD8AGHNZU6LDAt3YZOWjoCMiIuIKK9+HI+shIBwuHV9siTGGJ2ZsIivPTsd6VbmuY5x7e6yEFHREREQuVNphmH9qQsBLxkJo8WNuvt9wmPnbkvDzsTBhWEusVi3zUNYUdERERC7Uj49AXjrU7gjtby22JCkthye/2wzAPRc3omF0qDs7rLQUdERERC7EHz/B1u/B4gODXwNr0ZdWYwyPTd9IanY+LWLDuOviBu7vs5JS0BERETlfuRnOGZABut4NNVsUWzZ93SHmbnW+ZfXS1a21zIMb6f+0iIjI+Zr7FKTuh/A60PvRYksS03J46nvnW1b3XdKYhJphbmxQFHRERETOx57FsOp95/aQieAfUqTEGOfEgGk5NlrVDuefF8W7uUlR0BERETlXeZnw/T3O7fa3QIOLiy2btuYg87cl4e9j5eWrW+Ort6zcTv/HRUREztW8Z+HEXgirDf2eLbbkSGo2z8zcAsAD/RvTqIausvIEBR0REZFzsW8ZrHjXuT3kdQgsOubGGMOj32wkPddGm7gI7uipt6w8RUFHRETkbOVlwXd3Awba3AANLym27KvVB1i4/Rj+vlZeuro1PpoY0GMUdERERM7Wr+Pg+C4IjYFLxxVbcuhkNs/+sBWAh/s3oWF0FXd2KH+joCMiInI2DqyC5W87ty9/HYIiipQ437L6nYxcG+3rVuW2HvXd26MUoaAjIiJyJvk58N1dzpXJW10HjS8ttuyLlQdYvCOZQD8rLw5vpbesygEFHRERkTNZMAGSt0OVGjBgQrElB45nMW6W8yqrhy9NIL663rIqD8ok6KSkpPDvf/+bhg0b0qhRI8aOHUteXl6hmu+++45OnTpRo0YNevTowYIFC4rcj6tqREREztuhNbB0onN70CsQXK1IicNheOSb38nMs9OpXjVu7VbPvT1KiVwedNLT0+nRowebN29m2rRpLFiwgMDAQL7//vuCmoULFzJ8+HBuuOEGli9fTp8+fRgwYACbNm1yeY2IiMh5s+XCjLudb1m1GA5NBxdbNmXFPpbuSiHIz4f/DW+FVW9ZlRsWY4xx5R0+8cQTvPvuu+zevZvQ0OInRxo4cCBWq5UffvihYF/btm1p27YtH330kUtrziQtLY3w8HBSU1MJC9P6IyIi8hfzn4NFL0JIdbhrBYREFinZn5LFgNcXkZVn5+khzblZZ3Pc4mxfv11+Ruebb77hyiuvLDHkACxZsoS+ffsW2tevXz+WLFni8hoREZHzcng9LH7FuT3wpWJDjsNheHjaBrLy7HSJr8aNXeq6t0c5I5cHnZ07dxIbG8uIESOIiYmhdevWPPvss+Tm5gLOBJaenk6NGjUKfV10dDSHDx92aU1xcnNzSUtLK/QhIiJSiC3POTGgsUOzK6D50GLL3lu8mxV7jhPs78OLw1vrLatyyOVBx263M378eHr37s3q1at56aWXePvtt3n44YcLf2Nr4W/t6+vL399Fc1XNX02YMIHw8PCCj7i4uLN+bCIiUkkseQUSN0FQNRj4crElGw+m8vKcPwB46vLmxFULdmeHcpZcHnSio6Pp27cvd955J7GxsfTr14/777+fKVOmABAaGkpQUBDJycmFvi4pKYno6GiX1hRnzJgxpKamFnwcOHDggh+ziIh4kaMbneNyAAa+CFWqFynJyrMxeuo68u2Gy1rU5OoOtd3cpJwtlwedrl27EhAQUGhfQEAANpsNYwwWi4WOHTuyePHiQjULFy6kc+fOAC6rKU5AQABhYWGFPkRERADnW1Yz7gKHDRIGQ4urii179oet7E7OpGZYIBOGtcRi0VtW5ZXLg87999/PTz/9xJw5czDGsGPHDt58802uuuqqgh+E0aNHM2PGDL7//ntsNhsff/wxK1as4N577y24H1fViIiInLUF4+Ho7xBU1TlnTjEB5qdNR/li5X4sFnjl2tZEBPt7oFE5a6YMfPHFF6ZOnTrG39/fREREmFGjRpn09PRCNRMnTjRRUVHGx8fHxMbGmsmTJxe5H1fVlCY1NdUAJjU19dwepIiIeJc9S4wZG27M2DBjNn9XbMnR1GzT+umfTd1HfjATZm91b39SyNm+frt8Hp2/ysnJITAwsNSa7OxsgoKC3FJTHM2jIyIi5KTCO90h9QC0uQGGvlWkxOEw3PjRCn7bmULL2HC+GdUNf1+tpOQpHptH56/OFHKAswonrqoREREp1uyHnSGnaj247PliSz5YspvfdjpnP37tujYKORWEniUREancNk6D378EixWGvQ8BRSe83XQolRd/dl5K/uTlzWigBTsrDAUdERGpvFIPwqwHnNsXPQxxnYqUZOfZCy4lv7R5Da7rqPnXKhIFHRERqZwcDpj+L+f4nNj2zqBTjOdmbWHXsUxqhAXw/LBWupS8glHQERGRymnZm7B3MfgFO9+y8vErUjJn81GmrNgPwMtXt6FqiC4lr2gUdEREpPI5uhHmPePcHjABIhsUKUlKy+GRb34H4M6L4unRKMqdHYqLKOiIiEjlkp8N39wBjnxoMgja3VykxOEwPPj1Bk5k5dMsJowH+zf2QKPiCgo6IiJSucx9Go5thZBoGDKx2NmPP/ptD4t3JBPoZ2Xi9W0I8PXxQKPiCgo6IiJSeeycByvecW4PfRtCir4dtflwKv/7yXkp+eODmtEwuujl5lJxKOiIiEjlkJniXLAToOMd0Khf0ZJcG6OnrifP7uCSpjUY2bmOm5sUV1PQERER72cM/DAaMo5CVGPo90wxJYb/Tt/IzqQMokMDeOEqrUruDRR0RETE+62fAltngtXPeSm5f3CRkqmrDjBj/WF8rBbeuL4tkVUCPNCouJqCjoiIeLfju+HHR5zbff4LtdoUKdl8OJWx328G4KH+TegcH+nGBqUsKeiIiIj3suU5LyXPy4C63aHbv4uUpOXkc/eUteTZHPRNiOafF8V7oFEpKwo6IiLiveY9DYdWQ2A4XPkuWAtfJm6M4dFvfmdvShaxEUG8fE1rrFaNy/EmCjoiIuKdts1yLvMAMPQdiCh6BdUnS/cye+NR/HwsvDmiLRHBWuLB2yjoiIiI9zmxD2aMcm53uRsSBhUpWbf/BONnbwXgsYFNaVunqjs7FDdR0BEREe9iy4Npt/25KvklTxUpOZmVxz2fryPfbrisRU1u6VbP7W2KeyjoiIiId/nruJzhH4Nv4bejHA7Dg19t4NDJbOpFBvPC8FaaL8eLKeiIiIj3+Pu4nKp1i5S8t3g387Yl4e9r5a2R7QgL9HNzk+JOCjoiIuIdzmJczordKbz4s3Mdq6eHNKd5rXB3digeoKAjIiIV31mMy0nOyOXeL9ZhdxiubBvLdR3j3N+nuJ2CjoiIVHxznyp1XI7dYbhv6nqS0nNpGF2F54a20LicSkJBR0REKrZts2D5W87toe8WOy7njfk7WLIzmSA/H94Z2Y6QAF83NymeoqAjIiIV11/H5XS9BxIGFilZsiOZ1+ftAGD8sBY0qhHqzg7FwxR0RESkYrLlwbRbT43L6QB9xxYpOXA8i3u/WIsxcH2nOK5sW9sDjYonKeiIiEjFNPcpOLTGOS7n6qLjcrLybNzx2WpOZOXTMjacsZc390yf4lEKOiIiUvH8fVzO39axMsbw8Ne/s+1oOlFV/Pm/G9sT6OdTzB2Jt1PQERGRiuUsxuW8vWAXszYewc/Hwjs3tKdWRJCbm5TyQkFHREQqjvxs+OrGUsflzN+WyEtznJMCPjWkOR3rVXN3l1KOKOiIiEjFYAzMHA1HNkBwZLHjcnYdy2D0F+sxBkZ0rsPIzkUvNZfKRUFHREQqhuXvwO9fgsUHrv6kyLictJx87vhsNem5NjrWq8pTGnwsKOiIiEhFsHshzHncuX3pOKh/UaHDp2c+3n0sk5jwQN4e2R5/X73EiYKOiIiUdyf2wde3gLFD6+uh87+KlLzyyx/M35ZEgK+V927sQPXQAPf3KeWSgo6IiJRfeVnw5UjIPg4xbWDwq/C3Napm/X6Et37dBcALV7WiZW2tSC5/UtAREZHyyRj4/l44uhGCo+C6KeBX+DLxLYfTeOjrDQDc0bM+Q9vGeqJTKccUdEREpHxa9iZsmgZWX7jmUwgvvHzD8cw87py0mux8Oz0bRfHIgAQPNSrlmYKOiIiUP7t+hV+edG5fOgHq9Sh0ON/u4O4pazl4Ipu6kcG8eX07fH30kiZF6adCRETKlxN7nYt1Gge0GQmd7ihSMm7WVpbtTiHE34f3b+pAeLCf+/uUCkFBR0REyo+8TJg6ErJPQK12MOiVIoOPv1p9gE+W7gXglWvb0LhGqAcalYpCQUdERMoHY+C7uyFxE4RUh2sng19goZLfdibz2LcbARjdtxGXNq/piU6lAlHQERGR8uG312Hz9FODjydBeOErqHYkpvOvyWuwOQyXt67F6L6NPNSoVCQKOiIi4nk758K8p53bl70AdbsWOpyUnsMtH68iPce5vMOLw1thtVqKuSORwhR0RETEs47vhmm3OQcft7sJOtxe6HBWno1/fLqaQyezqR8Vwns3diDQz8dDzUpFo6AjIiKek3UcplwDOalQuyMMfKnQ4GO7wzB66np+P5hK1WA/Pr6lI1VD/Eu5Q5HCFHRERMQzbHnw5Y2QsgPCajsHH/sWXqNq3Kyt/LIlEX9fK+/f1IF6USEealYqKgUdERFxP2Ng5r9h3xLwD4WRX0Fo4SuoPvltDx/9tgeAV65pTYd61TzRqVRwCjoiIuJ+i16EDV+AxQeu+QRqNC90eO6WRJ75YQsA/xnQhMGtanmgSfEGCjoiIuJev38Fv45zbg96GRpeUujwxoOp3PvFOhwGru8Ux6heDTzQpHgLBR0REXGffUudkwICdPs3dLi10OGDJ7K47dNVBQt1PnNFCywWXUYu509BR0RE3CNlF0wdAfY8aDoELnm60OG0nHxu+2QVx9JzSagZytsj2+GnhTrlApX5T5DNZsPhcJT1txERkfIs6zhMGe5cwyq2PVz5f2D98yUo3+7grslr2Z6YQY2wAD66pSOhgVqoUy5cmQadV199FT8/P6655poixz7++GPi4+Px9fUlISGBGTNmlFmNiIh4kC3XeSbn+G4IrwPXTwX/4ILDxhj+O30jS3YmE+zvw4c3d6RWRJAHGxZvUmZBZ82aNbz22mt07ty5yLHZs2dz55138txzz3HixAnuuusurr76alatWuXyGhER8aDTC3XuXwYB4TDya6gSXahk4rydfLX6IFYLvDmiLS1iwz3UrHgjizHGuPpOMzIyaNeuHRMnTuTNN98kMDCQadOmFRzv27cvERERfPPNNwX7OnfuTKNGjZg8ebJLa84kLS2N8PBwUlNTCQsLu6DHLSIif/PreFj4gnOhzpHToMHFhQ5/unQvY7/fDMCzQ1twY5e6nuhSKqCzff0ukzM6o0aN4rLLLmPAgAFFjhljWL58Ob169Sq0v0+fPixdutSlNSIi4kHrv3CGHIDBrxYJOTPWHSoIOfdd0kghR8qEr6vv8JNPPmHdunWsXr262OPp6elkZWVRvXr1Qvujo6NJTEx0aU1xcnNzyc3NLbidlpZ29g9ORETOzp7F8P29zu0eDzgX6/yL+dsSefDrDQDc0q0eo/s2cneHUkm49IzO7t27efDBB/nss8/w9fXFZrNhjMEYg81mK/VrHQ7HGedKcEXNhAkTCA8PL/iIi4sr9f5EROQcHfsDvhwJjnxofiX0eaLQ4ZV7jjNq8lrsDsOVbWN5cnAzzZUjZcalZ3Q2bdpEamoqnTp1Kth3+tLywMBAdu3aRZ06dQgJCSEpKanQ1x47doyaNZ3rnISGhrqkpjhjxozhgQceKLidlpamsCMi4ion98NnQ0+tRt4Jhr5T6DLyTYdSuf2TVeTaHPRNiOZ/w1thtSrkSNlx6RmdIUOGYLPZCn0MHDiQYcOGYbPZqFu3LhaLhW7duvHrr78W+tp58+bRrVs3AJfVFCcgIICwsLBCHyIi4gKZyTDpSkg/DFFNYMSX4PfnZeJ7kjO55eOVpOfa6FSvGm9pQkBxA4/8hD300EPMmjWLjz76iGPHjvHiiy+yYcMG7r//fpfXiIiIG+SkweRhkLITwuPgxukQ/Odq40dSs7nhgxUkZ+TRLCaMD27pQKCfjwcblsqizIOOj48PPj6Ff5j79+/Pp59+yosvvki9evWYMmUKM2bMoG3bti6vERGRMpaf45wQ8MgGCI6CG2dAeGzB4ROZedz04UoOncymflQIn93eiTDNeixuUibz6FQkmkdHROQC2G3w9c2w7QfwD4VbfoBabQoOZ+TaGPnBCjYcOEnNsECmjepK7arBJd+fyFny6Dw6IiJSCRgDM0c7Q45PAFz/RaGQk2uz889Jq9lw4CQRwX5Mur2TQo64nYKOiIicO2NgzuOwfjJYrHD1x1C/Z8Fhm93B6C/W89vOFIL9ffjk1k40qhHqwYalslLQERGRc7fkVVj2pnN7yJuQMKjgkHORzk38tPko/j5W3r+pA23iIjzTp1R6CjoiInJu1nwC8552bvcfB21HFhwyxvD0zC18ufoAVgtMvL4N3RtGeaZPERR0RETkXGyeAT+cmsKjxwPQ7Z6CQ6dDzidL9wLw/FWtGNAixv09ivyFgo6IiJydXb/Ct3eAcUD7W6DvkwWHjDE888OfIeeFq1pyTQfNOi+ep6AjIiJndnANTB0J9jxodgUMegVOrU9ljOHZH7by8W97AZgwrCXXdqzjwWZF/qSgIyIipUvcDFOGQ34mxF8Mw94Hq3MiWGMM42Zt5aPf9gAw/sqWXN9JIUfKDwUdEREpWeIW+PRyyD4Ose3h2sngGwA4Q8742Vv5YIkz5Iy7sgUjOivkSPmioCMiIsU7HXKyUiCmDdzwDQRUAZwh5/kft/H+YmfIeW5oC0Z2ruvBZkWKp6AjIiJFJW09FXKSIaY13DQDgqoCp0LOT9v4v0W7AXh2aAtu6KKQI+WTgo6IiBSWtO3PkFOzlXORzr+EnBd++oP/W+gMOc9c0ZwbFXKkHFPQERGRPx37wxlyMo9BzZZw03cQXA1whpwXf/6DdxfuApwh56au9TzYrMiZKeiIiIjTse3wyWDITDoVcr4vFHJemvMHby9whpynhyjkSMWgoCMiIpC8Az49FXJqFA05r/yynbd+dYacsZc34+Zu9TzYrMjZ8/V0AyIi4mHJO51ncjISoUaLIm9XjZv15yXkTw5uxq3d63uyW5FzoqAjIlKZpexynsnJOArRzZ1nckIiAbA7DGO+/Z2vVh8EnGdyFHKkolHQERGprFJ2wSeDIP0IRDeDm/8MObk2O/dNXc+Pm45itcALV7Xiaq1dJRWQgo6ISGWUssv5dlX6Eaje9NSZnCgAsvJs/HPSGhbvSMbfx8rE69toFXKpsBR0REQqm2PbYdJQSD8M1RPg5plQpToAqVn53PrJStbuP0mwvw/v3diBHo2iPNuvyAVQ0BERqUwOr4PJVzmXdYhqUijkJKXncNOHK9l2NJ3wID8+vrUj7epU9XDDIhdGQUdEpLLYuwQ+vw7y0qFWWxj5TcGYnAPHs7jxwxXsTcmiemgAk27vRELNMA83LHLhFHRERCqDP36Cr28GWw7U6wnXfQ6BziCzMymdGz5YydG0HOKqBTH59s7UjQzxcMMirqGgIyLi7X7/Cqb/C4wdmgyE4R+DX6Dz0MGT3PzRSk5k5dMougqT/9GZGmGBHm5YxHUUdEREvNnK92H2w4CBVtfBFW+Bj/NP/7JdKdzx2Woycm20rh3OJ7d2omqIv2f7FXExBR0REW9kDCx6CX59znm70z9hwPNgda78M29rIqOmrCXP5qBrfCTv39yBKgF6SRDvo59qERFvYwzMeRyWvem83etR6P0oWCwAfL5iP098twm7w9CvWQ3euL4tgX4+HmxYpOwo6IiIeBO7DWaOhvWTnbcHPA9dRgHgcBj+9/MfvLvQuTjnVe1q88JVLfH10frO4r0UdEREvIUtF765HbbOBIsPXPEmtBkBQE6+nQe/3sCs348AcP8ljfl334ZYTp3lEfFWCjoiIt4gNwOmjoA9C8HH33llVdPBAKRk5HLHZ6tZu/8kfj4WXriqFcPa1fZwwyLuoaAjIlLRZRyDL66FQ2vAv4pzjpz4XgDsPpbBrZ+sYl9KFmGBvvzfjR3o2iDSww2LuI+CjohIRZa0DT6/Gk7uh6CqztmOa7cHYOWe49w5aTUns/KJqxbEx7d0omF0FQ83LOJeCjoiIhXV7gXw5U2QmwrV4mHE1xDVEIDv1h/i4a9/J8/uoE1cBB/c3IGoKgGe7VfEAxR0REQqorWT4If7wGGDOl3h2ikQEokxhrd+3clLc7YDcFmLmrx6bRtdPi6VloKOiEhF4nA4JwFc/LLzdsurnbMd+waQb3fw2Lcb+XrNQQDuvCieRwckYLXqyiqpvBR0REQqivwcmDEKNn/rvH3Rf+Dix8BiITU7n7umrOG3nSlYLfD0FS24sUtdz/YrUg4o6IiIVASZyc7Lxw+sAKsfDJlYMEfOnuRM7vxsNTuSMgj29+GtEe24OCHaww2LlA8KOiIi5V3yDpgyHE7shcBwuHYy1L8IgPnbEhk9dT3pOTZqhAXw4c0daREb7tl+RcoRBR0RkfJs7xKYOhJyTkJEXRg5Dao3xuFwDjp+Ze52jIEOdavy9sh2RIcFerpjkXJFQUdEpLzaMBW+uwcc+VC7I1w/FUKiyMi18cCX65mzJRGAG7rU4cnBzfH31ZpVIn+noCMiUt44HLBgPCx60Xm72VC48l3wC2LXsQz+OWkNO5My8Pex8uzQ5lzbsY5H2xUpzxR0RETKk+wT8O2dsGOO83aPB6DPE2C1MndLIvd/uZ70XBs1wwJ554Z2tK1T1bP9ipRzCjoiIuVF4mbneJwTe8A3EAa/Bm2ux+EwvDF3B6/OdU4C2LFeVd4a2Y7oUI3HETkTBR0RkfJg4zT4/l7Iz4KIOs4rq2Jak56TzwNfbeCXU+Nxbupal8cHNdN4HJGzpKAjIuJJdhvMHQvL3nTejr8Yhn8EwdXYmZTBnZNWs/tYJv6+Vp4b2oJrOsR5tl+RCkZBR0TEUzKOwbRbYe9i5+0e958aj+PDz5uP8uBXG8g4NR7n/25sT+u4CI+2K1IRKeiIiHjCoTXw5Y2Qdgj8q8DQt6HZFeTa7Ez4YTOfLN0LQKf61XhrRDuqh2rlcZHzoaAjIuJuaz+DWQ+CPQ8iGzpXHo9OYPexDO79Yh2bD6cB8I8e9XnksgT8fDQeR+R8KeiIiLiLLRd+fATWfOy83WSgc36cwHC+XXuQx2dsIivPTrUQf16+urXWqxJxAQUdERF3SDsMX90EB1cBFrj4v9DzQTLzHTzx1Xq+XXsIgC7x1Xjt2rbUDNel4yKuoKAjIlLW/vgRZtwF2cedi3Je9SE06semQ6nc+8U69iRnYrXAfZc05u6LG+JjtXi6YxGvUWZBx2azYYzBz8+vxBpjDBkZGYSGhpZ5jYiI2+XnwC9PwMr3nLdrtoJrPsVUrc+nv+1h/Oxt5NkdxIQH8vp1belUv5pn+xXxQi4f4TZ37lz69u1LREQEYWFhdOjQgYULFxape/XVV4mKiiIyMpKYmBg+++yzMqsREXG7pG3wfp8/Q07Xe+AfczkRUJs7PlvDUzO3kGd3cEnTGsz+d0+FHJGyYlzsxhtvNPPnzzc5OTkmNzfXPPzwwyYkJMTs3r27oObrr782/v7+ZtasWcZms5lPP/3U+Pj4mEWLFrm85kxSU1MNYFJTU13zP0BEKjeHw5hVHxnzbA1jxoYZ878Gxmz/xRhjzIrdKabL+Lmm7iM/mEaPzTYfL9ltHA6HhxsWqZjO9vXbYowxZRmkbDYbwcHBvPvuu9x2220A9OrVi5iYGKZOnVpQ16NHD2JjY/nyyy9dWnMmaWlphIeHk5qaSlhY2AU/XhGpxLKOw8x/w9aZztsN+sDQd8kLqs6bv+7kzfk7cBiIjwph4vVtaREb7tl+RSqws339LvPJGQ4dOkR+fj7Vq1cHwOFwsHLlSnr06FGorlevXqxYscKlNSIibrP3N3i3hzPkWP2g37Mw8hu2ZgQx9K3fmDjPGXKGtYtl5r09FHJE3KRMr7pyOByMGjWKJk2acOmllwKQkZFBTk5OQfA5rXr16hw7dsylNcXJzc0lNze34HZaWtr5P0AREbsNFr0Ii/4HxgHV4uGqD7HVbMO7C3bx+rwd5NsNEcF+PHtFCy5vXcvTHYtUKmUadO666y5WrlzJokWL8Pf3B8BicV42abfbC9XabDasVqtLa4ozYcIEnn766fN9SCIifzq5H765Aw4sd95ufT0MfJEdJ+HBd5by+8FUAPo1q8G4K1sQHaq5cUTcrcyCzr333su0adOYN28ezZo1K9gfGhpKaGgoiYmJheoTExOJiYlxaU1xxowZwwMPPFBwOy0tjbg4rQYsIufAGNj0Dcx6AHJSwT8UBr+CvcXVvL94N6/M2U6e3UFYoC9PX9GcoW1iC/5xJiLuVSZjdP7973/z+eefM3fuXFq3bl3keM+ePZk7d26hfXPmzKFnz54ur/m7gIAAwsLCCn2IiJy19KMwdSR8c7sz5MS2h38tYlfMQIa/u5Tnf3TOjXNxk+r88kAvrmxbWyFHxINcfkbnwQcf5OOPP2b69OnUrl2b5ORkAIKDgwkODgbg0UcfpU+fPrzyyitcfvnlfPLJJ2zfvp0vvvii4H5cVSMi4hLGwO9fOteqyjkJVl+46D/Yu9/Px8sP8uLPi8m1OQgN8OWJy5txdXsFHJHywOWXl9euXZucnJwi+//zn//wn//8p+D2Dz/8wLhx49i/fz+NGjXimWee4aKLLir0Na6qKY0uLxeRM0o7Aj/cB9t/ct6OaQ1XvM1e3/o8PG0Dq/aeAKBnoyiev6oVsRFBnutVpJI429fvMp9Hp7xT0BGREhkD6z+Hn8c436ay+kHvR7F1uZdPVhzi5Tnbyc63E+zvw38HNWVEpzo6iyPiJmf7+q1FPUVEipN6EGbeBzt/cd6u1RaueJu1uTH8952VbD3inJqiS3w1XhzemrhqwZ7rVURKpKAjIvJXxsC6SfDzfyE3DXwC4OIxnGzzT16Ys4upq5ZiDIQH+fHoZQlc2yEOq1YbFym3FHRERE47ecC5hMOu+c7btTtihrzJtweqMP7V30jJzANgePvajLksgcgqAR5sVkTOhoKOiIjdBqveh/njIC8dfAOhz+PsjL+Rx2dsZfnuXQA0iq7Cc0Nb0Dk+0sMNi8jZUtARkcpt3zKY/RAkbnLejutCzsCJvPG74b03lpJvNwT6Wfl330b8o0c8/r5lvkSgiLiQgo6IVE4ZSfDLk7Dh1LxbQVWh71h+DR7Ak5O2cuB4NgB9E6J5akhzDTYWqaAUdESkcrHbYPVHMP85yE0FLNDuJg53eJhn5yfx46a1AMSEB/LUkOb0b1ZDl4yLVGAKOiJSeexfAbMfhKMbnbdj2pDZ7wXe+COCj97eRJ7NgY/Vwu096jO6byNCAvQnUqSi02+xiHi/jGMw9ylYP9l5OzACe58n+MLeh1en7CIlMwWArvGRPHl5M5rGaPJQEW+hoCMi3sthP/U21bPOmY0B0/ZGltS9m6fnJ7EzaSsA8VEhPDawKX2bRuttKhEvo6AjIt5pz2KY8184ssF5u2Yr9nR+hsfXBPHbst0AVA32475LGjOicx38fHQ1lYg3UtAREe+SuAXmjoUdc5y3A8JJ6/4o4xK78NVXRzAmC38fK7d2r8ddFzckPMjPs/2KSJlS0BER75B6CH4dDxs+B+MAqy/5bW7iI99ree2Xk2TnHwFgcKsYHhmQoMvFRSoJBR0RqdhyUmHJq7D8HbDlAGBvOoSZkf9gwsp8EtOcA43b1ong8UHNaF+3qie7FRE3U9ARkYrJlgurPoRFL0L2cQAccV2ZE3sXz6wL4fC6DADiqgXxyIAEBrWM0UBjkUpIQUdEKhaHAzZ/C/OegZP7ADBRTVhS724e3VibQztygBxqhAVw98UNubZjHAG+Pp7tWUQ8RkFHRCoGY2DPQvhlLBxZ79xVpSZr6v+Lh3e2ZM+SXCCH6qEB3NW7Add3qkOgnwKOSGWnoCMi5ZsxsPtXWPg/2L/Mucs/lK3xt/DA/u5sW+UAcomq4s+/ejXghi51FXBEpICCjoiUT8bAjl9g4QtwaLVzl48/e+oM56GkS1m73g9wUC3En39eFM+NXesS7K8/aSJSmP4qiEj5Ygz8Mdt5Buf0W1S+geyIG84Tx/qyYmsAABHBftx5UTw3d62nNalEpET66yAi5YPDAVu/g0UvQeImAIxfMOtrXsVjR3qxdatz3puwQF9nwOlWj9BATfYnIqVT0BERz3LYYfN052Xix7Y5d/lXYWm1YTx6uCcHd4QAUDMskNt61OO6TnUIU8ARkbOkoCMinmHLhY1fOyf7S9kJgN0/jF9Cr+SxIz04nuYMOAk1Q7mjZzyXt66Fv6/WoxKRc6OgIyLulXHMuaL4qg8gMwmAfP8IZgRewTNJPUlPc75F1b1hJHf0jKdX4+qa6E9EzpuCjoi4x9FNzmUaNn4F9jwAsgJr8DmX8erJnmSmBeFjtTCkZQx3XhRPi9hwDzcsIt5AQUdEyo7DATt+huVvw55FBbsPhTRjYlZ/vjnZDhu+BPv7cGvHOG7rXl+LbYqISynoiIjr5WbA+s9hxTtwfDcADosPKwO787+TfVib0xiA2IggRnSuww2d6xIerAHGIuJ6Cjoi4jon9sLK92HtJMhNBSDHJ5SvTR/eyerL4ewoLBbokxDNDV3q0KtxND5Wjb8RkbKjoCMiF8aWC9tmwdrPYPcCwABw1K82b2f1Y1pOT7IIJKqKP3d3jOP6TnWoXVVvT4mIeyjoiMj5SdwC6ybBhqmQfbxg90pra97J6c+CnNYYrHSNj2Rklzr0b1ZTl4eLiNsp6IjI2cvNgM3fOs/eHFxVsDvFGsXkvJ58be/FQRNNWKAvt7aPY0TnOjSMruLBhkWkslPQEZHSGQMHV8O6z2DTt5CXAYAdH+Y52vG5rTeLHK0xFitd6kcyul0sg1vVIshfK4iLiOcp6IhI8U4ecJ69Wf8FHNtasHsfMXye35tv7T05RgSNoqvwULtYhraJpVZEkAcbFhEpSkFHRP6UnghbvoNN38CB5QW7c/Bnlr0zX9p6s9IkEFUlkCGtazGsXSzNa4Vp5mIRKbcUdEQqu6zjsHUmbPoGs3cxFuMAwIGFlY4EZtq7MtPelTy/UPq3qsnH7WLp2TAKXx8NLBaR8k9BR6Qyyk2HbbOd4WbXPCwOGwAWYJ2jITPtXZll70yyNZKu8ZE80aYWl7WMoUqA/mSISMWiv1oilUX2CdgxF7bNxGz/GYstB3CGmy2Ousy0d+UHR2cSfWK4qHEUD7eIoW9CNFVD/D3bt4jIBVDQEfFmyTth+4/wx0+Y/cuwGDvgDDe7HDH84OjK9/auHPWrw8XNo3mkRU16N4nWmRsR8Rr6aybiTew2OLACtv+I+eMnLCk7Cg5ZgD8ctZnnaMcsexcOBTbkkpY1GdO8Jj0aRRHop8vBRcT7KOiIVHQ5qbBzLvzxE44dv2DNOQE4g02+8WGFI4G5jvbMc7TFp1p9ejWuzmPNa9KpfjX8NKBYRLycgo5IRWPLdU7gt2chZvcCOLgGi3EOJrYCJ0wVfnW0YZ69HSt92tKqQRy9mlTnlkbVqRcV4tHWRUTcTUFHpLxz2OHo77B7IY7dCzH7luJj/3MgMcBORy3mOtoxz96OjOrt6JlQkxGNq/NKvaoE+OotKRGpvBR0RMobYyB5B+xZiH3XAhx7FuOXlwo4z9gAHDNhLHM05zdHC373a0X9Js3p1bg6ExtXJyZcsxOLiJymoCPiabZcOPI7HFxJ3t7lmP0rCMhOBMDn1Ee6CWK5oylLHc3ZEtCGavXb0Ck+kpvrR9KkZig+Vs1MLCJSHAUdEXdLOwIHV5K/bwW5e5YTmLwRX0ceAKdnrMk1fqx2NGapoznbgtoSGt+Rjg2iGVm/Gg2qV9GSCyIiZ0lBR6Qs5WdD0hbs+1eRsfM3fA+vJiT7MAB+pz4AUkwoax2NWOtozOHQFgTW60z7hjFcU78adaoFK9iIiJwnBR0RV8k6Dkc3knNgHRn71uGbtJHQjL34YMcHCD9VZjcW/jB1WOtoyPaAZthiOlKrflNaxVXln7XDiQjWTMQiIq6ioCNyroyB1APYDm0gdc8a8g5uIPj4FsLzjgIQeOrjtBQTyu+OeDZaE0iPaktwfCea1q1F37gIRoYF6myNiEgZUtARKYndBif2kn1kC6n7N5OXuA2/EzuJyNxDkCMTXyDyb1+yzxHNZlOPg/4NyKzWHL/arakdF0+L2hH0igrBqkHDIiJupaAjkpNG/rGdpOzdSNbhrViS/yA4bTeRuQfxxUYQ8PcLtvOMDztMbbZb6pESmoCjRktC67ahQVws3WuEEh7sV9x3EhERN1PQEe+Xn0Pe8X2cOLSDjKO7yE/egzV1P0GZB4nIPUyoSccPqFnMl2aZAHaZGA761OZkSDy2qg3xq9mUyDoJJMRGcUVEkM7SiIiUY14RdHJycjh27Bg1atTA318DOSsVu42c1KOkJu4n/dgBck8cxJ56GGvaoYIgU9VxHH8MNYAaJdxNsgljD7EkB9YlM7whlqjGVIltRs24BtSrHkrLIJ2hERGpiCp80Bk7diwvvvgiQUFB5OfnM27cOO69915PtyUXwhhyMlNJP55I+vGj5J5MIictEfvJw1gzjuCXlURwbhLhtmSqmhMEYgik5BADkGkCOEQ0yb41SQ+KJT+0DtZqdQmMbkBErQbE1oimQ2iABgaLiHiZCh10Jk2axIsvvsjcuXPp1q0b33//PcOGDSMhIYF+/fp5ur1Kz2F3kJ6ZTmZqCtnpJ8hNP0Fu5glsmSexZ5/AZKZgyUrBL/c4/nknCM4/Sag9lXCTRqAln0Cg+ll8H5uxkkwEx62RpPtFkR0YjS2kJpZq9QiMjic8phE1Y2JpVCWAxgoyIiKVisUYYzzdxPnq1q0bDRo0YNKkSQX7Lr74YqpWrcq33357VveRlpZGeHg4qamphIWFlVWr5ZIxhlybg7z8fHJzssjPy8GWk01+Xja2vBzysjPIz87AnpuJLScDR24mJjcDk5cF+VlY8jOx2LLwsWXja8vC355BoD2TYHsGwSaTULLws9jPu79s489JSxjp1nCy/CLICojGFlwDwmrhFxFDYLU4wqLjiIquTViIzsaIiFQmZ/v6XWHP6DgcDtauXcsNN9xQaH+PHj349NNPPdTVn9bMfJf8E4ecN4zB4MBiwBgHYJz/GcepauOsMQaM3TlPi3GAw47FODA4wOHAYhzO/TiwOOxgHFhNPjjsWI0Ni8OG1diwGvupz85tH2PDih0/k4+vycff5ONHPv7kE0A+gRZHCY/iAvwlc9iNhQxLCJmWELKtVcj1DSHPN5S8gKrYAyOxhERiDamOf1gUgRE1CImoSVhkDcLCwomxWIhxfXciIlJJVNigk56eTm5uLpGRhWcyiYqKIjk5ucSvy83NJTc3t+B2WlpamfRXZcPHNLFtK5P7vmClnPiwGwt5Fn/y8SPXEkCuJZA8ayD5PkHkW4Ox+wZh9w3C+AZj/ILBPxiLfwj4h+AbHI5fcFX8q0QQGFqN4LBqhIRVJSA4nHCLpWBmYBEREXepsEHHarUCkJ+fX2h/Xl4ePj4+JX7dhAkTePrpp8u0N4Djsb1ZebIeYIFTb6mcfmvFWKzOrGGx/OW487Ox+GCxWDEWK1isf25bnfv567bVB3x8sVj9sPj4YfHxweLjj9XHF3z8sPr4YvXxx+rri9XHFx+/QHz8A/ELCML31Ge/gCD8A4LwDwjE4huEj49vsfPGiIiIVEQVNuiEhoYSHh7O0aNHC+0/evQotWvXLvHrxowZwwMPPFBwOy0tjbi4OJf31/XWF1x+nyIiInJurJ5u4EL07t2bn3/+udC+H3/8kd69e5f4NQEBAYSFhRX6EBEREe9UoYPOf//7XxYtWsSTTz7JqlWruPvuuzlw4AAPPvigp1sTERGRcqBCB52OHTsyZ84cVq1axS233MKhQ4dYuHAhDRs29HRrIiIiUg5U6Hl0XKEyz6MjIiJSUZ3t63eFPqMjIiIiUhoFHREREfFaCjoiIiLitRR0RERExGsp6IiIiIjXUtARERERr6WgIyIiIl5LQUdERES8loKOiIiIeK0Ku3q5q5yeGDotLc3DnYiIiMjZOv26faYFHip90ElPTwcgLi7Ow52IiIjIuUpPTyc8PLzE45V+rSuHw8Hhw4cJDQ3FYrGUWJeWlkZcXBwHDhyoFGtiVabHq8fqvSrT49Vj9V6V6fGey2M1xpCenk6tWrWwWkseiVPpz+hYrVZq16591vVhYWFe/4P2V5Xp8eqxeq/K9Hj1WL1XZXq8Z/tYSzuTc5oGI4uIiIjXUtARERERr6Wgc5YCAgIYO3YsAQEBnm7FLSrT49Vj9V6V6fHqsXqvyvR4y+KxVvrByCIiIuK9dEZHREREvJaCjoiIiHgtBR0RERHxWpV+Hp2z4XA4WLlyJUePHqV58+Y0atTI0y2ViaSkJObPn19k/2WXXXZWcxVUBHv27GHlypW0a9euxOfx999/Z9euXdSvX582bdq4t0EXysjI4JdffiE8PJw+ffoUOpaTk8OMGTOKfE2PHj3OaV6p8uLQoUNs2LCB8PBw2rZtS3BwcJGa3NxcfvvtNzIyMujUqRM1a9b0QKcXLiMjg7Vr15KdnU2rVq2IiYkpdHz79u2sXbu20D6r1co111zjzjZdZteuXWzZsoXIyEg6duyIn59fkZqjR4+ycuVKqlSpQvfu3SvsoN0TJ06wevVqLBYLrVq1Ijo6utDxefPmcezYsUL76tatS9euXd3ZpktlZGTwww8/EBMTQ69evYoc37BhA7t37yY+Pp7WrVuf3zcxUqrU1FTTrVs3U6tWLdOvXz8TEhJiHnzwQU+3VSZ+/fVXA5hrrrnGXHvttQUfBw4c8HRrF2zjxo3msssuM/Xr1zd+fn7mjTfeKFJjs9nMtddeayIiIkz//v1NtWrVzJVXXmny8vI80PH5y8nJMXfffbeJiYkxtWrVMr169SpSc+TIEQOYAQMGFHquly9f7v6GL0BKSooZNmyYiYuLMwMHDjQtW7Y0NWvWNPPmzStUt2PHDlOvXj3TpEkTc9FFF5ng4GDz4Ycfeqjr8zd+/HgTGxtrevbsafr162eCgoLM448/Xqjm1VdfNeHh4YWe1xEjRnio4/N36NAh079/f5OQkGCGDBliGjdubGJjY4v8jH744YcmODjY9OrVyzRu3NjUq1fP7Nixw0Ndn7/HHnvMxMXFmQEDBpiePXuaoKAgM27cuEI13bt3N82bNy/03L7++use6tg1brzxRuPv728uvfTSQvvz8/PN8OHDTdWqVU3//v1N1apVzfDhw01+fv45fw8FnTMYPXq0adCggTlx4oQxxpilS5cai8VifvrpJ882VgZOB53z+UEq75YsWWJmzZpl7Ha7CQ8PLzbovPPOOyYsLMzs3LnTGGPMnj17TEREhHnttdfc3e4FSU9PN2+88YY5efKkuf3220sNOhs3bnR/gy60f/9+88033xiHw1Gw7+677zZRUVHGbrcX7OvVq5fp37+/sdlsxhjnc+3v72/27dvn9p4vxIcffmhSU1MLbs+fP98AhYLdq6++apo3b+6J9lxq+/bt5rfffiu074orrjCdOnUquL13717j7+9v3n//fWOM8x8rffv2Nb1793Zrr64wZcqUQv+o+vzzzw1gdu3aVbCve/fuZuzYsR7ormx8+umnpnPnzuaqq64qEnTeeOMNExERYfbs2WOMMWbXrl0mLCzMvPnmm+f8fTRG5wymTJnCbbfdRkREBABdu3ala9euTJ482bONlaH58+cze/Zs9uzZ4+lWXKZ79+4MHDiw1PVQJk+ezBVXXEGDBg0AqFevHsOGDatwz3WVKlW45557zurtxlWrVvH999+zZcsWN3TmenFxcQwbNqzQOnXDhg0jOTmZgwcPAnDw4EEWLlzI6NGj8fHxAeD2228nODiYr7/+2iN9n6/bbrut0LT4F198MVWrVmX9+vWF6nJycpg9eza//PILiYmJbu7SNRo1akS3bt0K7WvcuHHBQswAX3/9NSEhIdxyyy0A+Pj4MHr0aBYsWFDw/FcUI0aMKPS2XJMmTQDnWzt/dfDgQaZPn87y5cvJzs52a4+utH37dh555BEmT56Mr2/RUTSTJ0/myiuvpF69egDEx8czdOjQ8/p7rDE6pThy5AjJycm0aNGi0P6WLVuyfPlyD3VVtvz8/Hj22Wfx8/Nj2bJlXHXVVXz00Uf4+/t7urUyt3HjRoYMGVJoX8uWLZkyZYqHOipbFouFt956i6ioKJYvX0779u2ZOnUq1atX93RrF2Tu3LlEREQQGxsLOJ9XoNDvsZ+fH02aNCk4VlGtXbuWEydOFPkblZiYyGuvvUZGRgZr1qxhzJgxPPXUU55p8gLNmTOHY8eOsWXLFr744gs++OCDgmMbN24kISGh0Atly5YtAdi0aVOFG2/2xx9/sG7dOpKSknjvvfcYPXo0rVq1KlQzZ84cjh49ytatW8nNzeWzzz4rMgavvMvNzeW6665j3LhxNGzYsNiajRs3FhlX1rJlS7755ptz/n4KOqVITU0FoFq1aoX2R0ZGcvLkSQ90VLbi4uLYtGkTjRs3BmDbtm106dKFcePG8fTTT3u4u7JljCEtLa3Y5zo3N5ecnBwCAwM91J3rBQcHs2TJkoJ/MSclJdGjRw/uuecevvzySw93d/4WL17Myy+/zGuvvVZw9sZbf4/T0tK48cYb6du3L/369SvY361bN/bu3UtkZCQAs2fPZvDgwbRu3Zorr7zSU+2et4ULF7J161Z+//134uPjqVOnTsGx1NTUYp9XoEI+tzt27GD69OkcOnSI9PR02rZtW+j4E088Qb9+/bBardjtdu666y6uvfZatm/fTtWqVT3U9bn7z3/+Q/369bntttuKPW6z2cjKyir2uc3MzMRmsxV7FqgkeuuqFKdH7v/91GFGRoZXveid1qBBg4KQA5CQkMDIkSOZOXOmB7tyD4vFgr+/f7HP9elj3iQsLKzQ2wLR0dHce++9zJo1C1NBJ0tfs2YNQ4YM4Z577mHUqFEF+73x9zgzM5NBgwbh7+/P119/Xeitu06dOhW82AMMHDiQrl27Vtjf43HjxvHtt9+yfft24uPjGTRoEHa7HXA+t8U9r0CFfG4HDx7Ml19+yZIlS3jnnXe45ZZbWLp0acHxSy+9tODtdx8fH5566imSk5NZtmyZp1o+Z+vWrePtt9+mb9++TJ06lalTp7J//36OHj3K1KlTSU1NxdfXFx8fn2KfW19f33MKOaCgU6ratWvj7+/P/v37C+3ft28f8fHxHurKvcLCwopczuitGjRoUOxzXa9evVLH9niLsLAwMjMzycrK8nQr52zt2rX069ePW265hZdffrnQsdNjrv7+3O7fv79C/h6fDjlpaWnMnTv3rP4l7w2/x1arlREjRrBnzx4OHToElPw7C1TI5/avBg4cSLVq1ViyZEmJNaGhoQAV6rn18/PjqquuYtGiRcyYMYMZM2Zw6NAhEhMTmTFjRsEYrPj4+GKf2/r165/z9/T+v94XwM/Pj379+hUasHj8+HHmzp3LoEGDPNhZ2Thy5Eih2/n5+cycOZOOHTt6qCP3GjhwIN999x15eXmA8/FPnz69UjzXAN9++y1NmzYlJCTEAx2dv/Xr19OvXz9uuukmXn311SLHW7ZsSVxcXKHf4xUrVrB3794K99xmZWUxaNAgTpw4wbx58wqduTnt78/t0aNHWbZsWYX7PS7uZ3TNmjUEBgYSFRUFOH9n9+zZw5o1awpqvvzyS+rUqVMwVqciSE1NLTKweM+ePZw4cYK4uDjA+Vbl3/8RMn36dAA6dOjgnkZdoEWLFgVnck5/dO3aldatWzN16tSCcVUDBw5kxowZ5OfnA5CXl8eMGTPO63dWY3TOYMKECXTr1o2RI0fSvXt3PvroIxo2bMjtt9/u6dZcbvz48Rw5cqRg0qZJkyZx/Phxxo8f7+HOLtyJEyf4+eefAWeAWbt2LVOnTiUuLo7u3bsDzveNv/rqKwYNGsSwYcP47rvvSE9PZ8yYMZ5s/bzMnDmTzMxMdu/eTVJSElOnTgXguuuuA2DatGlMnz6dgQMHEhoaynfffceSJUv49ttvPdn2Odu/fz+XXHIJtWrVokuXLgWPE6Bfv35ERkZisVh49dVXCx57bGwsr7zyCtdee23Bc19RDB8+nBUrVvDSSy8xd+7cgv0JCQkFk1vecMMNNGjQgA4dOnDy5Enefvtt4uPjGT16tIe6Pj9Tpkzhl19+oX///kRERLB69Wo+/vhjnn/++YIJIXv06ME111zDsGHDuP/++zl48CBvvPEGX331VaG388q7I0eOcPXVV3PllVcSHx/PwYMHee+99+jZsyfDhw8HnAPMhw4dyrBhw6hfvz4bN27k3Xff5aGHHqJ58+YefgSu9+ijjzJt2jQGDx7M0KFDmT59Ojk5OTzyyCPnfF9avfws7Ny5k/fff5+jR4/SokULRo0aRZUqVTzdVpn48ccf+fnnn8nLy6NZs2bccsstXvFYd+/ezWOPPVZkf5cuXbjvvvsKbiclJfHOO+8UzIw8atSoCjmD7r333lvs6ey/BoEVK1Ywffp0UlJSaNSoETfffDM1atRwZ5sXbMuWLTzzzDPFHnvuuecKXdGxfPlypkyZQkZGBj179uTmm28uGLBcUdx5552kpaUV2X/55ZczcuRIwDmQ84svvmDp0qUEBATQvn17RowYUeEeK8CyZcv47rvvSE5Opk6dOlxzzTUkJCQUqrHb7Xz66acsXryYKlWqMHLkSLp06eKhjs9fYmIin376Kdu2bSMyMpIePXowZMiQQoEtMTGRTz75hO3btxMTE8OgQYMq9KzIp02cOJGsrCweffTRQvsTExN55513CmZGHjVq1Hn9jVLQEREREa+lMToiIiLitRR0RERExGsp6IiIiIjXUtARERERr6WgIyIiIl5LQUdERES8loKOiIiIeC0FHREREfFaCjoiIiLitRR0RERExGsp6IiIiIjXUtARERERr/X/Z+nm8tXKLVIAAAAASUVORK5CYII=", "text/plain": [ "
" ] }, "metadata": {} } ], "id": "20e78533-1aa0-4a3e-a46d-bb4518df617c" }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Пузырёк и инвариант\n", "\n", "Пузырёк — те же соседние обмены, но прогон **доводят до конца** и помнят флагом, был ли обмен. Индекс после инверсии в начало не сбрасывают. На графике это уже не куб: в худшем случае $\\Theta(n^2)$ сравнений. Проход без обменов — «готово».\n", "\n", "Держим один вариант инварианта: после $k$ проходов $k$ **наибольших** уже стоят на своих местах **справа**, в порядке. Следующий прогон достаточно вести только по ещё не зафиксированному префиксу.\n", "\n", "### Инвариант\n", "\n", "**Инвариант цикла** — утверждение, которое верно на **границе** итерации. Его можно мысленно поставить как `assert`.\n", "\n", "Для пузырька после $k$ проходов:\n", "\n", "> суффикс длины $k$ содержит $k$ наибольших элементов массива и сам упорядочен.\n", "\n", "Отсюда видно, зачем хватает $n-1$ проходов: когда $k = n-1$, слева остался один элемент, и он обязан быть наименьшим.\n", "\n", "" ], "id": "bubble" }, { "cell_type": "code", "metadata": {}, "source": [ "def bubble_sort(a: list):\n", " n = 0\n", " is_ascending = False\n", " while not is_ascending:\n", " is_ascending = True\n", " for i in range(len(a) - 1):\n", " n += 1\n", " if a[i] > a[i + 1]:\n", " a[i], a[i + 1] = a[i + 1], a[i]\n", " is_ascending = False\n", " return n" ], "execution_count": 70, "outputs": [], "id": "63cee8bd-ddfa-4df8-b86c-59c4c7b4c5dd" }, { "cell_type": "code", "metadata": {}, "source": [ "num_op2 = []\n", "for n in x:\n", " a = list(range(n, 0, -1))\n", " num_op2.append(bubble_sort(a))\n", "plt.plot(x, num_op2, x, num_op)" ], "execution_count": 73, "outputs": [ { "output_type": "execute_result", "data": { "text/plain": [ "[,\n", " ]" ] }, "metadata": {}, "execution_count": 73 }, { "output_type": "display_data", "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAjoAAAGdCAYAAAAbudkLAAAAOnRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjExLjIsIGh0dHBzOi8vbWF0cGxvdGxpYi5vcmcvgI3uAAAAAAlwSFlzAAAPYQAAD2EBqD+naQAASERJREFUeJzt3Xl4U1X+x/F3kqbpmq6spayyyOqKrIIiqKCIiKKII6Mzzigu4zI6uIw6iv5mHEdnnNEZccMVN0BRQQWVRTYBRRBlhxZogZaSdF+S+/vjlkClYIG0t0k+r+fJk3NvTttvCCUfTs49x2YYhoGIiIhIGLJbXYCIiIhIfVHQERERkbCloCMiIiJhS0FHREREwpaCjoiIiIQtBR0REREJWwo6IiIiErYUdERERCRsRVldgNX8fj+7du0iMTERm81mdTkiIiJSB4ZhUFhYSMuWLbHbjzxuE/FBZ9euXWRmZlpdhoiIiByH7OxsWrVqdcTHIz7oJCYmAuYflNvttrgaERERqQuv10tmZmbgffxIIj7oHPi4yu12K+iIiIiEmF+adqLJyCIiIhK2FHREREQkbCnoiIiISNhS0BEREZGwpaAjIiIiYUtBR0RERMLWMQUdn8/HrFmzGD58OM2bN+f999+vtd/s2bM5++yzadOmDeeddx6LFy+2tI+IiIhEpmMKOv/85z/53//+x0033cTu3bspLS09rM/XX3/NyJEjueiii5gzZw6nnXYa5513Hj/99JMlfURERCRy2QzDMOra2e/3B/aTsNlsvPbaa4wfP75Gn4suugifz8fs2bMD53r27MlZZ53FlClTGrzPL/F6vSQlJeHxeLRgoIiISIio6/v3MY3oHG3TrAMWLlzI0KFDa5w7//zzWbBggSV9REREJHIFdQuIwsJCvF4vzZo1q3G+WbNm7Nq1q8H71Ka8vJzy8vLAsdfrPcZnKSIiIqEiqFddHfgULCqqZn6KiorC5/M1eJ/aPP744yQlJQVu2rlcREQkfAU16CQkJBATE0NeXl6N83v37qVp06YN3qc2kyZNwuPxBG7Z2dnH92RFRETk6Fa9BsunQOXhFy81lKAGHbvdzhlnnMGiRYtqnF+wYAG9e/du8D61cblcgZ3KtWO5iIhIPakshXl/gU/ugnUfWlZG0BcMvPnmm5kxYwafffYZhmHw1ltvsXjxYiZOnGhJHxEREbHAd29C8R5IyoTuoy0r45gmIy9cuJDLL788cHzzzTdz1113cfXVV/Pkk08CMHbsWLKysrjiiisoLy8nMTGRKVOmMGjQoMDXNWQfERERaWC+Kvj6n2a73y3gcFpWyjGto1NRUcG+ffsOOx8XF3fYR0A+ny9wjfuRLktvyD5HonV0REREguz7d2H6byAuHf6wBqLjgv4j6vr+fUwjOtHR0TRv3rxOfR0OBykpKY2mj4iIiDQAw4BFT5ntPr+vl5BzLLSpp4iIiATPhk9hzw8QnQhn/tbqahR0REREJEgMAxb9w2yfeR3EJltaDijoiIiISLBkLYHsZeBwQZ+brK4GUNARERGRYFlYPZpzyjhIrNuc3vqmoCMiIiInLud72PQ52OzQ/1arqwlQ0BEREZETd+BKq26jIbW9tbUcQkFHRERETkz+Zlg302wPuN3SUn5OQUdEREROzNf/BMMPHYdB8+5WV1ODgo6IiIgcP28OrH7LbA+4w9paaqGgIyIiIsdv6X/AVwGt+0KbvlZXcxgFHRERETk+pQWw4mWz3QhHc0BBR0RERI7X8ilQUQTNukPHoVZXUysFHRERETl2FcWw9DmzPeB2sNmsrecIFHRERETk2K16DUr3QUpb6DrK6mqOSEFHREREjk1VBSx+xmz3vw0cUdbWcxQKOiIiInJs1rwL3h2Q0Ax6jbO6mqNS0BEREZG68/vh66fNdt+J4IyxtJxfoqAjIiIidffTR5C3AWKS4PRfW13NL1LQERERkboxDFj0D7N95m8hxm1tPXWgoCMiIiJ1s3U+7PoWomKhz41WV1MnCjoiIiJSNwv+bt6f9iuIT7e2ljpS0BEREZFftn0xbFsIdif0u8XqaupMQUdERER+2Vf/Z96fOh6SM62t5Rgo6IiIiMjRbV9izs+xO2Fg49y880gUdEREROTo5h8YzbkakltbW8sxUtARERGRI8taClu+AnsUDLzT6mqOmYKOiIiIHNmBuTmnhN5oDijoiIiIyJFkLYMtX4bsaA4o6IiIiMiRHJibc8o4SGljbS3HSUFHREREDpe9HDZ/EdKjOaCgIyIiIrU5MDen11WQ0tbSUk6Ego6IiIjUlP0NbJ4HNkdIj+aAgo6IiIj83PxDRnNS21lbywlS0BEREZGDdqyETXPN0ZyzQ3s0BxR0RERE5FCB0ZwrIbW9tbUEgYKOiIiImHashI2fhcXcnAMUdERERMQ0/6/mfc+xkNbB2lqCREFHREREYOdK2Pgp2Oxw9l1WVxM0CjoiIiIC8/9m3ofRaA4o6IiIiMiub2HDnOrRnD9aXU1QKeiIiIhEuq+q5+b0uDysRnNAQUdERCSy7foONswOy9EcUNARERGJbAeutOo+BtI7WltLPVDQERERiVQ5q2H9J2E7mgMKOiIiIpHry8fN++6XQZNO1tZSTxR0REREIlHWsuq5OQ4YdI/V1dQbBR0REZFIYxgw7y9m+5RxYTk35wAFHRERkUiz+QvYvggc0WE9mgMKOiIiIpHl0NGcM38DyZnW1lPPFHREREQiyY8fQs534IyHAXdYXU29U9ARERGJFH4ffPGo2e47ERKaWFtPA1DQERERiRTfvw15GyA2BfrdbHU1DUJBR0REJBJUlR9cN2fA7RCTZG09DURBR0REJBKsnAqeLEhoDmf+1upqGoyCjoiISLirKIYFT5jtQX+E6Dhr62lA9RZ0iouL2bZtG2VlZUfsU1JSwtatWykvL6/3PiIiIhFr2X+heA+ktIVTf2V1NQ0q6EFn7969XHjhhaSnpzN48GCSk5O5/PLLKSoqqtHvvvvuIy0tjT59+pCWlsZTTz112PcKVh8REZGIVVoAX//TbA++F6Kira2noRlBds011xgnn3yykZeXZxiGYWRlZRktWrQw7r777kCfl19+2YiLizOWLl1qGIZhfPzxx4bD4TDmzJkT9D6/xOPxGIDh8XiO/0mLiIg0Vp8/ZBgPug3jP30Mw1dldTVBU9f3b5thGEYwg9OgQYM46aSTePHFFwPnhg8fjtvtZtq0aQD07duXjh078uqrrwb6DBkyBLfbzYwZM4La55d4vV6SkpLweDy43e7jf+IiIiKNTeFu+NcpUFkCV74JXUZYXVHQ1PX9O+gfXd1xxx3MmjWLt956i9WrV/P888+zfPlybr31VgD8fj+rVq2iT58+Nb6uX79+rFy5Mqh9REREItrCv5shJ+MM6Dzc6mosERXsb3jBBRdw+eWXM2HCBJo1a8bu3bu55557AoGksLCQiooK0tPTa3xdeno6eXl5Qe1Tm/Ly8hqTlr1e7/E/WRERkcaqYDuseNlsD/kz2GzW1mORoI/o/PrXv2bJkiXs2LGDrKwsNm7cyOuvv87dd98NgMPhAKCioqLG15WXlxMVFRXUPrV5/PHHSUpKCtwyM8N7MzMREYlQX/0f+Cuh3SBoP8jqaiwT1KDj8/l47733+N3vfkeTJub+Ga1bt+baa6/lrbfeAiAhIYHk5GRycnJqfG1ubi6tWrUKap/aTJo0CY/HE7hlZ2ef2JMWERFpbPb8BN+b82IZ8qC1tVgsqEHH4XCQmJhIfn5+jfN5eXkkJycHjgcPHsycOXMCx4Zh8MknnzB48OCg9/k5l8uF2+2ucRMREQkrXz4Khh+6XAStTre6GksFfY7O9ddfzxNPPEFGRgY9e/Zk6dKlvPDCC0yePDnQ5/7776dfv37ce++9XHzxxUydOpWcnBzuuuuuoPcRERGJKDtXwo+zABucc5/V1Vgu6JeXV1VV8eKLLzJjxgx2795NRkYGV111FePGjcN2yESoRYsW8de//pWsrCw6duzIAw88QK9evWp8r2D1ORpdXi4iImHl1VGw5UvoeSWM/p/V1dSbur5/Bz3ohBoFHRERCRtbF8DUi8EeBTevgNR2VldUbyxbR0dEREQs4PfDZw+Y7dMnhHXIORYKOiIiIuFg7XuQ8x1EJ8KgP1ldTaOhoCMiIhLqKkth3l/M9oA/QEITS8tpTBR0REREQt2y/4InG9wZ0Ocmq6tpVBR0REREQllxHiz8h9k+9wGIjrO2nkZGQUdERCSUzf8rlHuheQ/oOdbqahodBR0REZFQlbcRVrxktodNBrve1n9OfyIiIiKhau5D4K+CjudH9MadR6OgIyIiEoq2fQ0/fQQ2Bwz9i9XVNFoKOiIiIqHG74fP7jfbp18LTbtYW08jpqAjIiISan6YDrtWQXQCDJ5kdTWNmoKOiIhIKKksg7kPm+0Bf4CEppaW09gp6IiIiISS5f8DTxYktoQ+E62uptFT0BEREQkVxfmw4EmzPUSLA9aFgo6IiEiomP9XKPdoccBjoKAjIiISCvI2wYoXzfawR8HusLaeEKGgIyIiEgrmPli9OOAwaD/Y6mpChoKOiIhIY7d9cfXigHYtDniMFHREREQaM78fPr3PbJ92LTQ92dp6QoyCjoiISGOmxQFPiIKOiIhIY3Xo4oD9/wCJzSwtJxQp6IiIiDRWS5+tXhywBfTV4oDHQ0FHRESkMfLuggV/N9vnPaTFAY+Tgo6IiEhj9PmfobIYWvXW4oAnQEFHRESksdm+BNa8C9hg+BNgs1ldUchS0BEREWlM/D6Y/Uezffq10PIUS8sJdQo6IiIijcnKVyB3DcQkwbkPWF1NyFPQERERaSxK9sEXj5jtc+6H+HRr6wkDCjoiIiKNxZeTobQAmnaDM66zupqwoKAjIiLSGOSugRUvme0L/wqOKGvrCRMKOiIiIlYzDPjkbjD80O1SaDfQ6orChoKOiIiI1da+D1mLISoWhj5idTVhRUFHRETESuVF8Fn11VUD74TkTGvrCTMKOiIiIlZa9A8o3AXJbaDfLVZXE3YUdERERKySvxkWP2O2L3gcnDHW1hOGFHRERESs8ul94KuADudC5+FWVxOWFHRERESssPFz2DAb7FFwwV+1n1U9UdARERFpaFUVMOdPZvus30OTTtbWE8YUdERERBrasucgfxPEN4VB91hdTVhT0BEREWlI3hyY/zezPfRhiHFbW0+YU9ARERFpSHMfgooiaHUm9LzS6mrCnoKOiIhIQ9m+GL6fBtjM/azsehuub/oTFhERaQhVFTDrD2b7tF9BxumWlhMpFHREREQawuJ/Qd56iG8C5z1kdTURQ0FHRESkvu3bAgueMNvnPwZxqdbWE0EUdEREROqTYcDHd0JVGbQfDD0ut7qiiKKgIyIiUp/Wvg+bvwCHC0b8QysgNzAFHRERkfpSWgBzJpnts/8IaR2srScCKeiIiIjUl7kPQ/EeSO8M/W+1upqIpKAjIiJSH7KWwcqXzfZFT0GUy9p6IpSCjoiISLD5KuGjP5jtU8dD2/6WlhPJFHRERESCbcm/Yc86iEuDoY9YXU1EU9AREREJpoJt8NVfzfawyVozx2IKOiIiIsFiGPDxXVBVCm0HQi9t2mk1BR0REZFgWTcTNn0OjmhzArLWzLGcgo6IiEgwlHlg9j1me+CdkN7R2noEgKj6+sZ5eXl89dVX2Gw2hgwZQnJyco3H/X4/X331Fdu3b6djx44MGDDgsO8RrD4iIiL1bt4jULQb0k6CAbdbXY1Uq5cRnRdeeIG2bdvywgsvMHPmTPr37893330XeLykpITBgwczYcIE5syZw5gxYxg1ahRVVVVB7yMiIlLvdqyEb14w21ozp1EJ+ojOwoULueGGG3jnnXcYM2YMAHv37mXPnj2BPn/729/YvHkzq1evJj09na1bt9KzZ09efPFFfve73wW1j4iISL3yVcGs2wADel0F7c62uiI5RNBHdP7+97/Tv3//QMgBaNKkCd26dQscT5s2jbFjx5Keng5Au3btGDFiBNOmTQt6HxERkXq17DnYvQZiU2DYo1ZXIz8T9KDz9ddfM2TIEDZt2sTUqVOZPXs2hYWFgccrKyvZuHEjXbt2rfF1Xbt25Ycffghqn9qUl5fj9Xpr3ERERI7Lvq3w5WNme9ijEJ9ubT1ymKAGHcMwyM/PZ9GiRVx44YXMnTuXBx54gI4dO7J8+XIAioqK8Pv9h01OTklJCYSOYPWpzeOPP05SUlLglpmZeWJPWkREIpPfDx/eApUl5po5p1xtdUVSi6AGHZvNRkxMDBs2bGDVqlW89tprrFixgn79+nHjjTcCEBsbC1BjlAfA6/USFxcX1D61mTRpEh6PJ3DLzs4+3qcrIiKRbOVLsG0hOONg5DNaM6eRCvpk5E6dOtGtWzcSExMD584//3xuueUWDMMgJiaGVq1asXXr1hpft3XrVk466SSAoPWpjcvlwuXSbHgRETkBBdvh8wfN9nkPQWo7S8uRIwv6HJ1Ro0axZs0a/H5/4Nzq1atp164dtuq0O3LkSN577z0qKioAcxTmww8/ZOTIkYGvCVYfERGRoDIMmHUrVBRB635w5m+trkiOwmYYhhHMb+j1eunfvz/Nmzfnwgsv5IcffuDNN9/k3Xff5aKLLgIgJyeHs846i/bt23P++eczffp0SkpKWLJkCW63O6h96lJvUlISHo+nzl8jIiIRbOUr5uXkUbFw49eQ1sHqiiJSXd+/gx50wFzIb+rUqaxfv54WLVowZswYOnSo+RchPz+fV155haysLDp27MiECRNISEiolz5Ho6AjIiJ1tj8bnu0LFYVw/mPQd6LVFUUsS4NOKFHQERGROjEMeP0y2DwPWvWG6+aA3WF1VRGrru/f2tRTRESkLr593Qw5DheMelYhJ0Qo6IiIiPwSz0749D6zfe592pk8hCjoiIiIHI1hwEd/gHIPZJwBfW+2uiI5Bgo6IiIiR7N6Gmz8DBzRcMl/9JFViFHQERERORJvDsy5x2wPngRNu1hbjxwzBR0REZHaGAZ8dDuUeaDlqdDvVqsrkuOgoCMiIlKbNe/Chtlgd8Ilz4Ij6LsmSQNQ0BEREfm5wt3wyR/N9qB7oFlXa+uR46agIyIicijDgI/vgLL90LwnDPiD1RXJCVDQEREROdTa9+Gnj8AeZS4M6HBaXZGcAAUdERGRA7w5Bz+yOvuP0LyHtfXICVPQERERAfD74YOboHRf9UdWd1hdkQSBgo6IiAjA8udh8xcQFQOXvQBR0VZXJEGgoCMiIrJ7HXz+Z7M97FFo0tnaeiRoFHRERCSyVZXD9N+CrxxOGgpn/sbqiiSIFHRERCSyffEI7F4LcWnmXlY2m9UVSRAp6IiISOTaMh8W/9tsj/w3JDazth4JOgUdERGJTKUFMOP3gAGnT4Auw62uSOqBgo6IiESeAxt2Fu6C1A5w/mNWVyT1REFHREQiz/dvww8zwOaAy6ZAdLzVFUk9UdAREZHIUrAdPr7LbA+eBBmnW1uP1CsFHRERiRx+H8z4HVQUQmYfGKjVj8Odgo6IiESORU9B1hKIToTR/wO7w+qKpJ4p6IiISGTYuQq+etxsD38CUtpaWo40DAUdEREJfxXF5urH/iroOgp6XWl1RdJAFHRERCT8fXY/5G+CxJZw0VNa/TiCKOiIiEh4Wz8HVrxkti99DuJSra1HGpSCjoiIhC/PTph5o9nuezO0H2xpOdLwFHRERCQ8+SrhveugdB+06AVD/mx1RWIBBR0REQlPXzwK2UvB5YbLX4Eol9UViQUUdEREJPxs+Ay+ftpsj3wGUttbWo5YR0FHRETCi2cHzLjBbPe+AbqNsrQcsZaCjoiIhI/AvJwCaHEKDHvU6orEYgo6IiISPub9BbKXaV6OBCjoiIhIeFg/Bxb/y2xf8m9IbWdtPdIoKOiIiEjo258NM39vts/6PXS9xNp6pNFQ0BERkdDmq4T3fm3Oy2l5Ggz9i9UVSSOioCMiIqFt3sOw4xtwJcHlL2tejtSgoCMiIqFr/WxY/IzZHvUfSGlraTnS+CjoiIhIaNqfBTMOzMu5EU6+2Np6pFFS0BERkdBTVQHv/hrK9mtejhyVgo6IiISeeQ/DzhUQk1S9Xk601RVJI6WgIyIioeWnj2HJv832qOcgpY219UijpqAjIiKhY+8GmP47s93nJugywtp6pNFT0BERkdBQ5oFp46CiEFr307wcqRMFHRERafz8fph+A+RvBHcGXDEVHE6rq5IQoKAjIiKN31ePw4Y54HDB2NchoanVFUmIUNAREZHG7cdZsOBvZvvif0LGadbWIyFFQUdERBqvPT/WXBTwlKusrUdCjoKOiIg0TqUF1ZOPi6DtQBj2iNUVSQhS0BERkcbH74P3fwv7tkBSa3NRQE0+luOgoCMiIo3PF4/Cps8hKhaufB3i062uSEKUgo6IiDQuP8yARf8w2yOfgRa9rK1HQpqCjoiINB65a2HmTWa73y3Q83Jr65GQp6AjIiKNQ8k+c/JxZQm0PweGPGR1RRIGFHRERMR6vip47zrYvx2S28CYl8ARZXVVEgbq9W/Rt99+y5NPPknv3r259dZbazyWk5PDlClT2L59Ox07duR3v/sdKSkp9dJHREQauXkPw5YvwRkHV74JcalWVyRhot5GdIqKirjqqqv48ssvWbBgQY3HsrOzOe2001i6dCmnnHIKH3/8Mb1796agoCDofUREpJH7/h1Y/C+zPepZaN7d2nokrNRb0Lnpppu4+OKLOfXUUw977JFHHqFp06bMmjWLW265hU8//ZSioiKefvrpoPcREZFGbPti+GCi2R5wO3S71Np6JOzUS9B57bXXWLNmDZMnT6718Y8++ojRo0fjcDgAiIuLY+TIkXz00UdB7yMiIo1U3iZz8rGvAk4eCef+2eqKJAwFPehs3LiRO++8kzfeeIPo6OjDHi8tLSUnJ4c2bdrUON+mTRu2bNkS1D61KS8vx+v11riJiEgDK86HNy83t3nIOB0u/R/YdX2MBF9Q/1ZVVFRw5ZVX8uCDD9K1a9da+5SVlQGQkJBQ43xiYiKlpaVB7VObxx9/nKSkpMAtMzOzrk9PRESCobLMHMnZtwWSW8NV0yA6zuqqJEwFNeh8+umnrF27liVLljB+/HjGjx/Pd999xzfffMP48ePJy8sjISEBu91+2IThffv2kZSUBBC0PrWZNGkSHo8ncMvOzg7GUxcRkbrw+805OdlLwZUE496FhKZWVyVhLKiXl5966qm8+OKLNc798MMPOJ1OLrjgAmJjY3E6nXTp0oW1a9fW6LdmzRp69OgBELQ+tXG5XLhcruN+jiIicgK+egzWvgf2KBj7KjTtYnVFEuaCOqLTqlWrwEjOgVtGRgatW7dm/PjxxMfHAzBu3DjefvttcnNzAVi/fj2zZ89m3Lhxge8VrD4iItJIfPsGLHjCbF/0NLQfbGU1EiEsWXbyzjvvZOHChfTq1YszzjiDJUuWMGrUKCZMmBD0PiIi0ghsmQ+zqheOHXgnnHaNtfVIxLAZhmHU5w/46quvcDgcDBw4sMZ5wzBYvnw5WVlZdOzYkVNOOeWwrw1Wn6Pxer0kJSXh8Xhwu93H9LUiIlIHe9fDC0Oh3APdL4PRL+gKKzlhdX3/rveg09gp6IiI1KOiPfDCENifBZlnwa8+BGeM1VVJGKjr+7citYiI1I/KUnjrKjPkpLQz97BSyJEGpqAjIiLB5/fD9Btg5wqISYar34X4dKurkgikoCMiIsE37yH48UOwO82RnPSOVlckEUpBR0REgmv5FPj6n2b7kv9A2/7W1iMRTUFHRESC5/t34ZO7zPbge6HXWGvrkYinoCMiIsGx4TOY+Xuz3fsGGHS3tfWIoKAjIiLBkLUU3vkV+Kugx+VwwV/BZrO6KhEFHREROUG5a+HNK6CqFE4aCqOe04KA0mjob6KIiBy/fVvgtUuhzAOZfeCKV8HhtLoqkQAFHREROT6FufDqKCjeA826w7i3ITrO6qpEalDQERGRY1daYI7k7N9urno8fjrEJltdlchhFHREROTYVBTDm2NhzzpIaA7XzIDEZlZXJVIrBR0REam7qgrz6qrsZRCTBNdMh9R2VlclckQKOiIiUjd+v7lOzqa54IyDq9+DZt2srkrkqBR0RETklxkGzP4jrH3f3L/qitcgs7fVVYn8IgUdERH5ZV8+Bt+8ANjg0v9Cx/OsrkikThR0RETk6BY9BQv+ZrZH/B16jLG2HpFjoKAjIiJHtuhpmPuQ2T73ATjzN1ZWI3LMFHRERKR2X/8T5j5ots+5H86+y9p6RI6Dgo6IiBxu8TPw+Z/N9uB7YdAfra1H5Dgp6IiISE2L/w2f3W+2B0+CwfdYW4/ICVDQERGRg5b8Bz67z2wP+hMM/pO19YicIAUdERExLXkWPr3XbJ99t0KOhAUFHRERgaXPwaeTzPbZf4Rz7gWbzdqaRIJAQUdEJNIt+x/MqR69GXgXnHOfQo6EDQUdEZFItux5mH232R5wB5x7v0KOhBUFHRGRSLV8irl/FcCA22HInxVyJOwo6IiIRKLlU+CT6gUA+/8BhjyokCNhSUFHRCTSfP2vgyGn361w3kMKORK2oqwuQEREGohhwLy/wKJ/mMcDbtdIjoQ9BR0RkUjg98HHd8LKl83j8x4yg45ImFPQEREJd1UVMON38MN0wAYXPw2nT7C4KJGGoaAjIhLOKkrgnV/Bps/B7oTRz0P30VZXJdJgFHRERMJV6X54cyxkLwVnHIx9DU46z+qqRBqUgo6ISDgq2gOvjYbdayAmCca9C63PsroqkQanoCMiEm72Z8Grl8C+LRDfFK6ZAc27W12ViCUUdEREwsne9fDqKCjcBcmt4ZqZkNbB6qpELKOgIyISLnaugtcvg9J90KSLOZLjbml1VSKWUtAREQkHWxfCW1dBRSG0PA3Gvw9xqVZXJWI5BR0RkVD3/bvwwU3gq4B2Z8OVb4Ir0eqqRBoFBR0RkVBlGLDgCfhysnl88kgYPQWcMdbWJdKIKOiIiISiqgqYdSusfss87n8bDHkI7NqrWeRQCjoiIqGmZJ+52vG2hWBzwIgn4YxfW12VSKOkoCMiEkr2bYE3roD8jRCdCFe8otWORY5CQUdEJFRkLYNpV0FJPrhbwdXvQLNuVlcl0qgp6IiIhIK178OMG8FXDi1OgXFvQ2Jzq6sSafQUdEREGjPDgIVPwhePmMedR8BlUyA63tq6REKEgo6ISGNVVQEf3Q7fvW4e970Zhv4F7A5r6xIJIQo6IiKNUel+eOca2LoAbHa48G/Q+7dWVyUSchR0REQam73rYdrV1VdWJcCYl6HTMKurEglJCjoiIo3Jug9h5o1QUQTuDLhqGrToaXVVIiFLQUdEpDHw+8wJx4ueMo/bDjRHchKaWFuXSIhT0BERsVrJPnjvOtjypXnc92Y472Fw6J9okROl3yIRESvlrIa3x8P+LHDGwchnoMcYq6sSCRsKOiIiVlk9DWbdBlVlkNIOxr4OzbtbXZVIWFHQERFpaL5K+PQ+WP4/87jjMBj9PMSmWFuXSBiyB/sb7tixgzvvvJMzzjiDXr168Zvf/IZt27Yd1u/zzz/n3HPPpUOHDlxwwQUsW7as3vqIiDQahbth6sUHQ86ge+CqtxVyROpJ0IPO5ZdfTqtWrfjvf//LK6+8wp49exgwYAB5eXmBPkuWLGHEiBGcd955zJw5k27dunHuueeyfv36oPcREWk0spfD/86GrCXgcpuXjp9zL9iD/k+xiFSzGYZhBPMb+nw+HI6Dy5MXFRWRnJzMK6+8wvjx4wEYOXIkFRUVzJkzJ9Cve/fu9OvXj+effz6ofX6J1+slKSkJj8eD2+0+/icuInIkhgHLp8Cn94K/Epp0gbFvQPpJVlcmErLq+v4d9P9GHBpyACorKzEMA6fTGTg3f/58hg4dWqPfBRdcwIIFC4LeR0TEUsX5MG0czP6jGXK6XgK/maeQI9JA6n0y8v33309KSgrDhpnLlxcWFuL1emnevHmNfs2aNWPnzp1B7VOb8vJyysvLA8der/f4n5yIyNFsXQDTb4DCHHBEmxtynvV7sNmsrkwkYtRr0PnPf/7DlClT+Oijj0hJMSfa+f1+8wdH1fzRTqcTn88X1D61efzxx3n44YeP9ymJiPwyXyV89Tgs/AdgQHonuOxFbeUgYoF6mwH3/PPPc8cdd/DOO+8ERnMAEhMTcblcNSYnA+Tl5dGkSZOg9qnNpEmT8Hg8gVt2dvYJPU8RkRoKtsFLF8DCJwEDTvsV3PCVQo6IReol6LzwwgvccsstvPXWW4waNarmD7TbOeOMM/j6669rnF+4cCG9e/cOap/auFwu3G53jZuISFCseQ/+OxB2roCYJLh8qrnScXS81ZWJRKygB52XX36ZiRMn8tZbbzF69Oha+0ycOJEZM2bwxRdfAPDuu++yaNEibrrppqD3ERGpd+VFMPMmeP96KPdCZh/4/SLoNsrqykQiXtDn6EycOBGbzcatt97KrbfeGjh/xx13cMcddwBw1VVXsW3bNkaNGoXf78flcvHcc89xzjnnBPoHq4+ISL3a9Z25Iee+zWCzw9l/hLPv1oacIo1E0NfR2blzJ7V9y9o+JqqqqqKgoIDU1NTDLksPdp8j0To6InJc/H5Y+izMfci8bNydAaOnQNv+VlcmEhHq+v4d9P9yZGRk1LlvVFTUUScOB7OPiEjQFGyDD28xLx8H6HKRORcnLtXSskTkcBpbFRGpK78fVrwInz8IlcUQFQvnT4YzrtPaOCKNlIKOiEhd7NsCH9wC2xeZx236m6M4aR2srUtEjkpBR0TkaPx+WP48zHsYKkvAGQ/nPQRn/kabcYqEAAUdEZEjyd8MH0w0dxsHaDvQHMVJbWdtXSJSZwo6IiI/5/fBsv/CvL9AVRlEJ5j7VJ3+a43iiIQYBR0RkUPlbTQX/9ux3DxuP9gcxUlubWlZInJ8FHRERAB8Vea6OF9Orh7FSYTzH4XTrtUVVSIhTEFHRCRrGXx8J+xeYx53GAIX/xOSM62tS0ROmIKOiESuor3mysbfvW4exyTDsEfg1Gs0iiMSJhR0RCTy+H2w4iX44hEo85jnTr3GvGw8Pt3S0kTCQa6njO+yC/g2az/fZu/nhWvPwB3jtKQWBR0RiSzZ38And0LOavO4eU8Y8SRk9ra2LpEQVVrhY81OD99mFfBd9n6+y95PjqesRp/vsz0M6GjNfyIUdEQkMhTnw7yHYNWr5rErCYY8YG7fYD+2zYBFIpXfb7A1v5hvs/YHRmx+yi3E56+5mbfdBp2buzm1dTKnZibTuXmiRRUr6IhIuPP7YNVUmPswlO03z51yNZz3MCRoM2CRo9lTWMbqbA+rs/ezesd+Vmfvx1tWdVi/pokuM9S0TuGUzGR6ZCQR72ocEaNxVCEiUh92rjSvptr1rXncrLv5MVXrPtbWJdIIFZdX8f0OTyDQrM7ez66ffQQF4Iqy0yMjqUawaZEUg62RTuBX0BGR8LM/C754FL5/BzDA5YZz7jP3p3Lonz2Riio/P+V6+X6Hh+937Gd1toeNewr52SdQ2GzQqWkivTKT6JWZTK9W5sdQTkforBCu33gRCR8l+2Dhk+YmnL4K81zPsTD0EUhsZm1tIhap8vnZtLcoEGq+3+Hhp5xCKnz+w/q2TIrhlNZmoOmVmUz3jCQSGslHUMcrtKsXEQGoLDPDzcK/H7xcvO1Ac3+qjNOsrU2kAfn9Btvyi1mz08PqbDPY/LDLS2ml77C+yXFOemQkBUJNr1ZJNHXHWFB1/VLQEZHQ5ffDmnfMj6k82ea5pl3NgHPSeVr0T8LaoaFm7U4Pa3Z6+GGnl8LywycLJ7ii6J7hpmerZHq2SqJnRjKZqbGNdl5NMCnoiEho2jQP5j4IudXbNiS2hHPvh15X6nJxCTvHEmpcUXa6tTwk1LRKpn16PHZ7+Iea2ijoiEhoyVkNnz8IW740j11uGHA79LkRnLHW1iYSBD6/wZa9RazdZYaZA/dHCjVdW7rpkZFE94wkemQk0bFpAlEhNFm4vinoiEhoyNsI8/8Ga94FDLA7ofdvYeBdEJ9mdXUix6W8ysfG3UWs3enhh11mqPkxx0tZ5eEThRVqjo+Cjog0bnt+ggVPwA/Twaj+x7/7GPNjqtR21tYmcgyKyqv4KcfLD7u8/LDLw9qdXjbuKaTSZxzWNy7aQdcWbrpnJAXCjULN8VHQEZHGKXetGXDWfQBUvxF0uhAG3wMtT7W0NJGjMQyDPYXlrNvlZV2OGWrW7fKyLb+k1v5JsU66Z7jp3tIMNd0zkmibFo8jQufUBJuCjog0Lru+MwPOTx8dPHfyxXD2H6FFL8vKEqlNlc/PtvxifqgONet2mbf84opa+zd3x9C1pTswWtM9w01GcmRc/WQVBR0RaRx2rIQFf4MNc6pP2KDbpXD2XdCsm6WliQB4Sir5MdfLjzkHboVs2F1IedXh82nsNujQJCEQag7cpyW4LKg8sinoiIi1spbB/L/C5nnmsc0OPS6HgXdCk87W1iYRyVd9KfdPOYWHhBpvrfs+AcQ6HXRunki3lm66VX/81LlZIrHRWuagMVDQEZGG5/fDxk9hyX9g20LznM1hroEz8E5I62BtfRIx8orKWZ9rBpr1uYWs322O0tR21RNARnIsJ7dw07VFIl1auDm5hZs2qXERu0ZNKFDQEZGGU14E370Jy56DfVvMc3YnnDLOXAtHV1FJPSmt8LFxTyE/5RayPreQn3LNYJNXVPtcmhinnc7NEjm5Osyc3MJN5+aJJMU6G7hyOVEKOiJS//Znm3tRrZp6cC+qmCQ4fQL0vgGSWllanoSPSp+fbXnF5shMYISmiO35xYftzA3mLiFtUuPo3DyRzs3dnNw8kc7NE2mjq57ChoKOiNSf7OWw9FlY9yEY1ZsKpnYwVzHudRW4EqytT0KW32+wo6A08FHT+lzzfvPeolrXpQFIjY+mc7NEurRIpEt1sOnULIG4aL0VhjO9uiISXL5Kc+2bpc/BzhUHz7cbBH0nwklDwa5Fz6RuDgSaDbsL2biniI17Ctm4u4hNe4pq3ZEbID7aQcdmiXRulkin5tX3zRJokujSZdwRSEFHRIKjMBe+fR1WvATeneY5hwt6Xg59btIl4nJUPr9B1r4SNlYHmk17igIjNEeaGBwdZadj0wQ6NUukU7NEOjc321qXRg6loCMix89XBZs+h1WvwoZPD348Fd8UzvwNnHEdJDSxtkZpVMqrfGzNK2ZTdZg5cNuSV0xFLevRgBloOjRJoFOzBDo2TaBjs0Q6Nk3QPBqpEwUdETl2+7aYozffvgFFuQfPt+4Lp10L3UdDlBZGi2Tesko2Hwgye4sC7ax9JbVOCgZz08qTmtYMMx2bJdI6NU6BRo6bgo6I1E1lmbktw6pXYev8g+fj0uGUq+DUX0GTTtbVJw3O5zfYWVDK5jwzyGzJK2bL3iI27y1mb2H5Eb8uMSaKk5omcFKTBPO+aQIdmiSQqUAj9UBBR0SObvc6M9x8Pw1KC6pP2qDDuXDar6DzcIiKtrREqV/eskq27i1mS14Rm/ccvN+af+SPmwCaJroCQebQYKNJwdKQFHRE5HCeHbB2Oqx9D3JWHzzvbgWnjodTr4bk1tbVJ0FXVukja18JW/YWszWvmK15RdX3xUdcVA8g2mGnXXo87ZvE06FJAu2bxNO++t4do8X1xHoKOiJiKtoL62bC2vcha8nB8/Yo6HyhOfemw7lg1/49oarK52dHQSnb8ovZllfMtvwStlSHmh0FpRhHmDsD0CTRRfv0eDo0TQjcd0hPICMlVh83SaOmoCMSyUr3w4+zzHCzdT4YBz6GsEGbftD9Muh6CcSnW1mlHIPKn4WZ7fklgfaOglKqjjQTGEh0RdG+STzt0uNpl55AuybxtE+Pp216PAkuvV1IaNLfXJFIU1EM62eb4WbTXPAd8rFEy9OgxxjoOgqSMiwrUY7uwMdM2/KKydpXwvb8ErbvKyErv5jsglJ8RwkzMU47bdPiaZMWR9v0eDpUB5p26fGkxUdr7oyEHQUdkUhQnGeuc7P+E9j8BVSWHHysaVdz5Kb7aEhtb12NEmAYBvtLKtm+r4Tt+cVkBYJMCdv3FbPbe+QrmuBgmGmbFk+b9DjapcXTJs0MM00TXdppWyKKgo5IODIM2PuTOXKzYY655xSH/C8/pV11uLkMmnW1rMxIVlbpY0dBKdkFJWRXh5jsghKy9pWSva+EovKqo359YkwUbdLiaJNqjs60SYujdarCjMjPKeiIhAtfJWxfXB1uZkPBtpqPt+gFnS40Jxa36GVu2yz1psrnJ8dTxo6CUnYUlNQMNftKfnFUBszLs80QE0+b1DhaH9JOjnPqYyaROlDQEQllxXmw+Usz2GycC+Weg485XNDubDPYdLpAc26CrMrnJ9d7IMiYozCHhppcb9lR58qAuflkZmocrVPjDrmPpXVqHK1S4ohx6go3kROloCMSSsqLzFGbrfNhy1ewe23Nx+PSzVDT+QJofw64EiwpMxyUVFSxs6CUnfurbwWl7DqknestO+JWBgdEO+xkpMTSKiWWVilxtEqJrRFqUjQqI1LvFHREGrOqCti5ArZUB5udK8D/s7kbTbtBp2Hmx1KtztA6N3VQ5fOzp7CcHE8pu/aXBe4PBJld+0spKKn8xe/jdNjISD4YYjJT46pDjXmuSYLmyohYTUFHpDHx+2D3D9UjNvPN0ZvK4pp9kttA+0HQrvqm3cFr8PsN8orLyfWUkeMpI2d/KTmeMnZW3+fsL2V3YfkvfqwE5royGSmxZCTH0jI5tka7VUqsgoxICFDQEbFS6X7YsQKyl8GO5bBjJVQU1uwTl27OtTkQblLbWVJqY1Dp87PbW8ZurxliDoSZXK/ZzvWYjx1tUbwDouw2mrljaJkcQ8vkWFokxZrtpOpAkxKrLQxEwoCCjkhDMQzI32SGmuxlkP0N7P3x8H7RidCmrxlq2g8217mx2xu83Ibk9xvsK6kIhJjd3vJa2/nFFUfdpuAAu83csqC5u2aIaZEUS4vkGDKSY0lPcGnrApEIoKAjUl8KcyHne3NTzB3fmCM2gd2/D5HaHjLPgsze0Ko3ND05bObZVPn85BdXsMdbzt6iMvZ4y9lTWM6ewrLqc+XV58qo9NUhwWDOi2nmjqFFUgzNk2JpkRRzyLF53yTBRZQjvMOhiNSNgo7IifL7oWCrGWhy10Du92bAKd5zeN+oGHObhczeZrhpdWbIzbExDANPaSV5RWZoySuqYG9hOXlF5eQVmuf2Vt/nF5fXaQQGzGV90uJdNHObIzFN3TE0c7to5o6pPnbRNDGGtPhozYsRkTpT0BE5FhXFkLfRvKw753sz1OSuPXxeDYDNDmkdoUVPM9y0Pgua9YCo6Iav+xdU+fzsK6kgv6j6VmwGmPyi6gBTVEFeUXkg0NR19AXMj5HSE1yBoNI00UXTRBdNEl00STQDTHN3DE0SXTg1CiMiQaagI1Kbkn2wdz3krYe9Gw7ee7Jq7+9wmVspNO9pBpvmvaBZN4iOa9i6q5VX+dhfUkl+UQUFJRXsK655OzTI5BdXsL8Ol1L/nDsmiiaJLtITXKQnumiSUB1eElw0cbuqA00MqfHRmgsjIpZR0JHIVVkGnmxzq4T8TdXBZoN5X5J35K+LTTUnCLfoeTDYpHcCR/1coVNWaYaWghIztBxo7y+ppKC4goLq4/ziCvO4uILCX9gnqTZ2G6TGR5MW7yItIZq0BBdp8dGkxUdXj74cDDXpCdG4osJjHpGIhDcFHQlffj8U7TaDTME22L+9ul19X7jr6F+flGkGmPRO0KQTpHeGJp0hPv2YSzEMg5IKH57SSvaXVOIprcRTWhFo7y+tPld9fCDI7CuuoLTSdxxPHhx2GylxTlLjo0mJiyYtwbxPjY8mPaE6zMSboSU1PprkOI28iEj4CYugU1ZWxt69e2nWrBnR0Y1v/oPUA7/fHHXx7oLCnEPuc8wA49lhBhrfL2ycGJ1gLsCX2s4MMemdzVCT1rHG9gmGYVBa6aOwrIrCPUV4yyrxllbiLauqvq/EW1oVOO+pfqyw+jFPaeUxzWv5OYfdRnKsk+Q4JylxZihJiXOSEh9NcpyTtFrCjDvGqUm7IhLxQj7oPPjggzzxxBPExsZSWVnJ5MmTueWWW6wuS46HYUC519yosjjPDDIH7ov2mgHGm2MGmsJc8P/yvBLD5sBwt6LC3ZryhFYUxbXC68qgwNWSvVHNKTASKa70mwHGW0nR3ioKv62iqGwN3rJKCsuqKCo3b3VZSfeXOB02kmLNcJIU6yQ51rxPOvQ4zlkdZMwwkxwXTaIrSqFFROQ4hHTQee2113jiiSeYO3cu/fr148MPP2T06NF06dKFoUOHWl1e5PL7oaIIyvZDmaf2W+n+6iCzF6M4D4rzoSQPWx3CS+DHYKMwKpUCRzr59lT2kEqukUqOP4WsqmQ2VqSzrSoFX6kDdv/8q6uAHcf81Ow2SIxx4o6Nwh3jNG8H2rGHHyfFOkmMiTJDTJyTWKdDmziKiDQgm2HUdZWLxqdfv3506NCB1157LXDunHPOISUlhenTp9fpe3i9XpKSkvB4PLjd7voqtfHx+6CqDKrK8VWUUlVRSmV5KVXlpfgqyvBVllJVVoy/vBB/eQlGeSFGRbF5eXVFMfbKEmyVJdirinFUluDwleCsLMRVVYTLV4Qd/3GXVmTEsM9IZB9u8g03+4xE8kki10gh10hld/X9XpKoqmNWj3bYSYiJIt7lID46igRXVPVxFAnR5n1ijHlzxzhJqG4nuKJIjHEGHlNQERFpHOr6/h2yIzp+v59Vq1Yxfvz4GucHDBjA1KlTLarqoBWz/kfV/p1gGBiGHzDA8BNYPa26bTP8GIHH/Nj8vuq2r7ptHtsMH7YD5wPHPuz+KuxG9a267TCqcBiVOPBVt6uIwkeUUUk0FURTiZODE1wd1TdXkP8Myo0ovMTjMeLxEoc3cB+Hl3gzwBju6kCTyD7DTVFUMvboWGKdDmKdDmKcDmKjzXa8y0FcdBRdox2c6YqqcS4u2rw/9DjBZQaVeFcU0VFan0VEJBKFbNApLCykvLyctLS0GufT09PJyzvypcHl5eWUlx+coOr1euulvsTVL9G56qd6+d7BVmk4KMcZuFUQTQVOymwxlNliKLfFUG6PpcIeS6U9lkpHHJVRcfgcsfii4vBFxeGPisPncmO43PhdSdhik3C64nA5Hbii7MQ4HcRE2Ul2OmhWfRwXXTPIxDgduupHRESCKmSDjr16k8PKyppzOioqKnA4jry+x+OPP87DDz9cr7UB7MsYzDf724DNjoHNXN+++t6w2avb1aMMgT52s213gM1h7ndUfW+zOTDsDmx2+8Fzdgc4orHZndiinOCIwmaPxh7lxOYwbw5nNDaHE7vDicMZgz06hihXLA5nLFExsURFxxDtjMbpsJPgsJFit2vSq4iIhI2QDTqJiYkkJSWRm5tb43xubi6tWrU64tdNmjSJO+64I3Ds9XrJzMwMen19f/3XoH9PEREROTYhPXFh8ODBfPrppzXOzZ49m8GDBx/xa1wuF263u8ZNREREwlNIB5377ruPBQsW8Oc//5lvvvmGiRMnkp2dzZ133ml1aSIiItIIhHTQOfPMM/nss8/45ptvmDBhAjt37mT+/PmcdNJJVpcmIiIijUBIr6MTDBG7jo6IiEgIq+v7d0iP6IiIiIgcjYKOiIiIhC0FHREREQlbCjoiIiISthR0REREJGwp6IiIiEjYUtARERGRsKWgIyIiImFLQUdERETCVsjuXh4sBxaG9nq9FlciIiIidXXgffuXNniI+KBTWFgIQGZmpsWViIiIyLEqLCwkKSnpiI9H/F5Xfr+fXbt2kZiYiM1mO2I/r9dLZmYm2dnZEbEnViQ9Xz3X8BVJz1fPNXxF0vM9ludqGAaFhYW0bNkSu/3IM3EifkTHbrfTqlWrOvd3u91h/xftUJH0fPVcw1ckPV891/AVSc+3rs/1aCM5B2gysoiIiIQtBR0REREJWwo6deRyuXjwwQdxuVxWl9IgIun56rmGr0h6vnqu4SuSnm99PNeIn4wsIiIi4UsjOiIiIhK2FHREREQkbCnoiIiISNiK+HV06sLv97N8+XJyc3Pp1q0bHTt2tLqkerFnzx6++OKLw85feOGFdVqrIBRs3bqV5cuXc9pppx3xdfz+++/ZvHkz7dq145RTTmnYAoOoqKiIzz//nKSkJM4999waj5WVlTFz5szDvmbAgAHHtK5UY7Fz505Wr15NUlISp556KnFxcYf1KS8v5+uvv6aoqIjevXvTvHlzCyo9cUVFRaxatYrS0lJ69uxJixYtajy+YcMGVq1aVeOc3W7niiuuaMgyg2bz5s2sW7eOtLQ0zjzzTJxO52F9cnNzWb58OQkJCfTv3z9kJ+0WFBSwYsUKbDYbPXv2pGnTpjUenzdvHnv37q1xrk2bNvTt27chywyqoqIiPvroI1q0aMGgQYMOe3z16tVs2bKF9u3b06tXr+P7IYYclcfjMfr162e0bNnSGDp0qBEfH2/ceeedVpdVL7788ksDMK644gpj7NixgVt2drbVpZ2wNWvWGBdeeKHRrl07w+l0Gs8888xhfaqqqoyxY8caycnJxrBhw4zU1FTj0ksvNSoqKiyo+PiVlZUZEydONFq0aGG0bNnSGDRo0GF9cnJyDMC44IILarzWS5cubfiCT0B+fr4xevRoIzMz0xg+fLjRo0cPo3nz5sa8efNq9Nu4caPRtm1bo3PnzsbZZ59txMXFGS+++KJFVR+/xx57zMjIyDAGDhxoDB061IiNjTXuv//+Gn2eeuopIykpqcbrOm7cOIsqPn47d+40hg0bZnTp0sUYOXKk0alTJyMjI+Owv6MvvviiERcXZwwaNMjo1KmT0bZtW2Pjxo0WVX387r33XiMzM9O44IILjIEDBxqxsbHG5MmTa/Tp37+/0a1btxqv7T//+U+LKg6Oa665xoiOjjbOP//8GucrKyuNMWPGGCkpKcawYcOMlJQUY8yYMUZlZeUx/wwFnV9w2223GR06dDAKCgoMwzCMxYsXGzabzZgzZ461hdWDA0HneP4iNXaLFi0yPv74Y8Pn8xlJSUm1Bp3nnnvOcLvdxqZNmwzDMIytW7caycnJxtNPP93Q5Z6QwsJC45lnnjH2799vXH/99UcNOmvWrGn4AoMoKyvLeP/99w2/3x84N3HiRCM9Pd3w+XyBc4MGDTKGDRtmVFVVGYZhvtbR0dHG9u3bG7zmE/Hiiy8aHo8ncPzFF18YQI1g99RTTxndunWzoryg2rBhg/H111/XOHfJJZcYvXv3Dhxv27bNiI6ONqZMmWIYhvmflSFDhhiDBw9u0FqD4Y033qjxn6o333zTAIzNmzcHzvXv39948MEHLaiufkydOtU466yzjMsuu+ywoPPMM88YycnJxtatWw3DMIzNmzcbbrfb+Pe//33MP0dzdH7BG2+8wXXXXUdycjIAffv2pW/fvrz++uvWFlaPvvjiCz755BO2bt1qdSlB079/f4YPH37U/VBef/11LrnkEjp06ABA27ZtGT16dMi91gkJCdx88811+rjxm2++4cMPP2TdunUNUFnwZWZmMnr06Br71I0ePZq8vDx27NgBwI4dO5g/fz633XYbDocDgOuvv564uDjeffddS+o+Xtddd12NZfHPOeccUlJS+O6772r0Kysr45NPPuHzzz9n9+7dDVxlcHTs2JF+/frVONepU6fARswA7777LvHx8UyYMAEAh8PBbbfdxldffRV4/UPFuHHjanws17lzZ8D8aOdQO3bsYMaMGSxdupTS0tIGrTGYNmzYwD333MPrr79OVNThs2hef/11Lr30Utq2bQtA+/btGTVq1HH9e6w5OkeRk5NDXl4e3bt3r3G+R48eLF261KKq6pfT6eSRRx7B6XSyZMkSLrvsMl566SWio6OtLq3erVmzhpEjR9Y416NHD9544w2LKqpfNpuN//znP6Snp7N06VJOP/10pk2bRpMmTawu7YTMnTuX5ORkMjIyAPN1BWr8HjudTjp37hx4LFStWrWKgoKCw/6N2r17N08//TRFRUWsXLmSSZMm8dBDD1lT5An67LPP2Lt3L+vWreOtt97ihRdeCDy2Zs0aunTpUuONskePHgCsXbs25OabrV+/nm+//ZY9e/bw/PPPc9ttt9GzZ88afT777DNyc3P58ccfKS8v59VXXz1sDl5jV15ezpVXXsnkyZM56aSTau2zZs2aw+aV9ejRg/fff/+Yf56CzlF4PB4AUlNTa5xPS0tj//79FlRUvzIzM1m7di2dOnUC4KeffqJPnz5MnjyZhx9+2OLq6pdhGHi93lpf6/LycsrKyoiJibGouuCLi4tj0aJFgf8x79mzhwEDBnDzzTfz9ttvW1zd8Vu4cCFPPvkkTz/9dGD0Jlx/j71eL9dccw1Dhgxh6NChgfP9+vVj27ZtpKWlAfDJJ59w0UUX0atXLy699FKryj1u8+fP58cff+T777+nffv2tG7dOvCYx+Op9XUFQvK13bhxIzNmzGDnzp0UFhZy6qmn1nj8gQceYOjQodjtdnw+HzfddBNjx45lw4YNpKSkWFT1sbv77rtp164d1113Xa2PV1VVUVJSUutrW1xcTFVVVa2jQEeij66O4sDM/Z8PHRYVFYXVm94BHTp0CIQcgC5dunD11Vcza9YsC6tqGDabjejo6Fpf6wOPhRO3213jY4GmTZtyyy238PHHH2OE6GLpK1euZOTIkdx8883ceOONgfPh+HtcXFzMiBEjiI6O5t13363x0V3v3r0Db/YAw4cPp2/fviH7ezx58mSmT5/Ohg0baN++PSNGjMDn8wHma1vb6wqE5Gt70UUX8fbbb7No0SKee+45JkyYwOLFiwOPn3/++YGP3x0OBw899BB5eXksWbLEqpKP2bfffsuzzz7LkCFDmDZtGtOmTSMrK4vc3FymTZuGx+MhKioKh8NR62sbFRV1TCEHFHSOqlWrVkRHR5OVlVXj/Pbt22nfvr1FVTUst9t92OWM4apDhw61vtZt27Y96tyecOF2uykuLqakpMTqUo7ZqlWrGDp0KBMmTODJJ5+s8diBOVc/f22zsrJC8vf4QMjxer3MnTu3Tv+TD4ffY7vdzrhx49i6dSs7d+4Ejvw7C4Tka3uo4cOHk5qayqJFi47YJzExESCkXlun08lll13GggULmDlzJjNnzmTnzp3s3r2bmTNnBuZgtW/fvtbXtl27dsf8M8P/X+8T4HQ6GTp0aI0Ji/v27WPu3LmMGDHCwsrqR05OTo3jyspKZs2axZlnnmlRRQ1r+PDhfPDBB1RUVADm858xY0ZEvNYA06dP5+STTyY+Pt6Cio7fd999x9ChQ/nVr37FU089ddjjPXr0IDMzs8bv8bJly9i2bVvIvbYlJSWMGDGCgoIC5s2bV2Pk5oCfv7a5ubksWbIk5H6Pa/s7unLlSmJiYkhPTwfM39mtW7eycuXKQJ+3336b1q1bB+bqhAKPx3PYxOKtW7dSUFBAZmYmYH5U+fP/hMyYMQOAM844o2EKDYLu3bsHRnIO3Pr27UuvXr2YNm1aYF7V8OHDmTlzJpWVlQBUVFQwc+bM4/qd1RydX/D444/Tr18/rr76avr3789LL73ESSedxPXXX291aUH32GOPkZOTE1i06bXXXmPfvn089thjFld24goKCvj0008BM8CsWrWKadOmkZmZSf/+/QHzc+N33nmHESNGMHr0aD744AMKCwuZNGmSlaUfl1mzZlFcXMyWLVvYs2cP06ZNA+DKK68E4L333mPGjBkMHz6cxMREPvjgAxYtWsT06dOtLPuYZWVlcd5559GyZUv69OkTeJ4AQ4cOJS0tDZvNxlNPPRV47hkZGfzjH/9g7Nixgdc+VIwZM4Zly5bx97//nblz5wbOd+nSJbC45fjx4+nQoQNnnHEG+/fv59lnn6V9+/bcdtttFlV9fN544w0+//xzhg0bRnJyMitWrODll1/m//7v/wILQg4YMIArrriC0aNHc/vtt7Njxw6eeeYZ3nnnnRof5zV2OTk5XH755Vx66aW0b9+eHTt28PzzzzNw4EDGjBkDmBPMR40axejRo2nXrh1r1qzhv//9L3fddRfdunWz+BkE35/+9Cfee+89LrroIkaNGsWMGTMoKyvjnnvuOebvpd3L62DTpk1MmTKF3Nxcunfvzo033khCQoLVZdWL2bNn8+mnn1JRUUHXrl2ZMGFCWDzXLVu2cO+99x52vk+fPvzhD38IHO/Zs4fnnnsusDLyjTfeGJIr6N5yyy21DmcfGgSWLVvGjBkzyM/Pp2PHjlx77bU0a9asIcs8YevWreMvf/lLrY89+uijNa7oWLp0KW+88QZFRUUMHDiQa6+9NjBhOVTccMMNeL3ew85ffPHFXH311YA5kfOtt95i8eLFuFwuTj/9dMaNGxdyzxVgyZIlfPDBB+Tl5dG6dWuuuOIKunTpUqOPz+dj6tSpLFy4kISEBK6++mr69OljUcXHb/fu3UydOpWffvqJtLQ0BgwYwMiRI2sEtt27d/PKK6+wYcMGWrRowYgRI0J6VeQD/vWvf1FSUsKf/vSnGud3797Nc889F1gZ+cYbbzyuf6MUdERERCRsaY6OiIiIhC0FHREREQlbCjoiIiISthR0REREJGwp6IiIiEjYUtARERGRsKWgIyIiImFLQUdERETCloKOiIiIhC0FHREREQlbCjoiIiISthR0REREJGz9P8+h7yoYAQluAAAAAElFTkSuQmCC", "text/plain": [ "
" ] }, "metadata": {} } ], "id": "72824199-f660-4e94-afee-eb30fe9ae63a" }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Вставки и выбор\n", "\n", "Две картинки, не два доказательства. Оба в худшем случае $\\Theta(n^2)$ сравнений. Вставки обычно дешевле на почти упорядоченном входе: новый элемент почти никуда не едет. Выбор адаптивным не бывает: он каждый раз смотрит весь хвост.\n", "\n", "Доказать корректность **одного** из двух (какой — решает монетка) — [домашнее задание к лекции](https://learn.ai.msu.ru/algo/1/03/hw-lecture/). Код туда не пишите. Полные циклы — на семинаре; здесь только один шаг, чтобы было видно инвариант.\n", "\n", "### Выбор\n", "\n", "**Инвариант (один, его и держим):** префикс длины $k$ содержит $k$ наименьших элементов массива.\n", "\n", "Каждый шаг: в хвосте находим минимум и меняем его с элементом на границе префикса. Префикс удлиняется на единицу.\n", "\n", "### Вставки\n", "\n", "**Инвариант:** префикс длины $k$ уже упорядочен.\n", "\n", "Новый элемент «въезжает» на своё место сдвигами вправо тех, кто больше него. Префикс снова упорядочен, только длиннее.\n", "\n", "" ], "id": "ins_sel" }, { "cell_type": "code", "metadata": {}, "source": [ "a = [4, 1, 3, 2]\n", "print(\"выбор, до шага: \", a)\n", "j = 1 # минимум хвоста [4, 1, 3, 2] стоит на месте 1\n", "a[0], a[j] = a[j], a[0]\n", "print(\"выбор, префикс k=1:\", a)\n", "\n" ], "execution_count": 1, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "выбор, до шага: [4, 1, 3, 2]\n", "выбор, префикс k=1: [1, 4, 3, 2]\n" ] } ], "id": "sel_step" }, { "cell_type": "code", "metadata": {}, "source": [ "a = [4, 1, 3, 2]\n", "print(\"вставки, до шага: \", a)\n", "# префикс [4] упорядочен; 1 въезжает, 4 сдвигается вправо\n", "a[1] = a[0]\n", "a[0] = 1\n", "print(\"вставки, префикс k=2:\", a)\n", "\n" ], "execution_count": 1, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "вставки, до шага: [4, 1, 3, 2]\n", "вставки, префикс k=2: [1, 4, 3, 2]\n" ] } ], "id": "ins_step" }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Нижняя оценка в модели сравнений\n", "\n", "Представим, что алгоритм умеет только спрашивать «$a_i < a_j$?» и ветвиться по ответу. Каждая перестановка входа — отдельный лист в дереве таких вопросов: иначе два разных порядка получили бы один и тот же ответ.\n", "\n", "Листьев нужно не меньше $n!$. Высота дерева (число вопросов в худшем случае) не меньше $\\log_2(n!)$. По формуле Стирлинга это $\\Omega(n\\log n)$. Вывод Стирлинга не разбираем: достаточно «логарифм факториала растёт как $n\\log n$».\n", "\n", "Следствия:\n", "\n", "- пузырёк, вставки, выбор в этой модели **не оптимальны по порядку**: они $n^2$, а нижняя оценка только $n\\log n$; Fool в записи выше ещё хуже, куб;\n", "- **сравнениями** быстрее $n\\log n$ в худшем случае нельзя;\n", "- подсчёт в эту модель **не входит**: он не спрашивает «$a_i < a_j$?», а использует, что ключ — небольшое целое и годится как индекс.\n", "\n", "" ], "id": "omega" }, { "cell_type": "code", "metadata": {}, "source": [ "from math import factorial, log2\n", "\n", "for n in (4, 8, 16):\n", " print(\n", " n,\n", " \" n! =\", factorial(n),\n", " \" log2(n!) ≈\", round(log2(factorial(n)), 1),\n", " \" n log2 n ≈\", round(n * log2(n), 1),\n", " )\n", "\n" ], "execution_count": 74, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "4 n! = 24 log2(n!) ≈ 4.6 n log2 n ≈ 8.0\n", "8 n! = 40320 log2(n!) ≈ 15.3 n log2 n ≈ 24.0\n", "16 n! = 20922789888000 log2(n!) ≈ 44.3 n log2 n ≈ 64.0\n" ] } ], "id": "omega_code" }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Сортировка подсчётом\n", "\n", "Если ключи — целые из **известного малого диапазона** (например, от $0$ до $U$), индекс массива снова может значить *значение*, как частотный массив на семинаре 2.\n", "\n", "Сначала сводка: сколько раз встретился каждый ключ $v$. Затем выписывание: значение $v$ повторяем столько раз, сколько насчитали. На доске достаточно этой картинки; цикл выписывания соберёте на семинаре.\n", "\n", "Время $\\Theta(n + U)$. Путать $n$ и $U$ нельзя: длина входа и размер диапазона — разные величины. Если $U$ порядка $10^9$, массив частот не построите.\n", "\n", "" ], "id": "count" }, { "cell_type": "code", "metadata": {}, "source": [ "a = [3, 1, 3, 2, 1, 3]\n", "U = 4 # ключи 0, 1, 2, 3\n", "cnt = [0] * U\n", "for x in a:\n", " cnt[x] += 1\n", "print(\"вход: \", a)\n", "print(\"сводка:\", cnt)\n", "print(\"ключ 1 встретился\", cnt[1], \"раза\")\n", "\n" ], "execution_count": 1, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "вход: [3, 1, 3, 2, 1, 3]\n", "сводка: [0, 2, 1, 3]\n", "ключ 1 встретился 2 раза\n" ] } ], "id": "count_code" }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Устойчивость и ключ\n", "\n", "**Устойчивость:** элементы с равными ключами остаются в том же относительном порядке, что и во входе.\n", "\n", "Она нужна, когда у равных ключей есть **полезная нагрузка** (имя, исходный индекс) и когда следующий проход не должен ломать предыдущий — именно так складывают стопку в LSD.\n", "\n", "**Ключ** — то, по чему сравнивают. Это не обязательно весь элемент: у пары $(k, p)$ ключом может быть только $k$. Если сравнивать пары целиком, нагрузка $p$ вмешается.\n", "\n", "" ], "id": "stable" }, { "cell_type": "code", "metadata": {}, "source": [ "# (ключ, имя). При равном ключе имена должны идти как во входе.\n", "pairs = [(2, \"Боря\"), (1, \"Аня\"), (2, \"Вика\"), (1, \"Гена\")]\n", "print(\"вход: \", pairs)\n", "\n", "# устойчиво по ключу: Аня раньше Гены, Боря раньше Вики — как во входе\n", "stable = [(1, \"Аня\"), (1, \"Гена\"), (2, \"Боря\"), (2, \"Вика\")]\n", "print(\"устойчиво:\", stable)\n", "\n", "# ключи те же, но пары с ключом 2 переставлены — устойчивость сломана\n", "broken = [(1, \"Аня\"), (1, \"Гена\"), (2, \"Вика\"), (2, \"Боря\")]\n", "print(\"сломано: \", broken)\n", "\n" ], "execution_count": 1, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "вход: [(2, 'Боря'), (1, 'Аня'), (2, 'Вика'), (1, 'Гена')]\n", "устойчиво: [(1, 'Аня'), (1, 'Гена'), (2, 'Боря'), (2, 'Вика')]\n", "сломано: [(1, 'Аня'), (1, 'Гена'), (2, 'Вика'), (2, 'Боря')]\n" ] } ], "id": "stable_code" }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Поразрядная LSD\n", "\n", "**LSD** (least significant digit) удобнее показывать карточками с дырками и палочкой, чем циклом. Палочка в разряд отделяет «0» и «1»; стопку складывают **устойчиво**: кто был раньше при равной дырке, тот раньше и остаётся. Так работали табуляторы начала XX века.\n", "\n", "Каждый проход — устойчивый подсчёт (или такая стопка) по одной цифре, начиная с младшей. **Инвариант** после $k$ проходов: порядок правильный по $k$ младшим разрядам.\n", "\n", "Не обещаем MSD и «построим radix на следующей неделе». Цикл LSD — на семинаре, если останется время. Ячейка ниже — тот же приём на трёх битах, не замена карточкам. Подробный разбор (псевдокод, инвариант, время и память) — в `lsd-example.tex`.\n", "\n", "" ], "id": "lsd" }, { "cell_type": "code", "metadata": {}, "source": [ "# четыре числа в трёх битах: 5=101, 2=010, 7=111, 4=100\n", "nums = [5, 2, 7, 4]\n", "print(\"биты: \", [(x, format(x, \"03b\")) for x in nums])\n", "\n", "# проход по младшему биту, устойчиво: сначала все *0 в старом порядке, потом *1\n", "zeros = [x for x in nums if x % 2 == 0]\n", "ones = [x for x in nums if x % 2 == 1]\n", "after = zeros + ones\n", "print(\"после младшего бита:\", after, [format(x, \"03b\") for x in after])\n", "print(\"инвариант: младший бит уже в порядке 0,0,1,1\")\n", "\n" ], "execution_count": 1, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "биты: [(5, '101'), (2, '010'), (7, '111'), (4, '100')]\n", "после младшего бита: [2, 4, 5, 7] ['010', '100', '101', '111']\n", "инвариант: младший бит уже в порядке 0,0,1,1\n" ] } ], "id": "lsd_code" }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Домашнее задание\n", "\n", "Короткий текст в LaTeX: монетка выбирает вставки или выбор. Условие, шаблон и образец — на отдельной странице:\n", "\n", "https://learn.ai.msu.ru/algo/1/03/hw-lecture/\n", "\n", "Сдаёте лектору `.tex` и PDF, не семинаристу.\n", "\n", "" ], "id": "latex" } ], "metadata": { "kernelspec": { "display_name": "Python 3 (ipykernel)", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.12.13" } }, "nbformat": 4, "nbformat_minor": 5 }