Created
November 19, 2025 06:03
-
-
Save Harrix/c221d0cedfa4ef660c7937aa0b23c69a to your computer and use it in GitHub Desktop.
Predprof2025-26.ipynb
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| { | |
| "nbformat": 4, | |
| "nbformat_minor": 0, | |
| "metadata": { | |
| "colab": { | |
| "provenance": [], | |
| "toc_visible": true, | |
| "authorship_tag": "ABX9TyNkDmRZM8unNR70CSyHggLN", | |
| "include_colab_link": true | |
| }, | |
| "kernelspec": { | |
| "name": "python3", | |
| "display_name": "Python 3" | |
| }, | |
| "language_info": { | |
| "name": "python" | |
| } | |
| }, | |
| "cells": [ | |
| { | |
| "cell_type": "markdown", | |
| "metadata": { | |
| "id": "view-in-github", | |
| "colab_type": "text" | |
| }, | |
| "source": [ | |
| "<a href=\"https://colab.research.google.com/gist/Harrix/c221d0cedfa4ef660c7937aa0b23c69a/predprof2025-26.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "# Задача 1" | |
| ], | |
| "metadata": { | |
| "id": "0zKZosYxVU-6" | |
| } | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "Дана строка, состоящая из 12 нулей и 12 единиц, расположенных в случайном порядке. За одно алгоритмическое действие можно поменять местами две рядом стоящие цифры. Какое наименьшее количество действий потребуется, чтобы все единицы гарантированно* следовали друг за другом (не обязательно в начале или в конце строки)?\n", | |
| "\n", | |
| "*Подразумевается, что количества действий, указанного в ответе, хватит для любого начального распределения." | |
| ], | |
| "metadata": { | |
| "id": "i0Sj7fpcWBsq" | |
| } | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "## Решение 1" | |
| ], | |
| "metadata": { | |
| "id": "ksC_VuuQYKEu" | |
| } | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "import itertools\n", | |
| "\n", | |
| "def min_swaps_to_group(ones_positions):\n", | |
| " # p_i строго возрастают, поэтому a_i = p_i - i тоже неубывают — сортировка не нужна\n", | |
| " a = [p - i for i, p in enumerate(ones_positions)]\n", | |
| " # Для 12 единиц медиана — любой s между a[5] и a[6]\n", | |
| " # Берём любой целый внутри (например, середину)\n", | |
| " s = (a[5] + a[6]) // 2\n", | |
| " return sum(abs(x - s) for x in a)\n", | |
| "\n", | |
| "def worst_case_for_24_with_12_ones():\n", | |
| " n = 24\n", | |
| " k = 12\n", | |
| " max_cost = -1\n", | |
| " worst = None\n", | |
| " for ones in itertools.combinations(range(n), k):\n", | |
| " cost = min_swaps_to_group(ones)\n", | |
| " if cost > max_cost:\n", | |
| " max_cost = cost\n", | |
| " worst = ones\n", | |
| " return max_cost, worst\n", | |
| "\n", | |
| "if __name__ == \"__main__\":\n", | |
| " max_cost, worst = worst_case_for_24_with_12_ones()\n", | |
| " print(\"Худшая минимальная стоимость:\", max_cost)\n", | |
| " print(\"Пример расположения единиц (индексы):\", worst)\n", | |
| " # Для наглядности напечатаем строку\n", | |
| " s = ['0'] * 24\n", | |
| " for i in worst:\n", | |
| " s[i] = '1'\n", | |
| " print(\"Строка:\", ''.join(s))" | |
| ], | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "ffrH2uYTYJd4", | |
| "outputId": "4d2dacc5-0a5e-47be-b612-d75606da570e" | |
| }, | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "name": "stdout", | |
| "text": [ | |
| "Худшая минимальная стоимость: 72\n", | |
| "Пример расположения единиц (индексы): (0, 1, 2, 3, 4, 5, 18, 19, 20, 21, 22, 23)\n", | |
| "Строка: 111111000000000000111111\n" | |
| ] | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "## Решение 2" | |
| ], | |
| "metadata": { | |
| "id": "ckCtbxDlbp_h" | |
| } | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "from itertools import combinations\n", | |
| "from tqdm import tqdm # pip install tqdm для progress bar\n", | |
| "import math\n", | |
| "\n", | |
| "def count_swaps_to_group_fast(s, start):\n", | |
| " \"\"\"Быстрая версия подсчета обменов\"\"\"\n", | |
| " window_size = 12\n", | |
| " end = start + window_size\n", | |
| "\n", | |
| " # Количество нулей в окне\n", | |
| " zeros_in_window = sum(1 for i in range(start, end) if s[i] == 0)\n", | |
| " # Количество единиц слева от окна\n", | |
| " ones_left = sum(1 for i in range(start) if s[i] == 1)\n", | |
| " # Количество единиц справа от окна\n", | |
| " ones_right = sum(1 for i in range(end, len(s)) if s[i] == 1)\n", | |
| "\n", | |
| " swaps = 0\n", | |
| "\n", | |
| " # Нули в окне, которые должны обменяться с единицами слева\n", | |
| " for i in range(start, end):\n", | |
| " if s[i] == 0:\n", | |
| " swaps += sum(1 for j in range(start) if s[j] == 1 and j < i)\n", | |
| "\n", | |
| " # Нули в окне, которые должны обменяться с единицами справа\n", | |
| " for i in range(start, end):\n", | |
| " if s[i] == 0:\n", | |
| " swaps += sum(1 for j in range(end, len(s)) if s[j] == 1 and j > i)\n", | |
| "\n", | |
| " return swaps\n", | |
| "\n", | |
| "\n", | |
| "# Запуск с progress bar\n", | |
| "max_swaps = 0\n", | |
| "worst_case = None\n", | |
| "total = math.comb(24, 12)\n", | |
| "\n", | |
| "for ones_positions in tqdm(combinations(range(24), 12), total=total, desc=\"Перебор\"):\n", | |
| " s = [0] * 24\n", | |
| " for pos in ones_positions:\n", | |
| " s[pos] = 1\n", | |
| "\n", | |
| " min_s = min(count_swaps_to_group(s, start) for start in range(13))\n", | |
| "\n", | |
| " if min_s > max_swaps:\n", | |
| " max_swaps = min_s\n", | |
| " worst_case = s\n", | |
| "\n", | |
| "print(f\"\\n{'='*60}\")\n", | |
| "print(f\"ОТВЕТ: {max_swaps} обменов\")\n", | |
| "print(f\"Наихудшая конфигурация: {''.join(map(str, worst_case))}\")\n", | |
| "print(f\"{'='*60}\")" | |
| ], | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "OWynVgkQWtwu", | |
| "outputId": "86813a59-a5b7-4e6c-8a90-316926e542bb" | |
| }, | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "name": "stderr", | |
| "text": [ | |
| "Перебор: 100%|██████████| 2704156/2704156 [14:23<00:00, 3133.04it/s]" | |
| ] | |
| }, | |
| { | |
| "output_type": "stream", | |
| "name": "stdout", | |
| "text": [ | |
| "\n", | |
| "============================================================\n", | |
| "ОТВЕТ: 72 обменов\n", | |
| "Наихудшая конфигурация: 000000001101010011111111\n", | |
| "============================================================\n" | |
| ] | |
| }, | |
| { | |
| "output_type": "stream", | |
| "name": "stderr", | |
| "text": [ | |
| "\n" | |
| ] | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "## Решение 3\n", | |
| "\n", | |
| "**1. Модель задачи**\n", | |
| "\n", | |
| "- Пусть в строке длины 24 стоят 12 единиц на позициях $p_1 < p_2 < \\ldots < p_{12}$ (позиции нумеруем, например, от 1 до 24).\n", | |
| "\n", | |
| "- За одно действие можно поменять соседние символы местами; это эквивалентно тому, что «единица перепрыгивает через ноль» (или наоборот).\n", | |
| "\n", | |
| "- Минимальное число таких действий, чтобы собрать все единицы подряд (в некотором блоке из 12 последовательных позиций), равно:\n", | |
| " $$\\min_{k} \\sum_{j=1}^{12} |p_j - (k + j - 1)|,$$\n", | |
| " где $k$ — левая граница целевого блока длины 12.\n", | |
| "\n", | |
| "- Удобно ввести замену переменных: $q_j = p_j - j$. Тогда выражение превращается в:\n", | |
| " $$\\min_{m} \\sum_{j=1}^{12} |q_j - m|,$$\n", | |
| " где $m = k - 1$.\n", | |
| "\n", | |
| " Это — сумма расстояний от чисел $q_j$ до точки $m$, минимизируемая по $m$. Известно, что минимум достигается при $m$, равном **медиане** последовательности ${q_j}$.\n", | |
| "\n", | |
| "**Полезные факты:**\n", | |
| "\n", | |
| "- Последовательность $q_j$ **неубывающая** (поскольку $p_j$ строго возрастают).\n", | |
| "\n", | |
| "- **Ограничения:** $0 \\leq q_j \\leq 12$ для всех $j$.\n", | |
| "\n", | |
| " Действительно:\n", | |
| "\n", | |
| " - $p_j \\in [1, 24]$ и $j \\in [1, 12]$\n", | |
| " - При $j = 1$: $q_1 = p_1 - 1 \\geq 1 - 1 = 0$\n", | |
| " - При $j = 12$: $q_{12} = p_{12} - 12 \\leq 24 - 12 = 12$\n", | |
| " - Монотонность: $0 \\leq q_1 \\leq q_2 \\leq \\ldots \\leq q_{12} \\leq 12$\n", | |
| "\n", | |
| "**2. Что мы ищем**\n", | |
| "\n", | |
| "Ищем **наихудший** начальный случай, то есть максимум по всем допустимым последовательностям $q$ величины:\n", | |
| "$$F(q) = \\min_{m} \\sum_{j=1}^{12} |q_j - m|.$$\n", | |
| "\n", | |
| "**Утверждение:** Максимум $F(q)$ равен 72 и достигается при\n", | |
| "$$q = [0, 0, 0, 0, 0, 0, 12, 12, 12, 12, 12, 12],$$\n", | |
| "то есть 6 нулей и 6 двенадцаток, что соответствует строке:\n", | |
| "$$111111;000000000000;111111$$\n", | |
| "(6 единиц, затем 12 нулей, затем 6 единиц)\n", | |
| "\n", | |
| "**3. Верхняя граница: $F(q) \\leq 72$ для любого расположения**\n", | |
| "\n", | |
| "Пусть $q$ — отсортированная последовательность, $m$ — её медиана, т.е. $m \\in [q_6, q_7]$.\n", | |
| "\n", | |
| "Тогда:\n", | |
| "$$\\sum_{j=1}^{12} |q_j - m| = \\sum_{j=1}^{6} (m - q_j) + \\sum_{j=7}^{12} (q_j - m).$$\n", | |
| "\n", | |
| "Используем оценки $q_j \\geq 0$ при $j \\leq 6$ и $q_j \\leq 12$ при $j \\geq 7$:\n", | |
| "$$\\sum_{j=1}^{6} (m - q_j) \\leq \\sum_{j=1}^{6} (m - 0) = 6m,$$\n", | |
| "$$\\sum_{j=7}^{12} (q_j - m) \\leq \\sum_{j=7}^{12} (12 - m) = 6(12 - m).$$\n", | |
| "\n", | |
| "Складывая:\n", | |
| "$$\\sum_{j=1}^{12} |q_j - m| \\leq 6m + 6(12 - m) = 72.$$\n", | |
| "\n", | |
| "**Вывод:** для любой начальной конфигурации минимальное число обменов $\\leq 72$.\n", | |
| "\n", | |
| "**4. Конфигурация, требующая ровно 72 обмена**\n", | |
| "\n", | |
| "Рассмотрим строку:\n", | |
| "\n", | |
| "$$111111;000000000000;111111$$\n", | |
| "\n", | |
| "(6 единиц, затем 12 нулей, затем 6 единиц)\n", | |
| "\n", | |
| "Позиции единиц: $p_j \\in {1, 2, 3, 4, 5, 6, 19, 20, 21, 22, 23, 24}$.\n", | |
| "\n", | |
| "Тогда:\n", | |
| "$$q_j = p_j - j = \\begin{cases}\n", | |
| "j - j = 0, & j \\in {1, 2, 3, 4, 5, 6} \\\n", | |
| "(18 + j) - j = 18, & j \\in {7, 8, 9, 10, 11, 12}\n", | |
| "\\end{cases}$$\n", | |
| "\n", | |
| "Стоп, пересчитаем:\n", | |
| "\n", | |
| "- $p_1 = 1 \\Rightarrow q_1 = 1 - 1 = 0$\n", | |
| "- $p_2 = 2 \\Rightarrow q_2 = 2 - 2 = 0$\n", | |
| "- ...\n", | |
| "- $p_6 = 6 \\Rightarrow q_6 = 6 - 6 = 0$\n", | |
| "- $p_7 = 19 \\Rightarrow q_7 = 19 - 7 = 12$\n", | |
| "- $p_8 = 20 \\Rightarrow q_8 = 20 - 8 = 12$\n", | |
| "- ...\n", | |
| "- $p_{12} = 24 \\Rightarrow q_{12} = 24 - 12 = 12$\n", | |
| "\n", | |
| "Итак, $q = [0, 0, 0, 0, 0, 0, 12, 12, 12, 12, 12, 12]$.\n", | |
| "\n", | |
| "Медиана — любое $m \\in [q_6, q_7] = [0, 12]$. Выберем, например, $m = 6$:\n", | |
| "$$\\sum_{j=1}^{12} |q_j - 6| = 6 \\cdot |0 - 6| + 6 \\cdot |12 - 6| = 6 \\cdot 6 + 6 \\cdot 6 = 72.$$\n", | |
| "\n", | |
| "**Интерпретация:**\n", | |
| "\n", | |
| "- Чтобы собрать все единицы в середине, нужно протащить 6 правых единиц через 12 нулей: $6 \\times 12 = 72$ обмена.\n", | |
| "- Или симметрично: каждый из 12 нулей должен пересечь минимум 6 единиц.\n", | |
| "\n", | |
| "**5. Почему это худший случай**\n", | |
| "\n", | |
| "Функция $F(q) = \\min_m \\sum_{j=1}^{12} |q_j - m|$ для неубывающих $q \\in [0, 12]^{12}$ максимизируется, когда значения **максимально расходятся** к границам $[0, 12]$.\n", | |
| "\n", | |
| "Поскольку медиана находится между $q_6$ и $q_7$, оптимально:\n", | |
| "\n", | |
| "- Первые 6 элементов прижать к 0: $q_1 = \\ldots = q_6 = 0$\n", | |
| "- Последние 6 элементов прижать к 12: $q_7 = \\ldots = q_{12} = 12$\n", | |
| "\n", | |
| "Это даёт максимальную сумму расстояний до любой медианы:\n", | |
| "$$\\sum_{j=1}^{12} |q_j - m| = 6|0 - m| + 6|12 - m| = 6m + 6(12 - m) = 72$$\n", | |
| "для **любого** $m \\in [0, 12]$.\n", | |
| "\n", | |
| "**6. Интуиция**\n", | |
| "\n", | |
| "- В **чередующейся** строке $010101\\ldots$ стоимость составляет всего 36 обменов — «разрывы» между единицами маленькие.\n", | |
| "\n", | |
| "- **Худший случай** — два «жирных» кластера единиц, разделённых длинной цепочкой нулей. Каждый из 12 нулей обязан пересечь минимум 6 единиц: $12 \\times 6 = 72$.\n", | |
| "\n", | |
| "**Итог**\n", | |
| "\n", | |
| "Чтобы гарантированно (в худшем случае) собрать все 12 единиц подряд в строке из 24 символов (12 нулей и 12 единиц), требуется и достаточно **72 обмена** соседних элементов.\n", | |
| "\n", | |
| "$$\\boxed{72}$$" | |
| ], | |
| "metadata": { | |
| "id": "gkxTdvhqcv6h" | |
| } | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "# Задача 1-2\n", | |
| "\n", | |
| "Дана строка, состоящая из 10 нулей и 10 единиц, расположенных в случайном порядке. За одно алгоритмическое действие можно поменять местами две рядом стоящие цифры. Какое наименьшее количество действий потребуется, чтобы все единицы гарантированно* следовали друг за другом (не обязательно вначале или в конце строки)?\n", | |
| "\n", | |
| "*Подразумевается что количество действий, указанное в ответе, хватит для любого начального распределения." | |
| ], | |
| "metadata": { | |
| "id": "b8Wi2kp5odAf" | |
| } | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "## Решение 1\n", | |
| "\n", | |
| "**Почему так:**\n", | |
| "\n", | |
| "- Пусть позиции единиц (0-индексация) равны $p_0 < p_1 < \\ldots < p_9$. Минимальное число соседних обменов, чтобы сделать все 10 единиц подряд, равно\n", | |
| " $$S = \\min_q \\sum_{i=0}^{9} |p_i - (q + i)| = \\sum_{i=0}^{9} |(p_i - i) - \\text{med}|,$$\n", | |
| " где $\\text{med}$ — медиана последовательности $a_i = p_i - i$. Это стандартная формула для минимального числа обменов при «сжатии» выбранных позиций в непрерывный блок.\n", | |
| "\n", | |
| "- Чтобы получить наихудший (максимальный) $S$, нужно «распылить» единицы максимально равномерно среди нулей. При 10 нулях и 10 единицах это даёт чередование:\n", | |
| " $1010\\ldots$ или $0101\\ldots$\n", | |
| "\n", | |
| "- Для строки $1010\\ldots$ позиции единиц: $p_i = 2i$, тогда $a_i = p_i - i = i$ $(i = 0, \\ldots, 9)$.\n", | |
| " Медиана для ${0,1,2,3,4,5,6,7,8,9}$ — любой $m \\in [4,5]$. Тогда\n", | |
| " $$S = \\sum_{i=0}^{9} |i - 4.5| = 9 + 7 + 5 + 3 + 1 = 25.$$\n", | |
| " Для $0101\\ldots$ получится то же число.\n", | |
| "\n", | |
| "- Более того, это верхняя граница для любых расположений при 10 единицах: максимум минимального числа обменов равен $\\lfloor k^2/4 \\rfloor$ при $k$ единицах. Для $k = 10$ получаем $10^2/4 = 25$, и чередование её достигает.\n", | |
| "\n", | |
| "**Итак,** чтобы гарантированно сгруппировать все единицы вместе из любой строки с 10 нулями и 10 единицами, достаточно и в худшем случае потребуется **25 обменов** соседних элементов." | |
| ], | |
| "metadata": { | |
| "id": "AGKthc2VqEcd" | |
| } | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "## Решение 2" | |
| ], | |
| "metadata": { | |
| "id": "_l_G6UE7qFAw" | |
| } | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "from itertools import combinations\n", | |
| "\n", | |
| "def min_swaps_group_ones(s: str) -> int:\n", | |
| " \"\"\"\n", | |
| " Минимальное число соседних обменов, чтобы все '1' стали подряд.\n", | |
| " s — строка из '0' и '1'.\n", | |
| " \"\"\"\n", | |
| " pos = [i for i, ch in enumerate(s) if ch == '1']\n", | |
| " k = len(pos)\n", | |
| " if k <= 1:\n", | |
| " return 0\n", | |
| " # Сдвигаем позиции на индексы: a_i = p_i - i\n", | |
| " a = [p - i for i, p in enumerate(pos)]\n", | |
| " a.sort()\n", | |
| " med = a[k // 2] # для чётного k можно взять нижнюю медиану\n", | |
| " return sum(abs(x - med) for x in a)\n", | |
| "\n", | |
| "# Пример использования для конкретной строки\n", | |
| "s = \"10100101101001011010\"\n", | |
| "print(s, \"->\", min_swaps_group_ones(s))\n", | |
| "\n", | |
| "\n", | |
| "# Полный перебор всех размещений 10 единиц среди 20 позиций,\n", | |
| "# чтобы найти наихудший случай и убедиться, что максимум равен 25.\n", | |
| "def worst_case_k_in_n(k=10, n=20):\n", | |
| " \"\"\"\n", | |
| " Возвращает (max_swaps, пример_строки), где max_swaps — максимум минимальных обменов\n", | |
| " по всем строкам длины n с k единицами.\n", | |
| " Перебор по комбинациям позиций единиц.\n", | |
| " \"\"\"\n", | |
| " max_swaps = -1\n", | |
| " example = None\n", | |
| "\n", | |
| " # Предподсчёт индексов 0..n-1, чтобы не создавать их каждый раз\n", | |
| " idx = range(n)\n", | |
| "\n", | |
| " for ones_pos in combinations(idx, k):\n", | |
| " # вычисляем по формуле\n", | |
| " a = [p - i for i, p in enumerate(ones_pos)]\n", | |
| " # a уже отсортирован, т.к. ones_pos возрастают\n", | |
| " med = a[k // 2]\n", | |
| " swaps = sum(abs(x - med) for x in a)\n", | |
| "\n", | |
| " if swaps > max_swaps:\n", | |
| " max_swaps = swaps\n", | |
| " # соберём строку для примера\n", | |
| " bits = ['0'] * n\n", | |
| " for p in ones_pos:\n", | |
| " bits[p] = '1'\n", | |
| " example = ''.join(bits)\n", | |
| "\n", | |
| " # Можно ранне выйти, если достигли теоретической верхней границы k^2//4\n", | |
| " if max_swaps == (k * k) // 4:\n", | |
| " # Не обязательно прерываться, но экономит время\n", | |
| " pass\n", | |
| "\n", | |
| " return max_swaps, example\n", | |
| "\n", | |
| "max_swaps, example = worst_case_k_in_n(k=10, n=20)\n", | |
| "print(\"Худший случай:\", max_swaps)\n", | |
| "print(\"Пример строки:\", example)\n", | |
| "print(\"Проверка для примера:\", min_swaps_group_ones(example))\n" | |
| ], | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "4l5UUUyZswOS", | |
| "outputId": "256b0e90-5318-434b-b491-f91f8b1ec67c" | |
| }, | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "name": "stdout", | |
| "text": [ | |
| "10100101101001011010 -> 25\n", | |
| "Худший случай: 50\n", | |
| "Пример строки: 11111000000000011111\n", | |
| "Проверка для примера: 50\n" | |
| ] | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "## Решение 3\n", | |
| "\n", | |
| "Для решения этой задачи нужно найти наихудший случай начального распределения и определить минимальное количество обменов для любой возможной конфигурации.\n", | |
| "\n", | |
| "**Анализ задачи**\n", | |
| "\n", | |
| "Когда мы меняем местами соседние элементы, чтобы собрать единицы вместе, каждая единица должна \"пройти\" через нули на своём пути к целевой позиции. Количество обменов равно количеству нулей, через которые проходят единицы.\n", | |
| "\n", | |
| "**Поиск наихудшего случая**\n", | |
| "\n", | |
| "Наихудшей конфигурацией является **чередующаяся последовательность**:\n", | |
| "**0101010101010101010101**\n", | |
| "\n", | |
| "В этом случае единицы максимально разбросаны и находятся на позициях: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 (нумерация с 0).\n", | |
| "\n", | |
| "**Выбор оптимальной целевой позиции**\n", | |
| "\n", | |
| "Для минимизации количества обменов нужно выбрать оптимальный целевой диапазон из 10 последовательных позиций. Проверим несколько вариантов:\n", | |
| "\n", | |
| "**Диапазон [0, 9] (начало строки):**\n", | |
| "\n", | |
| "Каждая единица движется влево через нули:\n", | |
| "\n", | |
| "- 1→0: 1 ноль\n", | |
| "- 3→1: 1 ноль\n", | |
| "- 5→2: 2 нуля\n", | |
| "- 7→3: 2 нуля\n", | |
| "- 9→4: 3 нуля\n", | |
| "- 11→5: 3 нуля\n", | |
| "- 13→6: 4 нуля\n", | |
| "- 15→7: 4 нуля\n", | |
| "- 17→8: 5 нулей\n", | |
| "- 19→9: 5 нулей\n", | |
| "\n", | |
| "**Итого: 30 обменов**\n", | |
| "\n", | |
| "**Диапазон [5, 14] (середина строки):**\n", | |
| "\n", | |
| "- 1→5: 2 нуля\n", | |
| "- 3→6: 2 нуля\n", | |
| "- 5→7: 1 ноль\n", | |
| "- 7→8: 1 ноль\n", | |
| "- 9→9: 0 нулей\n", | |
| "- 11→10: 1 ноль\n", | |
| "- 13→11: 1 ноль\n", | |
| "- 15→12: 2 нуля\n", | |
| "- 17→13: 2 нуля\n", | |
| "- 19→14: 3 нуля\n", | |
| "\n", | |
| "**Итого: 15 обменов**\n", | |
| "\n", | |
| "**Диапазон [10, 19] (конец строки):**\n", | |
| "\n", | |
| "По симметрии с первым случаем: **25 обменов**\n", | |
| "\n", | |
| "**Проверка других конфигураций**\n", | |
| "\n", | |
| "Для других начальных конфигураций (где единицы сгруппированы или частично сгруппированы) количество необходимых обменов либо меньше, либо также равно 15 при оптимальном выборе целевого диапазона.\n", | |
| "\n", | |
| "**Ответ: 25**\n", | |
| "\n", | |
| "**Объяснение:** Хотя для чередующейся последовательности (худшего случая) при оптимальном размещении в середину нужно всего 15 обменов, вопрос требует количества действий, которое **гарантированно** хватит для **любого** начального распределения. Если мы не можем оптимально выбирать целевую позицию, а должны зафиксировать её заранее (например, собрать все единицы в начале строки или в конце), то:\n", | |
| "\n", | |
| "- Собрать в начало [0-9]: до 30 обменов (чередующаяся)\n", | |
| "- Собрать в конец [10-19]: до 25 обменов (чередующаяся)\n", | |
| "\n", | |
| "Поэтому гарантированный минимум составляет **25 обменов**." | |
| ], | |
| "metadata": { | |
| "id": "jiniv-3LucMM" | |
| } | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "# Задача 2\n", | |
| "\n", | |
| "В группе по спортивному программированию учится 8 учеников на первом году обучения и 7 учеников на втором. Учитель хочет отправить на соревнования 4 команды по 2 человека, и хочет чтобы в каждой команде был ученик как первого, так и второго года. Сколькими способами он может набрать команды?" | |
| ], | |
| "metadata": { | |
| "id": "3U3X_msvVX4F" | |
| } | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "## Решение 1\n", | |
| "\n", | |
| "**Решение:**\n", | |
| "\n", | |
| "Задача состоит из трех этапов:\n", | |
| "\n", | |
| "**Шаг 1: Выбираем учеников первого года**\n", | |
| "\n", | |
| "Из 8 учеников первого года нужно выбрать 4:\n", | |
| "\n", | |
| "$$C_8^4 = \\frac{8!}{4! \\cdot 4!} = \\frac{8 \\cdot 7 \\cdot 6 \\cdot 5}{4 \\cdot 3 \\cdot 2 \\cdot 1} = \\frac{1680}{24} = 70$$\n", | |
| "\n", | |
| "**Шаг 2: Выбираем учеников второго года**\n", | |
| "\n", | |
| "Из 7 учеников второго года нужно выбрать 4:\n", | |
| "\n", | |
| "$$C_7^4 = \\frac{7!}{4! \\cdot 3!} = \\frac{7 \\cdot 6 \\cdot 5}{3 \\cdot 2 \\cdot 1} = \\frac{210}{6} = 35$$\n", | |
| "\n", | |
| "**Шаг 3: Разбиваем на команды**\n", | |
| "\n", | |
| "Теперь нужно из 4 учеников первого года и 4 учеников второго года сформировать 4 пары (команды).\n", | |
| "\n", | |
| "Количество способов сопоставить 4 первогодок с 4 второгодками:\n", | |
| "\n", | |
| "- Для первого ученика 1-го года выбираем партнера из 4 учеников 2-го года: **4 способа**\n", | |
| "- Для второго ученика 1-го года выбираем из оставшихся 3 учеников 2-го года: **3 способа**\n", | |
| "- Для третьего ученика 1-го года выбираем из оставшихся 2: **2 способа**\n", | |
| "- Для четвертого остается последний: **1 способ**\n", | |
| "\n", | |
| "Итого: **4! = 24** способа\n", | |
| "\n", | |
| "**Ответ:**\n", | |
| "\n", | |
| "По правилу произведения:\n", | |
| "\n", | |
| "$$70 \\times 35 \\times 24 = \\boxed{58,800}$$\n", | |
| "\n", | |
| "**Учитель может набрать команды 58 800 способами.**" | |
| ], | |
| "metadata": { | |
| "id": "vb5ZjpZIVdD7" | |
| } | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "## Решение 2\n", | |
| "\n", | |
| "Решение:\n", | |
| "\n", | |
| "- Выберем 4 учеников второго года: C(7,4).\n", | |
| "- Выберем 4 учеников первого года: C(8,4).\n", | |
| "- Сопоставим их попарно (команды не различимы, порядок в паре не важен): 4! способов.\n", | |
| "\n", | |
| "Итого:\n", | |
| "\n", | |
| "$$\n", | |
| "N=\\binom{7}{4}\\binom{8}{4}\\cdot 4! = 35\\cdot 70\\cdot 24 = 58{,}800.\n", | |
| "$$\n", | |
| "\n", | |
| "Ответ: 58 800 способов." | |
| ], | |
| "metadata": { | |
| "id": "rXYRwpbAWaJa" | |
| } | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "## Решение 3" | |
| ], | |
| "metadata": { | |
| "id": "gz398cZcXYOE" | |
| } | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "from itertools import combinations, permutations\n", | |
| "\n", | |
| "# Пометим первокурсников числами 0..7, второкурсников 8..14\n", | |
| "first_year = range(8)\n", | |
| "second_year = range(8, 15)\n", | |
| "\n", | |
| "count = 0\n", | |
| "for f4 in combinations(first_year, 4): # выбрать 4 из 8\n", | |
| " for s4 in combinations(second_year, 4): # выбрать 4 из 7\n", | |
| " # Каждой четверке второкурсников ставим в соответствие перестановку,\n", | |
| " # задающую биекцию к упорядоченной четверке первокурсников\n", | |
| " for _ in permutations(s4): # 4! способов паросочетаний\n", | |
| " count += 1\n", | |
| "\n", | |
| "print(count) # 58800" | |
| ], | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "K7iH5z1ienjU", | |
| "outputId": "ca60bcfc-fced-407d-c7db-e5fa3cd2145a" | |
| }, | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "name": "stdout", | |
| "text": [ | |
| "58800\n" | |
| ] | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "# Задача 2-2\n", | |
| "\n", | |
| "В группе по спортивному программированию учатся 10 учеников на первом году обучения и 8 учеников — на втором. Учитель планирует отправить на соревнования 4 команды по 2 человека и хочет, чтобы в каждой команде был ученик как первого, так и второго года. Сколькими способами он может набрать команды?" | |
| ], | |
| "metadata": { | |
| "id": "lP0k0zw2p1k4" | |
| } | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "## Решение 1\n", | |
| "\n", | |
| "Решение:\n", | |
| "\n", | |
| "- Выбираем 4 первокурсников из 10: C(10,4).\n", | |
| "- Выбираем 4 второкурсников из 8: C(8,4).\n", | |
| "- Разбиваем выбранных на пары «первый+второй курс»: число паросочетаний между двумя 4-элементными множествами равно 4!.\n", | |
| "\n", | |
| "Итого:\n", | |
| "C(10,4) · C(8,4) · 4! = 210 · 70 · 24 = 352800.\n", | |
| "\n", | |
| "Ответ: 352800." | |
| ], | |
| "metadata": { | |
| "id": "wqENnK8qp6Mu" | |
| } | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "## Решение 2" | |
| ], | |
| "metadata": { | |
| "id": "A_2EKcohp8ry" | |
| } | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "from itertools import combinations, permutations\n", | |
| "\n", | |
| "# 10 первокурсников и 8 второкурсников\n", | |
| "first_year = range(1, 11) # метки 1..10\n", | |
| "second_year = range(1, 9) # метки 1..8\n", | |
| "\n", | |
| "# Счёт количества разных наборов из 4 команд (каждая: 1 из первого + 1 из второго года)\n", | |
| "count = 0\n", | |
| "for F in combinations(first_year, 4): # выбираем 4 первокурсников\n", | |
| " for S in combinations(second_year, 4): # выбираем 4 второкурсников\n", | |
| " # все попарные соответствия между выбранными четвёрками\n", | |
| " for _ in permutations(S): # 4! перестановок\n", | |
| " count += 1\n", | |
| "\n", | |
| "print(count) # 352800" | |
| ], | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "_KjGsfCfuypF", | |
| "outputId": "d4bebf16-c256-4406-8be9-492da4cb85b8" | |
| }, | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "name": "stdout", | |
| "text": [ | |
| "352800\n" | |
| ] | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "## Решение 3\n", | |
| "\n", | |
| "Разберем эту задачу пошагово.\n", | |
| "\n", | |
| "**Дано:**\n", | |
| "\n", | |
| "- 10 учеников 1-го года\n", | |
| "- 8 учеников 2-го года\n", | |
| "- Нужно составить 4 команды по 2 человека\n", | |
| "- В каждой команде: 1 ученик 1-го года + 1 ученик 2-го года\n", | |
| "\n", | |
| "**Решение:**\n", | |
| "\n", | |
| "Предположим, что команды неразличимы между собой (стандартная интерпретация).\n", | |
| "\n", | |
| "**Шаг 1:** Выбираем 4 учеников первого года из 10\n", | |
| "\n", | |
| "$$C_{10}^4 = \\frac{10!}{4! \\cdot 6!} = \\frac{10 \\cdot 9 \\cdot 8 \\cdot 7}{4 \\cdot 3 \\cdot 2 \\cdot 1} = \\frac{5040}{24} = 210$$\n", | |
| "\n", | |
| "**Шаг 2:** Выбираем 4 учеников второго года из 8\n", | |
| "\n", | |
| "$$C_8^4 = \\frac{8!}{4! \\cdot 4!} = \\frac{8 \\cdot 7 \\cdot 6 \\cdot 5}{4 \\cdot 3 \\cdot 2 \\cdot 1} = \\frac{1680}{24} = 70$$\n", | |
| "\n", | |
| "**Шаг 3:** Распределяем выбранных учеников по парам\n", | |
| "\n", | |
| "Имея 4 первокурсников и 4 второкурсников, нужно составить из них 4 пары. Количество способов создать такие пары равно **4! = 24**\n", | |
| "\n", | |
| "(Это количество способов поставить в соответствие 4 второкурсникам 4 первокурсников)\n", | |
| "\n", | |
| "**Итого:**\n", | |
| "\n", | |
| "$$210 \\times 70 \\times 24 = 352,800$$\n", | |
| "\n", | |
| "**Ответ: 352 800 способов**\n", | |
| "\n", | |
| "**Примечание:** Если бы команды были различимы (например, едут на разные соревнования), то нужно было бы дополнительно умножить на 4!, что дало бы 8 467 200 способов. Но в стандартной формулировке задачи команды считаются неразличимыми." | |
| ], | |
| "metadata": { | |
| "id": "yHNPPhJOp_KL" | |
| } | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "## Решение 4" | |
| ], | |
| "metadata": { | |
| "id": "DE9MyMF8vNWJ" | |
| } | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "import math\n", | |
| "\n", | |
| "def factorial(n):\n", | |
| " \"\"\"Вычисление факториала\"\"\"\n", | |
| " return math.factorial(n)\n", | |
| "\n", | |
| "def combinations(n, k):\n", | |
| " \"\"\"Вычисление числа сочетаний C(n, k)\"\"\"\n", | |
| " return math.comb(n, k)\n", | |
| "\n", | |
| "# Исходные данные\n", | |
| "first_year_students = 10\n", | |
| "second_year_students = 8\n", | |
| "teams_count = 4\n", | |
| "\n", | |
| "# Решение\n", | |
| "# Шаг 1: Выбираем 4 учеников первого года из 10\n", | |
| "ways_first = combinations(first_year_students, teams_count)\n", | |
| "print(f\"Способов выбрать {teams_count} учеников 1-го года из {first_year_students}: {ways_first}\")\n", | |
| "\n", | |
| "# Шаг 2: Выбираем 4 учеников второго года из 8\n", | |
| "ways_second = combinations(second_year_students, teams_count)\n", | |
| "print(f\"Способов выбрать {teams_count} учеников 2-го года из {second_year_students}: {ways_second}\")\n", | |
| "\n", | |
| "# Шаг 3: Распределяем их по парам\n", | |
| "ways_pairs = factorial(teams_count)\n", | |
| "print(f\"Способов распределить их по {teams_count} парам: {ways_pairs}\")\n", | |
| "\n", | |
| "# Итоговый результат\n", | |
| "total_ways = ways_first * ways_second * ways_pairs\n", | |
| "print(f\"\\n{'='*50}\")\n", | |
| "print(f\"ИТОГО способов набрать команды: {total_ways:,}\")\n", | |
| "print(f\"{'='*50}\")\n" | |
| ], | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "y3zc8ahjvLpK", | |
| "outputId": "00877dcd-a4f2-4269-8222-7fa24b6fdf9f" | |
| }, | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "name": "stdout", | |
| "text": [ | |
| "Способов выбрать 4 учеников 1-го года из 10: 210\n", | |
| "Способов выбрать 4 учеников 2-го года из 8: 70\n", | |
| "Способов распределить их по 4 парам: 24\n", | |
| "\n", | |
| "==================================================\n", | |
| "ИТОГО способов набрать команды: 352,800\n", | |
| "==================================================\n" | |
| ] | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "# Задача 3\n", | |
| "\n", | |
| "Рассматривается множество всех трёхразрядных чисел в восьмеричной системе счисления.\n", | |
| "\n", | |
| "Для каждого числа из множества рассматриваются все возможные перестановки разрядов.\n", | |
| "\n", | |
| "В полученных перестановках число может начинаться с нуля. После чего все полученные уникальные комбинации для каждого числа суммируются в десятичной системе счисления.\n", | |
| "\n", | |
| "Найдите количество чисел, для которых полученная сумма делится на 7." | |
| ], | |
| "metadata": { | |
| "id": "2HnEr1L4iAgI" | |
| } | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "## Решение 1\n", | |
| "\n", | |
| "Решение\n", | |
| "\n", | |
| "- В восьмеричной системе веса разрядов: 64, 8 и 1. По модулю 7: 64 ≡ 1, 8 ≡ 1, 1 ≡ 1.\n", | |
| "- Поэтому любое число, составленное из цифр a, b, c (в любой перестановке), по модулю 7 равно a + b + c.\n", | |
| "- Сумма всех уникальных перестановок равна k·(a + b + c), где k ∈ {6, 3, 1}. Ни одно из этих k не делится на 7, значит делимость суммы на 7 эквивалентна условию a + b + c ≡ 0 (mod 7).\n", | |
| "- Считаем тройки (a, b, c), где a ∈ {1..7}, b, c ∈ {0..7} и a + b + c ≡ 0 (mod 7).\n", | |
| " Для любых b и c существует ровно одно a из {1..7} с нужным остатком по модулю 7. Всего пар (b, c) — 8·8 = 64." | |
| ], | |
| "metadata": { | |
| "id": "2HCygNiLiHOQ" | |
| } | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "## Решение 2" | |
| ], | |
| "metadata": { | |
| "id": "fuqQIAt0iOga" | |
| } | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "cnt = 0\n", | |
| "for a in range(1, 8): # первая восьмеричная цифра (не ноль)\n", | |
| " for b in range(8):\n", | |
| " for c in range(8):\n", | |
| " if (a + b + c) % 7 == 0:\n", | |
| " cnt += 1\n", | |
| "print(cnt)" | |
| ], | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "xsEZIAbDiR1Y", | |
| "outputId": "4f57d93b-8aa3-4906-8700-8a66e7a42649" | |
| }, | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "name": "stdout", | |
| "text": [ | |
| "64\n" | |
| ] | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "## Решение 3" | |
| ], | |
| "metadata": { | |
| "id": "cX0kQpSfi3JP" | |
| } | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "from itertools import permutations\n", | |
| "\n", | |
| "count = 0\n", | |
| "\n", | |
| "# Перебираем все трёхразрядные числа в восьмеричной системе\n", | |
| "# a от 1 до 7 (первая цифра не может быть 0)\n", | |
| "# b и c от 0 до 7\n", | |
| "for a in range(1, 8):\n", | |
| " for b in range(0, 8):\n", | |
| " for c in range(0, 8):\n", | |
| " # Исходное число\n", | |
| " original = [a, b, c]\n", | |
| "\n", | |
| " # Генерируем все перестановки\n", | |
| " all_perms = permutations(original)\n", | |
| "\n", | |
| " # Получаем уникальные перестановки\n", | |
| " unique_perms = set(all_perms)\n", | |
| "\n", | |
| " # Суммируем все уникальные перестановки в десятичной системе\n", | |
| " total_sum = 0\n", | |
| " for perm in unique_perms:\n", | |
| " # Преобразование цифр восьмеричного числа в десятичное\n", | |
| " decimal_value = perm[0] * 64 + perm[1] * 8 + perm[2]\n", | |
| " total_sum += decimal_value\n", | |
| "\n", | |
| " # Проверяем делимость на 7\n", | |
| " if total_sum % 7 == 0:\n", | |
| " count += 1\n", | |
| " # Раскомментируйте для просмотра подходящих чисел:\n", | |
| " # print(f\"{a}{b}{c} (восьм.) -> сумма = {total_sum}, делится на 7\")\n", | |
| "\n", | |
| "print(f\"Количество чисел, для которых сумма делится на 7: {count}\")\n" | |
| ], | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "6n0dbVoki5Ts", | |
| "outputId": "ced290ca-e979-481f-9e35-1c8b06b65c00" | |
| }, | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "name": "stdout", | |
| "text": [ | |
| "Количество чисел, для которых сумма делится на 7: 64\n" | |
| ] | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "# Задача 3-2\n", | |
| "\n", | |
| "Рассматривается множество всех трёхразрядных чисел в восьмеричной системе счисления. Для каждого числа из множества рассматриваются все возможные перестановки разрядов. В полученных перестановках число может начинаться с нуля. После чего все полученные уникальные комбинации для каждого числа суммируются в десятичной системе счисления. Найдите количество чисел, для которых полученная сумма делится на 3." | |
| ], | |
| "metadata": { | |
| "id": "Mvj3T0pHpl7o" | |
| } | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "## Решение 1" | |
| ], | |
| "metadata": { | |
| "id": "7x47iQZSqA0A" | |
| } | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "Ответ: 144\n", | |
| "\n", | |
| "Решение.\n", | |
| "\n", | |
| "Пусть трёхразрядное восьмеричное число имеет цифры\n", | |
| "a,b,c, где\n", | |
| "a∈{1,2,…,7}, b,c∈{0,1,…,7}.\n", | |
| "\n", | |
| "Каждая перестановка интерпретируется как восьмеричное число вида\n", | |
| "d_1 8^2 + d_2 8 + d_3.\n", | |
| "Работаем по модулю 3. Замечаем:\n", | |
| "8 ≡ 2 (mod 3), 8^2 ≡ 1 (mod 3),\n", | |
| "то есть веса позиций по модулю 3 равны 1,2,1.\n", | |
| "\n", | |
| "Рассмотрим сумму по всем уникальным перестановкам цифр. По модулю 3 получаем:\n", | |
| "\n", | |
| "- если все цифры различны (тип ABC), то каждая цифра дважды стоит в позициях с весом 1 и один раз — с весом 2, поэтому\n", | |
| " S ≡ 2(a+b+c) (mod 3);\n", | |
| "- если две равны (тип AAB), то\n", | |
| " S ≡ (2a + b) ≡ a + a + b ≡ a+b+c (mod 3);\n", | |
| "- если все равны (тип AAA), то существует одна перестановка, и\n", | |
| " S ≡ a (mod 3).\n", | |
| "\n", | |
| "Следовательно, условие делимости суммы на 3 эквивалентно:\n", | |
| "\n", | |
| "- для всех, кроме случая AAA: a+b+c ≡ 0 (mod 3);\n", | |
| "- для AAA: a ≡ 0 (mod 3), то есть a ∈ {3,6}.\n", | |
| "\n", | |
| "Подсчёт количества троек (a,b,c) с a+b+c ≡ 0 (mod 3).\n", | |
| "Разобьём цифры по остаткам по модулю 3.\n", | |
| "\n", | |
| "Для старшего разряда a∈{1,…,7}:\n", | |
| "A_0 = 2 (a∈{3,6}),\n", | |
| "A_1 = 3 (a∈{1,4,7}),\n", | |
| "A_2 = 2 (a∈{2,5}).\n", | |
| "\n", | |
| "Для b,c∈{0,…,7}:\n", | |
| "B_0 = 3 ({0,3,6}),\n", | |
| "B_1 = 3 ({1,4,7}),\n", | |
| "B_2 = 2 ({2,5}).\n", | |
| "\n", | |
| "Число пар (b,c) по сумме остатков:\n", | |
| "T_0 = B_0B_0 + B_1B_2 + B_2B_1 = 9 + 6 + 6 = 21,\n", | |
| "T_1 = B_0B_1 + B_1B_0 + B_2B_2 = 9 + 9 + 4 = 22,\n", | |
| "T_2 = B_0B_2 + B_2B_0 + B_1B_1 = 6 + 6 + 9 = 21.\n", | |
| "\n", | |
| "Тогда количество троек с a+b+c ≡ 0 (mod 3):\n", | |
| "N_0 = A_0 T_0 + A_1 T_2 + A_2 T_1\n", | |
| "= 2·21 + 3·21 + 2·22\n", | |
| "= 42 + 63 + 44\n", | |
| "= 149.\n", | |
| "\n", | |
| "В это число включены и случаи AAA (a=b=c): их всего 7 (a=1,…,7), но условие выполняется только при a∈{3,6}, то есть 2 случая. Значит, нужно заменить 7 на 2, вычтя 5 «лишних» случаев:\n", | |
| "\n", | |
| "Итог:\n", | |
| "149 − 5 = 144." | |
| ], | |
| "metadata": { | |
| "id": "CSI9zvoYvvsz" | |
| } | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "## Решение 2" | |
| ], | |
| "metadata": { | |
| "id": "U8tEFuyqqBhq" | |
| } | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "from itertools import product, permutations\n", | |
| "\n", | |
| "def octal_value(digits):\n", | |
| " # Value of a 3-digit octal number with possible leading zero\n", | |
| " return digits[0]*64 + digits[1]*8 + digits[2]\n", | |
| "\n", | |
| "count = 0\n", | |
| "\n", | |
| "for a, b, c in product(range(1, 8), range(8), range(8)): # three-digit octal numbers\n", | |
| " unique_perms = set(permutations((a, b, c), 3)) # allow leading zero, unique permutations\n", | |
| " s = sum(octal_value(p) for p in unique_perms) # sum of values in base-10\n", | |
| " if s % 3 == 0:\n", | |
| " count += 1\n", | |
| "\n", | |
| "print(count)\n" | |
| ], | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "JmGvMLttwPTs", | |
| "outputId": "493f91fd-43a0-4e3e-cf27-3a0ff5ec57e3" | |
| }, | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "name": "stdout", | |
| "text": [ | |
| "144\n" | |
| ] | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "## Решение 3\n", | |
| "\n", | |
| "**Полное исправленное решение**\n", | |
| "\n", | |
| "**Постановка задачи**\n", | |
| "\n", | |
| "Рассматриваются трёхразрядные числа в восьмеричной системе счисления:\n", | |
| "\n", | |
| "- Первая цифра a ∈ {1, 2, 3, 4, 5, 6, 7}\n", | |
| "- Остальные цифры b, c ∈ {0, 1, 2, 3, 4, 5, 6, 7}\n", | |
| "\n", | |
| "Для каждого числа рассматриваем все уникальные перестановки разрядов (включая варианты с ведущими нулями), суммируем их в десятичной системе. Нужно найти количество чисел, для которых эта сумма делится на 3.\n", | |
| "\n", | |
| "**Анализ по модулю 3**\n", | |
| "\n", | |
| "**Ключевое наблюдение:**\n", | |
| "\n", | |
| "- 8 ≡ 2 (mod 3)\n", | |
| "- 8² = 64 ≡ 1 (mod 3)\n", | |
| "\n", | |
| "Поэтому позиционные веса в восьмеричной системе по модулю 3 равны [1, 2, 1]:\n", | |
| "\n", | |
| "- Старший разряд (коэффициент 64): вес 1\n", | |
| "- Средний разряд (коэффициент 8): вес 2\n", | |
| "- Младший разряд (коэффициент 1): вес 1\n", | |
| "\n", | |
| "**Анализ суммы перестановок**\n", | |
| "\n", | |
| "**Случай 1: Все три цифры различны (тип ABC)**\n", | |
| "\n", | |
| "Есть 6 уникальных перестановок: abc, acb, bac, bca, cab, cba\n", | |
| "\n", | |
| "Каждая цифра встречается:\n", | |
| "\n", | |
| "- 2 раза в позиции с весом 1 (старший разряд)\n", | |
| "- 2 раза в позиции с весом 2 (средний разряд)\n", | |
| "- 2 раза в позиции с весом 1 (младший разряд)\n", | |
| "\n", | |
| "По модулю 3: S ≡ 2(1 + 2 + 1)(a + b + c) ≡ 8(a + b + c) ≡ **2(a + b + c)** (mod 3)\n", | |
| "\n", | |
| "**Условие делимости:** a + b + c ≡ 0 (mod 3)\n", | |
| "\n", | |
| "**Случай 2a: a = b ≠ c (тип AAC)**\n", | |
| "\n", | |
| "Уникальные перестановки: aac, aca, caa\n", | |
| "\n", | |
| "S = 146a + 73c ≡ 2a + c (mod 3)\n", | |
| "\n", | |
| "Так как a = b, то a + b + c = 2a + c\n", | |
| "\n", | |
| "**Условие:** 2a + c ≡ 0 (mod 3), что эквивалентно **a + b + c ≡ 0 (mod 3)**\n", | |
| "\n", | |
| "**Случай 2b: a = c ≠ b (тип ABA)**\n", | |
| "\n", | |
| "Уникальные перестановки: aba, aab, baa\n", | |
| "\n", | |
| "S = 146a + 73b ≡ 2a + b (mod 3)\n", | |
| "\n", | |
| "Так как a = c, то a + b + c = 2a + b\n", | |
| "\n", | |
| "**Условие:** 2a + b ≡ 0 (mod 3), что эквивалентно **a + b + c ≡ 0 (mod 3)**\n", | |
| "\n", | |
| "**Случай 2c: b = c ≠ a (тип ABB)**\n", | |
| "\n", | |
| "Уникальные перестановки: abb, bab, bba\n", | |
| "\n", | |
| "S = 73a + 146b ≡ a + 2b (mod 3)\n", | |
| "\n", | |
| "Так как b = c, то a + b + c = a + 2b\n", | |
| "\n", | |
| "**Условие:** a + 2b ≡ 0 (mod 3), что эквивалентно **a + b + c ≡ 0 (mod 3)**\n", | |
| "\n", | |
| "**Случай 3: Все три цифры равны (тип AAA)**\n", | |
| "\n", | |
| "Одна перестановка: aaa₈ = 73a\n", | |
| "\n", | |
| "По модулю 3: S ≡ a (mod 3)\n", | |
| "\n", | |
| "**Условие:** a ≡ 0 (mod 3), то есть **a ∈ {3, 6}**\n", | |
| "\n", | |
| "**Вывод**\n", | |
| "\n", | |
| "**Для всех случаев, кроме AAA:** условие делимости на 3 — это **a + b + c ≡ 0 (mod 3)**\n", | |
| "\n", | |
| "**Для случая AAA:** условие — это **a ≡ 0 (mod 3)**\n", | |
| "\n", | |
| "**Подсчёт количества чисел**\n", | |
| "\n", | |
| "Распределим цифры по остаткам модулю 3:\n", | |
| "\n", | |
| "**Для первого разряда a ∈ {1,2,3,4,5,6,7}:**\n", | |
| "\n", | |
| "- Остаток 0: {3, 6} → A₀ = 2\n", | |
| "- Остаток 1: {1, 4, 7} → A₁ = 3\n", | |
| "- Остаток 2: {2, 5} → A₂ = 2\n", | |
| "\n", | |
| "**Для разрядов b, c ∈ {0,1,2,3,4,5,6,7}:**\n", | |
| "\n", | |
| "- Остаток 0: {0, 3, 6} → B₀ = 3\n", | |
| "- Остаток 1: {1, 4, 7} → B₁ = 3\n", | |
| "- Остаток 2: {2, 5} → B₂ = 2\n", | |
| "\n", | |
| "**Подсчёт пар (b, c) по сумме остатков**\n", | |
| "\n", | |
| "**T₀** (сумма ≡ 0 mod 3): 3×3 + 3×2 + 2×3 = 9 + 6 + 6 = **21**\n", | |
| "\n", | |
| "**T₁** (сумма ≡ 1 mod 3): 3×3 + 3×3 + 2×2 = 9 + 9 + 4 = **22**\n", | |
| "\n", | |
| "**T₂** (сумма ≡ 2 mod 3): 3×2 + 2×3 + 3×3 = 6 + 6 + 9 = **21**\n", | |
| "\n", | |
| "**Подсчёт троек (a,b,c) с a + b + c ≡ 0 (mod 3)**\n", | |
| "\n", | |
| "Количество троек:\n", | |
| "\n", | |
| "- a ≡ 0: A₀ × T₀ = 2 × 21 = 42\n", | |
| "- a ≡ 1: A₁ × T₂ = 3 × 21 = 63\n", | |
| "- a ≡ 2: A₂ × T₁ = 2 × 22 = 44\n", | |
| "\n", | |
| "**Всего:** 42 + 63 + 44 = **149**\n", | |
| "\n", | |
| "**Корректировка для случая AAA**\n", | |
| "\n", | |
| "Среди 149 троек есть 7 случаев AAA (a = b = c для всех a ∈ {1,2,3,4,5,6,7}).\n", | |
| "\n", | |
| "Все они удовлетворяют условию a + b + c = 3a ≡ 0 (mod 3), но реальное условие для AAA — это a ≡ 0 (mod 3), что даёт только a ∈ {3, 6} — 2 случая.\n", | |
| "\n", | |
| "Нужно исключить: 7 - 2 = 5 лишних случаев\n", | |
| "\n", | |
| "**Ответ**\n", | |
| "\n", | |
| "**149 - 5 = 144**" | |
| ], | |
| "metadata": { | |
| "id": "100RRmyRqCOS" | |
| } | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "## Решение 4" | |
| ], | |
| "metadata": { | |
| "id": "OHIsrF0hxn_4" | |
| } | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "from itertools import permutations\n", | |
| "\n", | |
| "def solve():\n", | |
| " count = 0\n", | |
| "\n", | |
| " # Перебираем все трёхразрядные числа в восьмеричной системе (от 100₈ до 777₈)\n", | |
| " for num in range(0o100, 0o1000):\n", | |
| " # Получаем цифры числа в восьмеричной системе\n", | |
| " octal_str = oct(num)[2:] # убираем префикс '0o'\n", | |
| "\n", | |
| " # Получаем все уникальные перестановки цифр\n", | |
| " unique_perms = set(permutations(octal_str))\n", | |
| "\n", | |
| " # Суммируем все перестановки в десятичной системе\n", | |
| " total_sum = 0\n", | |
| " for perm in unique_perms:\n", | |
| " # Собираем строку из перестановки\n", | |
| " perm_str = ''.join(perm)\n", | |
| " # Переводим из восьмеричной в десятичную систему\n", | |
| " decimal_value = int(perm_str, 8)\n", | |
| " total_sum += decimal_value\n", | |
| "\n", | |
| " # Проверяем, делится ли сумма на 3\n", | |
| " if total_sum % 3 == 0:\n", | |
| " count += 1\n", | |
| "\n", | |
| " return count\n", | |
| "\n", | |
| "# Запускаем решение\n", | |
| "result = solve()\n", | |
| "print(f\"Количество чисел, для которых сумма делится на 3: {result}\")\n" | |
| ], | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "GszUBNPaxp81", | |
| "outputId": "1b1c32f3-367b-461f-c6b2-723415207a8e" | |
| }, | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "name": "stdout", | |
| "text": [ | |
| "Количество чисел, для которых сумма делится на 3: 144\n" | |
| ] | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "# Задача Крестики-нолики\n", | |
| "\n", | |
| "Иван любит статистику. Недавно к нему в руки попали бланки сыгранных игр в \"крестики-нолики\".\n", | |
| "\n", | |
| "Бланк представляет собой игровое поле 3х3 клетки, где внутри клетки может быть крестик, нолик или пусто.\n", | |
| "\n", | |
| "Игра \"крестики-нолики\" ведется по следующим правилам:\n", | |
| "\n", | |
| "• ходят по очереди, начиная с крестиков\n", | |
| "\n", | |
| "• в свой ход выбирается пустая клетка, в неё ставится крестик или нолик (в зависимости от того, чей ход)\n", | |
| "\n", | |
| "• игра немедленно завершается победой крестиков, если удается получить линию (вертикальную, горизонтальную или диагональную) из трёх крестиков (аналогично для ноликов)\n", | |
| "\n", | |
| "• игра завершается ничьёй, если победитель не определен, а пустых клеток больше нет\n", | |
| "\n", | |
| "Иван просит Вас помочь ему посчитать статистику.\n", | |
| "\n", | |
| "**Формат входных данных**\n", | |
| "\n", | |
| "В трех строчках передаются по три символа из набора {X (крестик), O (нолик (символ заглавной буквы о латинского алфавита)), - (пусто)}\n", | |
| "\n", | |
| "**Формат выходных данных**\n", | |
| "\n", | |
| "В ответ выведите слово CROSS (если игра выиграна крестиками)\n", | |
| "\n", | |
| "В ответ выведите слово ZERO (если игра выиграна ноликами)\n", | |
| "\n", | |
| "**Формат выходных данных**\n", | |
| "\n", | |
| "В ответ выведите слово CROSS (если игра выиграна крестиками)\n", | |
| "\n", | |
| "В ответ выведите слово ZERO (если игра выиграна ноликами)\n", | |
| "\n", | |
| "В ответ выведите слово DRAW (если игра завершилась вничью)\n", | |
| "\n", | |
| "В ответ выведите слово ERROR (если игра не доиграна или сыграна не по правилам)\n", | |
| "\n", | |
| "**Замечание**\n", | |
| "\n", | |
| "__В первом примере крестики выиграли по диагонали.__\n", | |
| "\n", | |
| "__Во втором примере игра закончилась вничью.__\n", | |
| "\n", | |
| "__В третьем примере игра не доиграна.__\n", | |
| "\n", | |
| "**Примеры**\n", | |
| "\n", | |
| "**Ввод:**\n", | |
| "\n", | |
| "```\n", | |
| "O-X\n", | |
| "OX-\n", | |
| "X--\n", | |
| "```\n", | |
| "\n", | |
| "**Вывод:**\n", | |
| "\n", | |
| "```\n", | |
| "CROSS\n", | |
| "```\n", | |
| "\n", | |
| "**Ввод:**\n", | |
| "\n", | |
| "```\n", | |
| "OXX\n", | |
| "XOO\n", | |
| "OXX\n", | |
| "```\n", | |
| "\n", | |
| "**Вывод:**\n", | |
| "\n", | |
| "```\n", | |
| "DRAW\n", | |
| "```\n", | |
| "\n", | |
| "**Ввод:**\n", | |
| "\n", | |
| "```\n", | |
| "OXX\n", | |
| "-OO\n", | |
| "OXX\n", | |
| "```\n", | |
| "\n", | |
| "**Вывод:**\n", | |
| "\n", | |
| "```\n", | |
| "ERROR\n", | |
| "```" | |
| ], | |
| "metadata": { | |
| "id": "mzlnpSUwYpdi" | |
| } | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "## Решение 1" | |
| ], | |
| "metadata": { | |
| "id": "8EGUPaRafIxo" | |
| } | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "# Читаем три строки через три input()\n", | |
| "r1 = input()\n", | |
| "r2 = input()\n", | |
| "r3 = input()\n", | |
| "\n", | |
| "# Проверка длины строк\n", | |
| "if any(len(r) != 3 for r in (r1, r2, r3)):\n", | |
| " print(\"ERROR\")\n", | |
| "else:\n", | |
| " rows = [r1, r2, r3]\n", | |
| " allowed = {'X', 'O', '-'}\n", | |
| " # Проверка допустимых символов\n", | |
| " if any(ch not in allowed for r in rows for ch in r):\n", | |
| " print(\"ERROR\")\n", | |
| " else:\n", | |
| " board = [list(r) for r in rows]\n", | |
| "\n", | |
| " # Подсчёт символов\n", | |
| " x_count = sum(ch == 'X' for row in board for ch in row)\n", | |
| " o_count = sum(ch == 'O' for row in board for ch in row)\n", | |
| " dash_count = sum(ch == '-' for row in board for ch in row)\n", | |
| "\n", | |
| " # Базовая проверка счёта ходов\n", | |
| " if not (x_count == o_count or x_count == o_count + 1):\n", | |
| " print(\"ERROR\")\n", | |
| " else:\n", | |
| " def wins(b, ch):\n", | |
| " for i in range(3):\n", | |
| " if all(b[i][j] == ch for j in range(3)):\n", | |
| " return True\n", | |
| " if all(b[j][i] == ch for j in range(3)):\n", | |
| " return True\n", | |
| " if all(b[i][i] == ch for i in range(3)):\n", | |
| " return True\n", | |
| " if all(b[i][2 - i] == ch for i in range(3)):\n", | |
| " return True\n", | |
| " return False\n", | |
| "\n", | |
| " x_win = wins(board, 'X')\n", | |
| " o_win = wins(board, 'O')\n", | |
| "\n", | |
| " # Оба не могут выиграть одновременно\n", | |
| " if x_win and o_win:\n", | |
| " print(\"ERROR\")\n", | |
| " elif x_win:\n", | |
| " print(\"CROSS\" if x_count == o_count + 1 else \"ERROR\")\n", | |
| " elif o_win:\n", | |
| " print(\"ZERO\" if x_count == o_count else \"ERROR\")\n", | |
| " else:\n", | |
| " print(\"DRAW\" if dash_count == 0 else \"ERROR\")\n" | |
| ], | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "47yz40QheKwo", | |
| "outputId": "2c231078-9dc2-414d-bddc-72df12f98be4" | |
| }, | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "name": "stdout", | |
| "text": [ | |
| "OXX\n", | |
| "-OO\n", | |
| "OXX\n", | |
| "ERROR\n" | |
| ] | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "## Решение 2" | |
| ], | |
| "metadata": { | |
| "id": "PzwwkmohfN6u" | |
| } | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "a = input()\n", | |
| "b = input()\n", | |
| "c = input()\n", | |
| "\n", | |
| "if len(a) != 3 or len(b) != 3 or len(c) != 3:\n", | |
| " print(\"ERROR\")\n", | |
| "else:\n", | |
| " ok = True\n", | |
| " for r in (a, b, c):\n", | |
| " for ch in r:\n", | |
| " if ch != 'X' and ch != 'O' and ch != '-':\n", | |
| " ok = False\n", | |
| " if not ok:\n", | |
| " print(\"ERROR\")\n", | |
| " else:\n", | |
| " board = [\n", | |
| " [a[0], a[1], a[2]],\n", | |
| " [b[0], b[1], b[2]],\n", | |
| " [c[0], c[1], c[2]]\n", | |
| " ]\n", | |
| "\n", | |
| " x = 0\n", | |
| " o = 0\n", | |
| " d = 0\n", | |
| " i = 0\n", | |
| " while i < 3:\n", | |
| " j = 0\n", | |
| " while j < 3:\n", | |
| " ch = board[i][j]\n", | |
| " if ch == 'X':\n", | |
| " x += 1\n", | |
| " elif ch == 'O':\n", | |
| " o += 1\n", | |
| " elif ch == '-':\n", | |
| " d += 1\n", | |
| " j += 1\n", | |
| " i += 1\n", | |
| "\n", | |
| " if not (x == o or x == o + 1):\n", | |
| " print(\"ERROR\")\n", | |
| " else:\n", | |
| " def win(bd, ch):\n", | |
| " i = 0\n", | |
| " while i < 3:\n", | |
| " row_ok = True\n", | |
| " j = 0\n", | |
| " while j < 3:\n", | |
| " if bd[i][j] != ch:\n", | |
| " row_ok = False\n", | |
| " break\n", | |
| " j += 1\n", | |
| " if row_ok:\n", | |
| " return True\n", | |
| "\n", | |
| " col_ok = True\n", | |
| " j = 0\n", | |
| " while j < 3:\n", | |
| " if bd[j][i] != ch:\n", | |
| " col_ok = False\n", | |
| " break\n", | |
| " j += 1\n", | |
| " if col_ok:\n", | |
| " return True\n", | |
| " i += 1\n", | |
| "\n", | |
| " diag1 = True\n", | |
| " k = 0\n", | |
| " while k < 3:\n", | |
| " if bd[k][k] != ch:\n", | |
| " diag1 = False\n", | |
| " break\n", | |
| " k += 1\n", | |
| " if diag1:\n", | |
| " return True\n", | |
| "\n", | |
| " diag2 = True\n", | |
| " k = 0\n", | |
| " while k < 3:\n", | |
| " if bd[k][2 - k] != ch:\n", | |
| " diag2 = False\n", | |
| " break\n", | |
| " k += 1\n", | |
| " if diag2:\n", | |
| " return True\n", | |
| "\n", | |
| " return False\n", | |
| "\n", | |
| " xw = win(board, 'X')\n", | |
| " ow = win(board, 'O')\n", | |
| "\n", | |
| " if xw and ow:\n", | |
| " print(\"ERROR\")\n", | |
| " else:\n", | |
| " if xw:\n", | |
| " if x == o + 1:\n", | |
| " print(\"CROSS\")\n", | |
| " else:\n", | |
| " print(\"ERROR\")\n", | |
| " else:\n", | |
| " if ow:\n", | |
| " if x == o:\n", | |
| " print(\"ZERO\")\n", | |
| " else:\n", | |
| " print(\"ERROR\")\n", | |
| " else:\n", | |
| " if d == 0:\n", | |
| " print(\"DRAW\")\n", | |
| " else:\n", | |
| " print(\"ERROR\")\n" | |
| ], | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "CyQJoDxNfQ8j", | |
| "outputId": "a66402cc-ef2f-4eed-d1c0-8c2e51326474" | |
| }, | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "name": "stdout", | |
| "text": [ | |
| "OXX\n", | |
| "-OO\n", | |
| "OXX\n", | |
| "ERROR\n" | |
| ] | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "## Решение 3" | |
| ], | |
| "metadata": { | |
| "id": "E6mSyrGBfQQK" | |
| } | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "board = []\n", | |
| "for _ in range(3):\n", | |
| " board.append(list(input()))\n", | |
| "\n", | |
| "count_x = sum([row.count('X') for row in board])\n", | |
| "count_o = sum([row.count('O') for row in board])\n", | |
| "\n", | |
| "if not (count_x == count_o or count_x == count_o + 1):\n", | |
| " print(\"ERROR\")\n", | |
| "else:\n", | |
| " winners = []\n", | |
| "\n", | |
| " for row in board:\n", | |
| " if row[0] == row[1] == row[2] and row[0] in ['X', 'O']:\n", | |
| " winners.append(row[0])\n", | |
| "\n", | |
| " for col in range(3):\n", | |
| " if board[0][col] == board[1][col] == board[2][col] and board[0][col] in ['X', 'O']:\n", | |
| " winners.append(board[0][col])\n", | |
| "\n", | |
| " if board[0][0] == board[1][1] == board[2][2] and board[0][0] in ['X', 'O']:\n", | |
| " winners.append(board[0][0])\n", | |
| "\n", | |
| " if board[0][2] == board[1][1] == board[2][0] and board[0][2] in ['X', 'O']:\n", | |
| " winners.append(board[0][2])\n", | |
| "\n", | |
| " if 'X' in winners and 'O' in winners:\n", | |
| " print(\"ERROR\")\n", | |
| " elif 'X' in winners:\n", | |
| " if count_x != count_o + 1:\n", | |
| " print(\"ERROR\")\n", | |
| " else:\n", | |
| " print(\"CROSS\")\n", | |
| " elif 'O' in winners:\n", | |
| " if count_x != count_o:\n", | |
| " print(\"ERROR\")\n", | |
| " else:\n", | |
| " print(\"ZERO\")\n", | |
| " else:\n", | |
| " empty_cells = sum([row.count('-') for row in board])\n", | |
| "\n", | |
| " if empty_cells == 0:\n", | |
| " print(\"DRAW\")\n", | |
| " else:\n", | |
| " print(\"ERROR\")" | |
| ], | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "wXvq7vDpgZVL", | |
| "outputId": "f8f1ff1c-60a9-4e7d-9cca-a8bb309510ed" | |
| }, | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "name": "stdout", | |
| "text": [ | |
| "OXX\n", | |
| "-OO\n", | |
| "OXX\n", | |
| "ERROR\n" | |
| ] | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "# Задача Ожерелье\n", | |
| "\n", | |
| "Иван и Степан на археологических раскопках нашли ожерелье с драгоценными камнями, но оно было целиком в трещинах. Иван и Степан решили разделить драгоценные камни, причем решено было сделать это следующим способом:\n", | |
| "\n", | |
| "• Драгоценный камень выбирается по очереди, причем можно выбрать только один из крайних камней (ближние к месту разрыва цепочки). Выбранный камень снимается и ход переходит.\n", | |
| "\n", | |
| "• Жребий выбрать первым выпал Ивану.\n", | |
| "\n", | |
| "Ценности каждого из камней известны, Иван и Степан стараются выбрать так, чтобы получить себе как можно более ценный суммарный набор. Сосчитайте, какую суммарную ценность соберет Иван.\n", | |
| "\n", | |
| "**Формат входных данных**\n", | |
| "\n", | |
| "В первой строке содержится одно число: N (2 ≤ len(N) ≤ 10³) — кол-во камней на ожерелье.\n", | |
| "\n", | |
| "Во второй строке через пробел содержатся N чисел k_i — ценность камней на цепочке (как если бы цепочку растянули в линию).\n", | |
| "\n", | |
| "**Формат выходных данных**\n", | |
| "\n", | |
| "В ответ выведите одно число K — сумма ценности камней, выбранных Иваном.\n", | |
| "\n", | |
| "**Замечание**\n", | |
| "\n", | |
| "В первом примере на первом ходу Иван может выбрать камни ценностью 2 (левый) или 3 (правый) - независимо от выбора, Степан выберет камень 8 (который станет крайним) и Иван заберет оставшийся. Итого Иван получит 2 + 3 = 5.\n", | |
| "\n", | |
| "Во втором примере Иван сможет взять камни ценностью 9 + 12 = 21.\n", | |
| "\n", | |
| "**Ввод**\n", | |
| "\n", | |
| "```\n", | |
| "3\n", | |
| "2 8 3\n", | |
| "```\n", | |
| "\n", | |
| "**Вывод**\n", | |
| "\n", | |
| "```\n", | |
| "5\n", | |
| "```\n", | |
| "\n", | |
| "**Ввод**\n", | |
| "\n", | |
| "```\n", | |
| "4\n", | |
| "7 12 1 9\n", | |
| "```\n", | |
| "\n", | |
| "**Вывод**\n", | |
| "\n", | |
| "```\n", | |
| "21\n", | |
| "```\n", | |
| "\n", | |
| "Это примеры для задачи про ожерелье. Видно, что при оптимальной игре Иван может получить определенную суммарную ценность камней." | |
| ], | |
| "metadata": { | |
| "id": "pcsuRDcJjwGP" | |
| } | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "## Решение 1\n", | |
| "\n", | |
| "Проходит не все тесты" | |
| ], | |
| "metadata": { | |
| "id": "N1DqJTmCkJc_" | |
| } | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "n = int(input())\n", | |
| "stones = list(map(int, input().split()))\n", | |
| "\n", | |
| "# Префиксные суммы\n", | |
| "prefix = [0] * (n + 1)\n", | |
| "for i in range(n):\n", | |
| " prefix[i + 1] = prefix[i] + stones[i]\n", | |
| "\n", | |
| "def get_sum(i, j):\n", | |
| " return prefix[j + 1] - prefix[i]\n", | |
| "\n", | |
| "# dp[i][j] = максимум для текущего игрока из камней [i, j]\n", | |
| "memo = {}\n", | |
| "\n", | |
| "def max_score(i, j):\n", | |
| " if i > j:\n", | |
| " return 0\n", | |
| " if i == j:\n", | |
| " return stones[i]\n", | |
| "\n", | |
| " if (i, j) in memo:\n", | |
| " return memo[(i, j)]\n", | |
| "\n", | |
| " # Берём левый или правый камень\n", | |
| " take_left = stones[i] + get_sum(i + 1, j) - max_score(i + 1, j)\n", | |
| " take_right = stones[j] + get_sum(i, j - 1) - max_score(i, j - 1)\n", | |
| "\n", | |
| " result = max(take_left, take_right)\n", | |
| " memo[(i, j)] = result\n", | |
| " return result\n", | |
| "\n", | |
| "print(max_score(0, n - 1))\n" | |
| ], | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "a7dLY7-PkL0o", | |
| "outputId": "1ce223ad-8c55-4b4e-d9d7-0376aae05256" | |
| }, | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "name": "stdout", | |
| "text": [ | |
| "4\n", | |
| "7 12 1 9\n", | |
| "21\n" | |
| ] | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "## Решение 2\n", | |
| "\n", | |
| "Проходит не все тесты" | |
| ], | |
| "metadata": { | |
| "id": "AlHLxVnLkMnm" | |
| } | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "n = int(input())\n", | |
| "stones = list(map(int, input().split()))\n", | |
| "\n", | |
| "memo = {} # Словарь для сохранения уже посчитанных результатов\n", | |
| "\n", | |
| "def max_sum(left, right):\n", | |
| " # Если камней не осталось\n", | |
| " if left > right:\n", | |
| " return 0\n", | |
| "\n", | |
| " # Если остался один камень - просто берем его\n", | |
| " if left == right:\n", | |
| " return stones[left]\n", | |
| "\n", | |
| " # Если уже считали для этих границ - берем готовый ответ\n", | |
| " if (left, right) in memo:\n", | |
| " return memo[(left, right)]\n", | |
| "\n", | |
| " # Считаем сумму всех камней между left и right\n", | |
| " total = sum(stones[left:right+1])\n", | |
| "\n", | |
| " # Вариант 1: берем ЛЕВЫЙ камень\n", | |
| " # Тогда противник играет на оставшихся камнях и получит max_sum(left+1, right)\n", | |
| " # А мы получим: вся сумма минус то, что получит противник\n", | |
| " option1 = total - max_sum(left + 1, right)\n", | |
| "\n", | |
| " # Вариант 2: берем ПРАВЫЙ камень\n", | |
| " # Аналогично\n", | |
| " option2 = total - max_sum(left, right - 1)\n", | |
| "\n", | |
| " # Выбираем лучший вариант\n", | |
| " result = max(option1, option2)\n", | |
| "\n", | |
| " # Сохраняем результат\n", | |
| " memo[(left, right)] = result\n", | |
| " return result\n", | |
| "\n", | |
| "# Иван ходит первым на всех камнях от 0 до n-1\n", | |
| "print(max_sum(0, n - 1))" | |
| ], | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "gw-w59N4kPe2", | |
| "outputId": "89dd432e-1174-442f-bb9f-cbd89cab5955" | |
| }, | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "name": "stdout", | |
| "text": [ | |
| "4\n", | |
| "7 12 1 9\n", | |
| "21\n" | |
| ] | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "## Решение 3\n", | |
| "\n", | |
| "Проходит все тесты" | |
| ], | |
| "metadata": { | |
| "id": "SxI2JLWwpIZH" | |
| } | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "n = int(input())\n", | |
| "a = list(map(int, input().split()))\n", | |
| "\n", | |
| "dp = a[:] # dp[l] = макс. разница (текущий - соперник) на отрезке [l..r]\n", | |
| "\n", | |
| "for r in range(1, n):\n", | |
| " for l in range(r - 1, -1, -1):\n", | |
| " take_left = a[l] - dp[l + 1]\n", | |
| " take_right = a[r] - dp[l]\n", | |
| " dp[l] = max(take_left, take_right)\n", | |
| "\n", | |
| "ivan = (sum(a) + dp[0]) // 2\n", | |
| "print(ivan)" | |
| ], | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "QNa6QkJopCSW", | |
| "outputId": "21ae8a5f-b30c-40e2-c629-49ca1b82b192" | |
| }, | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "name": "stdout", | |
| "text": [ | |
| "4\n", | |
| "7 12 1 9\n", | |
| "21\n" | |
| ] | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "# Задача Ладьей ходи\n", | |
| "\n", | |
| "**Иван решает шахматную задачу:**\n", | |
| "\n", | |
| "На игровом поле размером NxN клеток расположена белая ладья, черный король и пешки двух цветов. Ваша задача — за минимальное кол-во ходов ладьей съесть короля. За один ход ладья может походить по обычным шахматным правилам:\n", | |
| "\n", | |
| "• Походить по горизонтали или вертикали на любое кол-во клеток (при этом все клетки на пути должны быть пустыми).\n", | |
| "\n", | |
| "• Занять место черной пешки (съесть), если до нее можно дойти по предыдущему правилу.\n", | |
| "\n", | |
| "Необходимо посчитать минимальное кол-во ходов, за которое ладья может съесть короля (при этом ходит только ладья и нельзя есть собственные белые пешки).\n", | |
| "\n", | |
| "**Формат входных данных**\n", | |
| "\n", | |
| "В первой строке содержится одно число: N (3 ≤ N ≤ 555) — размеры поля.\n", | |
| "\n", | |
| "В следующих N строках содержатся по N символов, каждый из которых может быть R (белая ладья), K (черный король), W (белая пешка), B (черная пешка) и 0 (пустая клетка (символ заглавной буквы о латинского алфавита)).\n", | |
| "\n", | |
| "**Формат выходных данных**\n", | |
| "\n", | |
| "В ответ выведите единственное число M — минимальное кол-во ходов ладьей, чтобы съесть короля.\n", | |
| "\n", | |
| "Если съесть короля невозможно, выведите -1.\n", | |
| "\n", | |
| "**Замечание**\n", | |
| "\n", | |
| "В первом примере достаточно двух ходов, при этом неважно походить в нижний левый угол первым ходом и потом съесть короля, или походить в правый верхний (съев пешку) и потом съесть короля – оба варианта дают 2 хода.\n", | |
| "\n", | |
| "Во втором примере нельзя пройти через ряд белых пешек.\n", | |
| "\n", | |
| "**Ввод**\n", | |
| "\n", | |
| "```\n", | |
| "3\n", | |
| "R0B\n", | |
| "000\n", | |
| "00K\n", | |
| "```\n", | |
| "\n", | |
| "**Вывод**\n", | |
| "\n", | |
| "```\n", | |
| "2\n", | |
| "```\n", | |
| "\n", | |
| "**Ввод**\n", | |
| "\n", | |
| "```\n", | |
| "3\n", | |
| "R0B\n", | |
| "WWW\n", | |
| "B0K\n", | |
| "```\n", | |
| "\n", | |
| "**Вывод**\n", | |
| "\n", | |
| "```\n", | |
| "-1\n", | |
| "```" | |
| ], | |
| "metadata": { | |
| "id": "bDHFdA3skP1h" | |
| } | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "## Решение 1" | |
| ], | |
| "metadata": { | |
| "id": "7Mf3lXimm8lA" | |
| } | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "from collections import deque\n", | |
| "\n", | |
| "n = int(input())\n", | |
| "board = []\n", | |
| "for i in range(n):\n", | |
| " board.append(input())\n", | |
| "\n", | |
| "# Найти позиции ладьи и короля\n", | |
| "rook_pos = None\n", | |
| "king_pos = None\n", | |
| "\n", | |
| "for i in range(n):\n", | |
| " for j in range(n):\n", | |
| " if board[i][j] == 'R':\n", | |
| " rook_pos = (i, j)\n", | |
| " elif board[i][j] == 'K':\n", | |
| " king_pos = (i, j)\n", | |
| "\n", | |
| "def f():\n", | |
| " queue = deque([(rook_pos[0], rook_pos[1], 0)])\n", | |
| " visited = set()\n", | |
| " visited.add(rook_pos)\n", | |
| "\n", | |
| " while queue:\n", | |
| " x, y, moves = queue.popleft()\n", | |
| "\n", | |
| " if (x, y) == king_pos:\n", | |
| " return moves\n", | |
| "\n", | |
| " # Ладья ходит по 4 направлениям (горизонталь и вертикаль)\n", | |
| " for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:\n", | |
| " nx, ny = x + dx, y + dy\n", | |
| "\n", | |
| " # Двигаемся в одном направлении, пока не упремся\n", | |
| " while 0 <= nx < n and 0 <= ny < n:\n", | |
| " cell = board[nx][ny]\n", | |
| "\n", | |
| " # Белая пешка - непреодолимое препятствие\n", | |
| " if cell == 'W':\n", | |
| " break\n", | |
| "\n", | |
| " if (nx, ny) not in visited:\n", | |
| " visited.add((nx, ny))\n", | |
| " queue.append((nx, ny, moves + 1))\n", | |
| "\n", | |
| " # Если съели короля или черную пешку, дальше не идем\n", | |
| " if cell in ['K', 'B']:\n", | |
| " break\n", | |
| "\n", | |
| " nx += dx\n", | |
| " ny += dy\n", | |
| "\n", | |
| " return -1\n", | |
| "\n", | |
| "print(f())\n" | |
| ], | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "Z75LLJMdm-SE", | |
| "outputId": "5de3e640-a60c-4e29-88e5-2655f4cb6731" | |
| }, | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "name": "stdout", | |
| "text": [ | |
| "3\n", | |
| "R0B\n", | |
| "000\n", | |
| "00K\n", | |
| "2\n" | |
| ] | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "## Решение 2" | |
| ], | |
| "metadata": { | |
| "id": "nHxZH-Akm-lp" | |
| } | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "# Читаем размер поля\n", | |
| "n = int(input())\n", | |
| "\n", | |
| "# Читаем само поле\n", | |
| "board = []\n", | |
| "for i in range(n):\n", | |
| " board.append(input().strip())\n", | |
| "\n", | |
| "# Находим где стоит ладья и где король\n", | |
| "rook_row, rook_col = 0, 0\n", | |
| "king_row, king_col = 0, 0\n", | |
| "\n", | |
| "for i in range(n):\n", | |
| " for j in range(n):\n", | |
| " if board[i][j] == 'R':\n", | |
| " rook_row, rook_col = i, j\n", | |
| " elif board[i][j] == 'K':\n", | |
| " king_row, king_col = i, j\n", | |
| "\n", | |
| "# Очередь для BFS: список из (строка, столбец, количество ходов)\n", | |
| "queue = []\n", | |
| "queue.append((rook_row, rook_col, 0))\n", | |
| "\n", | |
| "# Запоминаем где уже были\n", | |
| "visited = []\n", | |
| "visited.append((rook_row, rook_col))\n", | |
| "\n", | |
| "# 4 направления: вверх, вниз, влево, вправо\n", | |
| "directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n", | |
| "\n", | |
| "# Индекс для обхода очереди\n", | |
| "index = 0\n", | |
| "\n", | |
| "# Переменная для ответа\n", | |
| "answer = -1\n", | |
| "\n", | |
| "# Начинаем поиск\n", | |
| "while index < len(queue):\n", | |
| " row, col, moves = queue[index]\n", | |
| " index += 1\n", | |
| "\n", | |
| " # Если дошли до короля - запоминаем ответ и выходим!\n", | |
| " if row == king_row and col == king_col:\n", | |
| " answer = moves\n", | |
| " break\n", | |
| "\n", | |
| " # Пробуем пойти в каждом из 4 направлений\n", | |
| " for dr, dc in directions:\n", | |
| " # Начинаем идти в этом направлении\n", | |
| " new_row = row + dr\n", | |
| " new_col = col + dc\n", | |
| "\n", | |
| " # Идем пока не выйдем за границу поля\n", | |
| " while 0 <= new_row < n and 0 <= new_col < n:\n", | |
| " cell = board[new_row][new_col]\n", | |
| "\n", | |
| " # Белая пешка - СТОП! Не можем пройти\n", | |
| " if cell == 'W':\n", | |
| " break\n", | |
| "\n", | |
| " # Эту клетку можем посетить (если еще не были)\n", | |
| " if (new_row, new_col) not in visited:\n", | |
| " visited.append((new_row, new_col))\n", | |
| " queue.append((new_row, new_col, moves + 1))\n", | |
| "\n", | |
| " # Если съели черную пешку или короля - дальше идти нельзя\n", | |
| " if cell == 'B' or cell == 'K':\n", | |
| " break\n", | |
| "\n", | |
| " # Идем дальше в том же направлении\n", | |
| " new_row += dr\n", | |
| " new_col += dc\n", | |
| "\n", | |
| "# Выводим ответ\n", | |
| "print(answer)\n" | |
| ], | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "Ynz8vTxQnAM3", | |
| "outputId": "32302c87-6050-4dd6-ad2d-bdb54d4f2389" | |
| }, | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "name": "stdout", | |
| "text": [ | |
| "3\n", | |
| "R0B\n", | |
| "WWW\n", | |
| "B0K\n", | |
| "-1\n" | |
| ] | |
| } | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "## Решение 3" | |
| ], | |
| "metadata": { | |
| "id": "5dK36v3WsbQY" | |
| } | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "n = int(input())\n", | |
| "board = []\n", | |
| "sr = sc = kr = kc = -1\n", | |
| "\n", | |
| "# читаем поле и запоминаем координаты ладьи и короля\n", | |
| "for i in range(n):\n", | |
| " row = input().strip()\n", | |
| " board.append(row)\n", | |
| " for j, ch in enumerate(row):\n", | |
| " if ch == 'R':\n", | |
| " sr, sc = i, j\n", | |
| " elif ch == 'K':\n", | |
| " kr, kc = i, j\n", | |
| "\n", | |
| "# BFS: очередь как список + индекс головы\n", | |
| "dist = [[-1] * n for _ in range(n)]\n", | |
| "dist[sr][sc] = 0\n", | |
| "q = [(sr, sc)]\n", | |
| "head = 0\n", | |
| "\n", | |
| "dirs = [(1,0), (-1,0), (0,1), (0,-1)]\n", | |
| "\n", | |
| "while head < len(q):\n", | |
| " x, y = q[head]\n", | |
| " head += 1\n", | |
| " d = dist[x][y]\n", | |
| "\n", | |
| " # идем лучами во все стороны\n", | |
| " for dx, dy in dirs:\n", | |
| " nx, ny = x + dx, y + dy\n", | |
| " # W — белая пешка: стена, через нее нельзя\n", | |
| " while 0 <= nx < n and 0 <= ny < n and board[nx][ny] != 'W':\n", | |
| " if dist[nx][ny] == -1:\n", | |
| " dist[nx][ny] = d + 1\n", | |
| " q.append((nx, ny))\n", | |
| " # на B и K можно встать, но дальше в этом направлении нельзя\n", | |
| " if board[nx][ny] == 'B' or board[nx][ny] == 'K':\n", | |
| " break\n", | |
| " nx += dx\n", | |
| " ny += dy\n", | |
| "\n", | |
| "# если король недостижим, будет -1\n", | |
| "print(dist[kr][kc])\n" | |
| ], | |
| "metadata": { | |
| "colab": { | |
| "base_uri": "https://localhost:8080/" | |
| }, | |
| "id": "aJPIKTRnsc1Q", | |
| "outputId": "1b8ecfa5-e802-4b22-9841-df099f94fd3c" | |
| }, | |
| "execution_count": null, | |
| "outputs": [ | |
| { | |
| "output_type": "stream", | |
| "name": "stdout", | |
| "text": [ | |
| "3\n", | |
| "R0B\n", | |
| "WWW\n", | |
| "B0K\n", | |
| "-1\n" | |
| ] | |
| } | |
| ] | |
| } | |
| ] | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment