{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Семинар 2. Два указателя, окно, префиксные суммы\n",
    "\n",
    "На этой паре вы решите задачи на массивы: частотный подсчёт, два указателя, скользящее окно, префиксные суммы и разностный массив. Сдаёте **этот** файл в LMS.\n",
    "\n",
    "На семинаре 1 дополнительная память $O(1)$ значила «несколько переменных». Здесь массив **нужен**: индекс бывает позицией во входе, а бывает значением. Квадратный перебор по длине отрезка или по всем парам на больших тестах не успеет: тестер даёт **TLE** (лимит 2 секунды на тест), не только «не тот ответ».\n",
    "\n",
    "Задачи 1–8 — основа занятия. Девятая и десятая — если после восьмой осталось время.\n",
    "\n",
    "Можно спрашивать соседа и семинариста. Готовое решение копировать не стоит: тесты это не заменят, а на зачёте рядом никого не будет.\n"
   ],
   "id": "intro"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Как устроен ноутбук\n",
    "\n",
    "Как на семинаре 1: ячейки **Markdown** и **Code**; командный режим — `Esc`, правка — `Enter`; `Shift+Enter` выполняет ячейку.\n",
    "\n",
    "Скачайте с сайта курса [этот файл `.ipynb`](https://learn.ai.msu.ru/algo/1/02/seminar.ipynb) и файл [`lab02_tests.py`](https://learn.ai.msu.ru/algo/1/02/lab02_tests.py) **в одну папку**. Без файла тестов проверка не запустится. Откройте ноутбук из этой папки.\n"
   ],
   "id": "jupyter"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ввод, вывод и тесты\n",
    "\n",
    "Решение — **функция без аргументов**: внутри `input` и `print`, как в контесте. Тест подставляет входы сам. **Не заполняйте поле ввода Jupyter.**\n",
    "\n",
    "В каждой задаче стоит заглушка: она что-то читает и печатает неверный ответ. Сначала запустите ячейку: увидите «не OK» или TLE, вход, «ожидалось» и «получено». Потом замените тело функции.\n",
    "\n",
    "Импорт тестов стоит **в каждой** ячейке с решением. Если перезапустите ядро, достаточно снова выполнить эту ячейку — отдельно «подключать библиотеку в начале» не обязательно, хотя общая ячейка ниже тоже есть.\n"
   ],
   "id": "how_tests"
  },
  {
   "cell_type": "code",
   "metadata": {},
   "source": [
    "import sys\n",
    "from pathlib import Path\n",
    "\n",
    "sys.path[:0] = [str(Path.cwd())]\n",
    "\n",
    "from lab02_tests import (\n",
    "    test_task1,\n",
    "    test_task2,\n",
    "    test_task3,\n",
    "    test_task4,\n",
    "    test_task5,\n",
    "    test_task6,\n",
    "    test_task7,\n",
    "    test_task8,\n",
    "    test_task9,\n",
    "    test_task10,\n",
    ")\n",
    "\n",
    "print('Тесты подключены')\n"
   ],
   "execution_count": null,
   "outputs": [],
   "id": "import_tests"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Частотный массив: индекс — значение\n",
    "\n",
    "На семинаре 1 индекс обычно значил позицию во входе. Здесь диапазон значений маленький и известен заранее: от $0$ до $1000$. Тогда ячейка массива может значить не «кто стоит на месте $i$», а «что известно про число $v$».\n",
    "\n",
    "После одного прохода по входу у вас есть сводка по всем значениям. Нуля в сводке и «значение ни разу не встретилось» — разные вещи.\n"
   ],
   "id": "t1_lesson"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Найдите самое редкое встретившееся значение; при равной частоте — меньшее число.\n",
    "\n",
    "### Задача 1. Самое редкое значение\n",
    "\n",
    "Дан массив целых чисел из диапазона от $0$ до $1000$ включительно. Среди значений, которые встречаются в массиве хотя бы один раз, найдите то, которое встречается наименьшее число раз. Если таких значений несколько, выведите меньшее из них.\n",
    "\n",
    "**Вход.** Первая строка: целое $n$ ($1 \\le n \\le 2\\cdot 10^5$). Вторая строка: $n$ целых чисел $a_i$ ($0 \\le a_i \\le 1000$).\n",
    "\n",
    "**Выход.** Одно целое — ответ.\n",
    "\n",
    "```\n",
    "-> 6\n",
    "-> 3 1 3 2 1 3\n",
    "--\n",
    "<- 2\n",
    "```\n",
    "\n",
    "```\n",
    "-> 5\n",
    "-> 7 7 7 7 7\n",
    "--\n",
    "<- 7\n",
    "```\n",
    "\n",
    "```\n",
    "-> 4\n",
    "-> 0 1000 0 5\n",
    "--\n",
    "<- 5\n",
    "```\n"
   ],
   "id": "t1_md"
  },
  {
   "cell_type": "code",
   "metadata": {},
   "source": [
    "import sys\n",
    "from pathlib import Path\n",
    "\n",
    "sys.path[:0] = [str(Path.cwd())]\n",
    "from lab02_tests import test_task1\n",
    "\n",
    "\n",
    "def task1():\n",
    "    n = int(input())\n",
    "    a = list(map(int, input().split()))\n",
    "    print(0)\n",
    "\n",
    "\n",
    "test_task1(task1)\n"
   ],
   "execution_count": null,
   "outputs": [],
   "id": "t1_code"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Два указателя вперёд: слияние\n",
    "\n",
    "Даны два уже упорядоченных массива. Нужен один общий, тоже по неубыванию.\n",
    "\n",
    "Сортировать склейку целиком можно, но приём этой недели другой: оба массива уже стоят в нужном порядке, и достаточно смотреть на их «головы». Подумайте, кого взять в ответ сейчас и что делать, когда один из массивов кончился.\n",
    "\n",
    "Пустой массив бывает: $n = 0$ или $m = 0$. Тогда `input()` вернёт пустую строку.\n"
   ],
   "id": "t2_lesson"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Слейте два упорядоченных массива в один.\n",
    "\n",
    "### Задача 2. Слияние двух массивов\n",
    "\n",
    "Даны два массива, каждый упорядочен по неубыванию. Слейте их в один массив, тоже упорядоченный по неубыванию.\n",
    "\n",
    "**Вход.** Первая строка: $n$ и $m$ ($0 \\le n, m \\le 2\\cdot 10^5$, $n+m \\ge 1$). Вторая строка: $n$ чисел (если $n = 0$, строка пустая). Третья: $m$ чисел (если $m = 0$, строка пустая). $|a_i|, |b_i| \\le 10^9$.\n",
    "\n",
    "**Выход.** Одна строка из $n+m$ чисел через пробел.\n",
    "\n",
    "```\n",
    "-> 3 3\n",
    "-> 1 3 5\n",
    "-> 2 4 6\n",
    "--\n",
    "<- 1 2 3 4 5 6\n",
    "```\n",
    "\n",
    "```\n",
    "-> 2 3\n",
    "-> 1 1\n",
    "-> 1 1 2\n",
    "--\n",
    "<- 1 1 1 1 2\n",
    "```\n",
    "\n",
    "```\n",
    "-> 0 2\n",
    "->\n",
    "-> 4 7\n",
    "--\n",
    "<- 4 7\n",
    "```\n"
   ],
   "id": "t2_md"
  },
  {
   "cell_type": "code",
   "metadata": {},
   "source": [
    "import sys\n",
    "from pathlib import Path\n",
    "\n",
    "sys.path[:0] = [str(Path.cwd())]\n",
    "from lab02_tests import test_task2\n",
    "\n",
    "\n",
    "def task2():\n",
    "    n, m = map(int, input().split())\n",
    "    a = list(map(int, input().split()))\n",
    "    b = list(map(int, input().split()))\n",
    "    print(0)\n",
    "\n",
    "\n",
    "test_task2(task2)\n"
   ],
   "execution_count": null,
   "outputs": [],
   "id": "t2_code"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Два указателя с концов\n",
    "\n",
    "Массив уже упорядочен по неубыванию. Нужны два разных индекса, сумма значений равна $S$.\n",
    "\n",
    "Перебор всех пар на больших $n$ не успеет (TLE). Раз массив упорядочен, концы отрезка несут информацию: слишком большая или слишком маленькая сумма подсказывает, какой конец сузить. Индексы в ответе — с единицы, $i < j$. Если пар несколько, тесты принимают любую верную.\n"
   ],
   "id": "t3_lesson"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Найдите любую пару индексов с суммой $S$.\n",
    "\n",
    "### Задача 3. Пара с суммой S\n",
    "\n",
    "Дан массив из $n$ целых чисел, упорядоченный по неубыванию, и число $S$. Найдите два элемента с разными индексами, сумма которых равна $S$.\n",
    "\n",
    "Гарантируется, что хотя бы одна такая пара существует. Если подходящих пар несколько, выведите любую.\n",
    "\n",
    "**Вход.** Первая строка: $n$ и $S$ ($2 \\le n \\le 2\\cdot 10^5$, $|S| \\le 2\\cdot 10^9$). Вторая строка: $n$ чисел, $a_1 \\le \\ldots \\le a_n$, $|a_i| \\le 10^9$.\n",
    "\n",
    "**Выход.** Два целых $i$ и $j$ ($1 \\le i < j \\le n$).\n",
    "\n",
    "```\n",
    "-> 4 9\n",
    "-> 2 7 11 15\n",
    "--\n",
    "<- 1 2\n",
    "```\n",
    "\n",
    "```\n",
    "-> 4 18\n",
    "-> 2 7 11 15\n",
    "--\n",
    "<- 2 3\n",
    "```\n",
    "\n",
    "```\n",
    "-> 5 8\n",
    "-> 1 2 3 4 4\n",
    "--\n",
    "<- 4 5\n",
    "```\n"
   ],
   "id": "t3_md"
  },
  {
   "cell_type": "code",
   "metadata": {},
   "source": [
    "import sys\n",
    "from pathlib import Path\n",
    "\n",
    "sys.path[:0] = [str(Path.cwd())]\n",
    "from lab02_tests import test_task3\n",
    "\n",
    "\n",
    "def task3():\n",
    "    n, s = map(int, input().split())\n",
    "    a = list(map(int, input().split()))\n",
    "    print(1, 2)\n",
    "\n",
    "\n",
    "test_task3(task3)\n"
   ],
   "execution_count": null,
   "outputs": [],
   "id": "t3_code"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Префиксные суммы\n",
    "\n",
    "Нужны суммы на многих отрезках $[l, r]$ (нумерация с единицы, оба конца включительно). Заново складывать элементы отрезка на каждый запрос на больших $n$ и $q$ не успеет.\n",
    "\n",
    "Имеет смысл один раз подготовить массив и дальше отвечать на запрос, не глядя внутрь отрезка. Аккуратно решите, что брать на границах: «до $r$ включительно» легко спутать с полуинтервалом.\n"
   ],
   "id": "t4_lesson"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ответьте на серию запросов, не складывая отрезок заново каждый раз.\n",
    "\n",
    "### Задача 4. Сумма на отрезках\n",
    "\n",
    "Дан массив из $n$ целых чисел. Поступают $q$ запросов: для каждого выведите сумму элементов на отрезке с индексами от $l$ до $r$ включительно (нумерация с единицы).\n",
    "\n",
    "**Вход.** Первая строка: $n$ и $q$ ($1 \\le n, q \\le 2\\cdot 10^5$). Вторая: $n$ чисел, $|a_i| \\le 10^9$. Далее $q$ строк: $l$ $r$ ($1 \\le l \\le r \\le n$).\n",
    "\n",
    "**Выход.** $q$ строк: в $i$-й — сумма для $i$-го запроса.\n",
    "\n",
    "```\n",
    "-> 5 3\n",
    "-> 1 2 3 4 5\n",
    "-> 1 1\n",
    "-> 2 4\n",
    "-> 1 5\n",
    "--\n",
    "<- 1\n",
    "<- 9\n",
    "<- 15\n",
    "```\n",
    "\n",
    "```\n",
    "-> 3 2\n",
    "-> -5 10 -3\n",
    "-> 1 3\n",
    "-> 2 2\n",
    "--\n",
    "<- 2\n",
    "<- 10\n",
    "```\n"
   ],
   "id": "t4_md"
  },
  {
   "cell_type": "code",
   "metadata": {},
   "source": [
    "import sys\n",
    "from pathlib import Path\n",
    "\n",
    "sys.path[:0] = [str(Path.cwd())]\n",
    "from lab02_tests import test_task4\n",
    "\n",
    "\n",
    "def task4():\n",
    "    n, q = map(int, input().split())\n",
    "    a = list(map(int, input().split()))\n",
    "    for _ in range(q):\n",
    "        l, r = map(int, input().split())\n",
    "        print(0)\n",
    "\n",
    "\n",
    "test_task4(task4)\n"
   ],
   "execution_count": null,
   "outputs": [],
   "id": "t4_code"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Скользящее окно фиксированной длины\n",
    "\n",
    "Нужна сумма каждого отрезка длины $k$: с позиции $1$, затем $2$, и так до конца.\n",
    "\n",
    "Соседние окна почти совпадают: отличаются парой элементов на краях. Можно опереться на предыдущую задачу — или обойтись без длинного предподсчёта. Считать каждое окно с нуля при большом $k$ не успеет.\n"
   ],
   "id": "t5_lesson"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Выведите суммы всех отрезков длины $k$.\n",
    "\n",
    "### Задача 5. Окно длины $k$\n",
    "\n",
    "Дан массив из $n$ целых чисел и число $k$. Для каждого отрезка длины $k$ выведите сумму его элементов. Отрезки идут подряд: с индексов $1\\ldots k$, $2\\ldots k+1$, …, $n-k+1\\ldots n$ (нумерация с единицы).\n",
    "\n",
    "**Вход.** Первая строка: $n$ и $k$ ($1 \\le k \\le n \\le 2\\cdot 10^5$). Вторая: $n$ чисел, $|a_i| \\le 10^9$.\n",
    "\n",
    "**Выход.** Одна строка из $n-k+1$ чисел — суммы в порядке возрастания левой границы.\n",
    "\n",
    "```\n",
    "-> 5 3\n",
    "-> 1 2 3 4 5\n",
    "--\n",
    "<- 6 9 12\n",
    "```\n",
    "\n",
    "```\n",
    "-> 4 4\n",
    "-> 2 -1 2 -1\n",
    "--\n",
    "<- 2\n",
    "```\n",
    "\n",
    "```\n",
    "-> 6 1\n",
    "-> 7 0 7 0 7 0\n",
    "--\n",
    "<- 7 0 7 0 7 0\n",
    "```\n"
   ],
   "id": "t5_md"
  },
  {
   "cell_type": "code",
   "metadata": {},
   "source": [
    "import sys\n",
    "from pathlib import Path\n",
    "\n",
    "sys.path[:0] = [str(Path.cwd())]\n",
    "from lab02_tests import test_task5\n",
    "\n",
    "\n",
    "def task5():\n",
    "    n, k = map(int, input().split())\n",
    "    a = list(map(int, input().split()))\n",
    "    print(0)\n",
    "\n",
    "\n",
    "test_task5(task5)\n"
   ],
   "execution_count": null,
   "outputs": [],
   "id": "t5_code"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Перестановка на месте\n",
    "\n",
    "Нужно изменить порядок только части элементов: положительные должны идти в обратном порядке появления, остальные остаться где были.\n",
    "\n",
    "Собрать нужные числа во второй список — верный вывод, но условие просит дополнительную память $O(1)$ кроме данного массива. Тесты это не проверяют: это требование к тому, как вы думаете. Подумайте, какими двумя позициями можно идти по массиву, не копируя положительные отдельно.\n"
   ],
   "id": "t6_lesson"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Переставьте положительные, не копируя их во второй список.\n",
    "\n",
    "### Задача 6. Реверс положительных\n",
    "\n",
    "Дан массив из $n$ целых чисел. Числа $\\le 0$ остаются на местах. Положительные нужно переставить в обратном порядке их появления.\n",
    "\n",
    "Разрешается изменять данный массив. Дополнительная память кроме него — $O(1)$: нельзя собирать положительные в отдельный список.\n",
    "\n",
    "**Вход.** Первая строка: $n$ ($1 \\le n \\le 2\\cdot 10^5$). Вторая: $n$ чисел, $|a_i| \\le 10^9$.\n",
    "\n",
    "**Выход.** Одна строка из $n$ чисел.\n",
    "\n",
    "```\n",
    "-> 5\n",
    "-> 1 -2 3 0 4\n",
    "--\n",
    "<- 4 -2 3 0 1\n",
    "```\n",
    "\n",
    "```\n",
    "-> 3\n",
    "-> 1 2 3\n",
    "--\n",
    "<- 3 2 1\n",
    "```\n",
    "\n",
    "```\n",
    "-> 3\n",
    "-> -1 0 -2\n",
    "--\n",
    "<- -1 0 -2\n",
    "```\n",
    "\n",
    "```\n",
    "-> 3\n",
    "-> 1 -1 2\n",
    "--\n",
    "<- 2 -1 1\n",
    "```\n"
   ],
   "id": "t6_md"
  },
  {
   "cell_type": "code",
   "metadata": {},
   "source": [
    "import sys\n",
    "from pathlib import Path\n",
    "\n",
    "sys.path[:0] = [str(Path.cwd())]\n",
    "from lab02_tests import test_task6\n",
    "\n",
    "\n",
    "def task6():\n",
    "    n = int(input())\n",
    "    a = list(map(int, input().split()))\n",
    "    print(*a)\n",
    "\n",
    "\n",
    "test_task6(task6)\n"
   ],
   "execution_count": null,
   "outputs": [],
   "id": "t6_code"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Разностный массив\n",
    "\n",
    "Дан массив из нулей и много операций «прибавить $x$ на отрезке». Идти циклом по отрезку на каждую операцию на больших $n$ и $q$ не успеет.\n",
    "\n",
    "Это обратная сторона префиксных сумм: обновление отрезка можно оставить следами на границах, а сам массив восстановить одним проходом в конце. Снова следите за тем, включён ли правый конец.\n"
   ],
   "id": "t7_lesson"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Выполните все прибавления и выведите итоговый массив.\n",
    "\n",
    "### Задача 7. Прибавления на отрезках\n",
    "\n",
    "Дан массив из $n$ нулей. Выполняется $q$ операций: к каждому элементу на отрезке с индексами от $l$ до $r$ включительно прибавить $x$. Выведите массив после всех операций. Нумерация с единицы.\n",
    "\n",
    "**Вход.** Первая строка: $n$ и $q$ ($1 \\le n, q \\le 2\\cdot 10^5$). Далее $q$ строк: $l$ $r$ $x$ ($1 \\le l \\le r \\le n$, $|x| \\le 10^9$).\n",
    "\n",
    "**Выход.** Одна строка из $n$ чисел.\n",
    "\n",
    "```\n",
    "-> 5 2\n",
    "-> 1 3 2\n",
    "-> 2 5 1\n",
    "--\n",
    "<- 2 3 3 1 1\n",
    "```\n",
    "\n",
    "```\n",
    "-> 4 3\n",
    "-> 1 4 5\n",
    "-> 2 2 -3\n",
    "-> 3 4 1\n",
    "--\n",
    "<- 5 2 6 6\n",
    "```\n",
    "\n",
    "```\n",
    "-> 3 1\n",
    "-> 2 3 0\n",
    "--\n",
    "<- 0 0 0\n",
    "```\n"
   ],
   "id": "t7_md"
  },
  {
   "cell_type": "code",
   "metadata": {},
   "source": [
    "import sys\n",
    "from pathlib import Path\n",
    "\n",
    "sys.path[:0] = [str(Path.cwd())]\n",
    "from lab02_tests import test_task7\n",
    "\n",
    "\n",
    "def task7():\n",
    "    n, q = map(int, input().split())\n",
    "    for _ in range(q):\n",
    "        l, r, x = map(int, input().split())\n",
    "    print(*([0] * n))\n",
    "\n",
    "\n",
    "test_task7(task7)\n"
   ],
   "execution_count": null,
   "outputs": [],
   "id": "t7_code"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Медиана и тот же диапазон\n",
    "\n",
    "Диапазон снова $0\\ldots 1000$. Медиана здесь — элемент на заданной позиции, если выписать все $n$ чисел по неубыванию (позиции с единицы). Для нечётного и чётного $n$ позиция считается по формуле в условии.\n",
    "\n",
    "Сортировка сравнением даст верный ответ. Приём пары — опереться на сводку по значениям, как в первой задаче, и понять, когда накопленное количество уже накрыло нужную позицию. Так вы готовитесь к сортировке подсчётом, не вызывая `sort`.\n"
   ],
   "id": "t8_lesson"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Найдите медиану в смысле позиции из условия.\n",
    "\n",
    "### Задача 8. Медиана набора\n",
    "\n",
    "Дано $n$ целых чисел из диапазона от $0$ до $1000$ включительно. Медиана — элемент на позиции $\\lfloor (n+1)/2 \\rfloor$ после выписывания всех чисел по неубыванию (позиции с единицы).\n",
    "\n",
    "**Вход.** Первая строка: $n$ ($1 \\le n \\le 2\\cdot 10^5$). Вторая: $n$ чисел $0 \\le a_i \\le 1000$.\n",
    "\n",
    "**Выход.** Одно число — медиана.\n",
    "\n",
    "```\n",
    "-> 5\n",
    "-> 10 1 10 5 10\n",
    "--\n",
    "<- 10\n",
    "```\n",
    "\n",
    "```\n",
    "-> 4\n",
    "-> 1 3 2 4\n",
    "--\n",
    "<- 2\n",
    "```\n",
    "\n",
    "```\n",
    "-> 1\n",
    "-> 0\n",
    "--\n",
    "<- 0\n",
    "```\n"
   ],
   "id": "t8_md"
  },
  {
   "cell_type": "code",
   "metadata": {},
   "source": [
    "import sys\n",
    "from pathlib import Path\n",
    "\n",
    "sys.path[:0] = [str(Path.cwd())]\n",
    "from lab02_tests import test_task8\n",
    "\n",
    "\n",
    "def task8():\n",
    "    n = int(input())\n",
    "    a = list(map(int, input().split()))\n",
    "    print(0)\n",
    "\n",
    "\n",
    "test_task8(task8)\n"
   ],
   "execution_count": null,
   "outputs": [],
   "id": "t8_code"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Если осталось время\n",
    "\n",
    "Две задачи ниже — для тех, кто закрыл тестами первые восемь. Новых обязательных конструкций нет: снова указатели, частоты по остатку и аккуратная перестановка.\n"
   ],
   "id": "spare"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Пара с расстоянием и модулем\n",
    "\n",
    "Нужна максимальная сумма двух элементов с разными индексами: сумма делится на $M$, номера отличаются не меньше чем на $K$. Пары нет — ответ $0$.\n",
    "\n",
    "Перебор всех пар не успеет. Подумайте, что достаточно помнить про уже просмотренные элементы, которые отстоят от текущего достаточно далеко, и как здесь помогает остаток по модулю $M$.\n"
   ],
   "id": "t9_lesson"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Найдите максимальную подходящую сумму или $0$.\n",
    "\n",
    "### Задача 9. Максимальная сумма пары\n",
    "\n",
    "Дана последовательность из $n$ чисел, а также $K$ и $M$. Среди пар с разными индексами найдите максимальную сумму, которая делится на $M$, если номера отличаются не меньше чем на $K$. Если подходящей пары нет, выведите $0$.\n",
    "\n",
    "Нумерация с единицы: у соседних номера отличаются на $1$.\n",
    "\n",
    "**Вход.** Первая строка: $n$, $K$, $M$ ($2 \\le n \\le 2\\cdot 10^5$, $1 \\le K < n$, $1 \\le M \\le 1000$). Вторая: $n$ чисел $0 \\le a_i \\le 2\\cdot 10^6$.\n",
    "\n",
    "**Выход.** Одно число — максимальная подходящая сумма либо $0$.\n",
    "\n",
    "```\n",
    "-> 10 4 101\n",
    "-> 240 26 35 8 152 222 183 41 268 6\n",
    "--\n",
    "<- 303\n",
    "```\n",
    "\n",
    "```\n",
    "-> 5 2 10\n",
    "-> 3 3 3 3 7\n",
    "--\n",
    "<- 10\n",
    "```\n",
    "\n",
    "```\n",
    "-> 4 3 2\n",
    "-> 1 1 1 1\n",
    "--\n",
    "<- 2\n",
    "```\n"
   ],
   "id": "t9_md"
  },
  {
   "cell_type": "code",
   "metadata": {},
   "source": [
    "import sys\n",
    "from pathlib import Path\n",
    "\n",
    "sys.path[:0] = [str(Path.cwd())]\n",
    "from lab02_tests import test_task9\n",
    "\n",
    "\n",
    "def task9():\n",
    "    n, k, m = map(int, input().split())\n",
    "    a = list(map(int, input().split()))\n",
    "    print(0)\n",
    "\n",
    "\n",
    "test_task9(task9)\n"
   ],
   "execution_count": null,
   "outputs": [],
   "id": "t9_code"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Следующая перестановка\n",
    "\n",
    "Нужна следующая последовательность из тех же чисел в лексикографическом порядке. Одинаковые значения неразличимы. Если текущая уже последняя, берут первую — неубывающую.\n",
    "\n",
    "Полный перечень перестановок строить не нужно: достаточно понять, чем соседние в порядке последовательности отличаются локально.\n"
   ],
   "id": "t10_lesson"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Сдвиньте последовательность на следующую в лексикографическом порядке.\n",
    "\n",
    "### Задача 10. Следующая перестановка\n",
    "\n",
    "Дана последовательность из $n$ целых чисел. Замените её на следующую перестановку этих чисел (с учётом повторов). Если данная уже последняя, замените на первую (неубывающую).\n",
    "\n",
    "Лексикографический порядок: $p$ меньше $q$, если на первой позиции, где они различаются, в $p$ стоит меньшее число.\n",
    "\n",
    "**Вход.** Первая строка: $n$ ($1 \\le n \\le 10^5$). Вторая: $n$ чисел, $|a_i| \\le 10^9$.\n",
    "\n",
    "**Выход.** Одна строка из $n$ чисел.\n",
    "\n",
    "```\n",
    "-> 3\n",
    "-> 1 2 3\n",
    "--\n",
    "<- 1 3 2\n",
    "```\n",
    "\n",
    "```\n",
    "-> 3\n",
    "-> 3 2 1\n",
    "--\n",
    "<- 1 2 3\n",
    "```\n",
    "\n",
    "```\n",
    "-> 3\n",
    "-> 1 1 5\n",
    "--\n",
    "<- 1 5 1\n",
    "```\n",
    "\n",
    "```\n",
    "-> 4\n",
    "-> 1 3 2 3\n",
    "--\n",
    "<- 1 3 3 2\n",
    "```\n"
   ],
   "id": "t10_md"
  },
  {
   "cell_type": "code",
   "metadata": {},
   "source": [
    "import sys\n",
    "from pathlib import Path\n",
    "\n",
    "sys.path[:0] = [str(Path.cwd())]\n",
    "from lab02_tests import test_task10\n",
    "\n",
    "\n",
    "def task10():\n",
    "    n = int(input())\n",
    "    a = list(map(int, input().split()))\n",
    "    print(*a)\n",
    "\n",
    "\n",
    "test_task10(task10)\n"
   ],
   "execution_count": null,
   "outputs": [],
   "id": "t10_code"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Сдача\n",
    "\n",
    "Перед отправкой проверьте:\n",
    "\n",
    "- сохранили ноутбук: `File → Save`;\n",
    "- рядом с ноутбуком лежит `lab02_tests.py`;\n",
    "- в ячейке решения есть `from lab02_tests import test_taskN` (после перезапуска ядра выполните эту ячейку снова);\n",
    "- отправили **этот** файл `.ipynb` в задание семинара 2 на [courses.ai.msu.ru](https://courses.ai.msu.ru).\n",
    "\n",
    "Если LMS не открывается, пришлите файл семинаристу в личные сообщения до конца дня.\n",
    "\n",
    "Недорешенные задачи не мешают отправке: сдайте то, что успели. Красный тест у заглушки — нормально. TLE значит «слишком медленно», обычно квадрат там, где нужен линейный проход.\n"
   ],
   "id": "submit"
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python",
   "pygments_lexer": "ipython3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}