{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "# Домашнее задание 2\n",
        "\n",
        "После семинара 2 решите пять задач. Сдаёте **этот** файл семинаристу.\n",
        "\n",
        "На больших тестах квадратный перебор не успеет: тестер даёт **TLE** (лимит 2 секунды на тест), не только «не тот ответ».\n",
        "\n",
        "Можно смотреть свой ноутбук семинара 2. Готовое решение копировать не стоит: тесты это не заменят, а на зачёте рядом никого не будет.\n",
        ""
      ],
      "id": "intro"
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Как устроен ноутбук\n",
        "\n",
        "Как на семинаре: ячейки **Markdown** и **Code**; командный режим — `Esc`, правка — `Enter`; `Shift+Enter` выполняет ячейку.\n",
        "\n",
        "Положите этот файл `.ipynb` и файл `lab02_hw_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_hw_tests import (\n",
        "    test_task1,\n",
        "    test_task2,\n",
        "    test_task3,\n",
        "    test_task4,\n",
        "    test_task5,\n",
        ")\n",
        "\n",
        "print('Тесты подключены')\n"
      ],
      "execution_count": null,
      "outputs": [],
      "id": "import_tests"
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Задача 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",
        "<- 1 2 3\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",
        "<- 0 5 1000\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_hw_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": [
        "### Задача 2. Пара с ближайшей суммой\n",
        "\n",
        "Дан массив из $n$ целых чисел, упорядоченный по неубыванию, и число $S$. Среди всех пар элементов с разными индексами найдите пару, сумма которой отличается от $S$ меньше всего, и выведите эту сумму.\n",
        "\n",
        "Если ближайших пар несколько и суммы у них разные, подойдёт сумма любой из них. Индексы выводить не нужно: проверяющему достаточно, чтобы выведенное число было суммой какой-нибудь пары и стояло так же близко к $S$, как лучшая пара.\n",
        "\n",
        "Расстоянием до $S$ считается $|a_i + a_j - S|$.\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",
        "**Выход.** Одно целое — сумма пары, ближайшей к $S$.\n",
        "\n",
        "```\n",
        "-> 4 9\n",
        "-> 2 7 11 15\n",
        "--\n",
        "<- 9\n",
        "```\n",
        "\n",
        "```\n",
        "-> 4 18\n",
        "-> 2 7 11 15\n",
        "--\n",
        "<- 18\n",
        "```\n",
        "\n",
        "```\n",
        "-> 7 10\n",
        "-> 1 4 4 6 8 9 20\n",
        "--\n",
        "<- 10\n",
        "```\n",
        "\n",
        "```\n",
        "-> 4 0\n",
        "-> -10 0 0 10\n",
        "--\n",
        "<- 0\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_hw_tests import test_task2\n",
        "\n",
        "\n",
        "def task2():\n",
        "    n, s = map(int, input().split())\n",
        "    a = 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": [
        "### Задача 3. Максимальная сумма отрезка длины $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",
        "**Выход.** Одно целое — максимальная сумма отрезка длины $k$.\n",
        "\n",
        "```\n",
        "-> 5 3\n",
        "-> 1 2 3 4 5\n",
        "--\n",
        "<- 12\n",
        "```\n",
        "\n",
        "```\n",
        "-> 4 4\n",
        "-> 2 -1 2 -1\n",
        "--\n",
        "<- 2\n",
        "```\n",
        "\n",
        "```\n",
        "-> 3 1\n",
        "-> -7 -2 -5\n",
        "--\n",
        "<- -2\n",
        "```\n",
        "\n",
        "```\n",
        "-> 6 2\n",
        "-> 7 0 7 0 7 0\n",
        "--\n",
        "<- 7\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_hw_tests import test_task3\n",
        "\n",
        "\n",
        "def task3():\n",
        "    n, k = map(int, input().split())\n",
        "    a = list(map(int, input().split()))\n",
        "    print(0)\n",
        "\n",
        "\n",
        "test_task3(task3)\n"
      ],
      "execution_count": null,
      "outputs": [],
      "id": "t3_code"
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Задача 4. Смена знаков\n",
        "\n",
        "Дан массив из $n$ целых чисел. Переставьте его элементы так, чтобы сначала шли все отрицательные числа, а затем все неотрицательные. Внутри каждой из двух групп порядок чисел должен остаться прежним: отрицательные идут в том же порядке, в каком они стояли в исходном массиве, а неотрицательные — в своём.\n",
        "\n",
        "Например, массив `5 0 -7 2 -1` превращается в `-7 -1 5 2 0`: отрицательные были в порядке $-7, -1$, неотрицательные — в порядке $5, 0, 2$.\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",
        "-> 4\n",
        "-> 3 -1 0 -4\n",
        "--\n",
        "<- -1 -4 3 0\n",
        "```\n",
        "\n",
        "```\n",
        "-> 3\n",
        "-> 1 2 3\n",
        "--\n",
        "<- 1 2 3\n",
        "```\n",
        "\n",
        "```\n",
        "-> 3\n",
        "-> -1 -2 -3\n",
        "--\n",
        "<- -1 -2 -3\n",
        "```\n",
        "\n",
        "```\n",
        "-> 5\n",
        "-> 5 0 -7 2 -1\n",
        "--\n",
        "<- -7 -1 5 2 0\n",
        "```\n",
        "\n",
        "```\n",
        "-> 2\n",
        "-> 0 -5\n",
        "--\n",
        "<- -5 0\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_hw_tests import test_task4\n",
        "\n",
        "\n",
        "def task4():\n",
        "    n = int(input())\n",
        "    a = list(map(int, input().split()))\n",
        "    print(*a)\n",
        "\n",
        "\n",
        "test_task4(task4)\n"
      ],
      "execution_count": null,
      "outputs": [],
      "id": "t4_code"
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Задача 5. Максимальная сумма пары на расстоянии\n",
        "\n",
        "Дана последовательность из $n$ целых чисел и число $K$. Рассматриваются пары элементов с разными индексами, у которых номера отличаются не менее чем на $K$ (порядок элементов в паре не важен, стоять рядом они не обязаны). Найдите наибольшую сумму такой пары.\n",
        "\n",
        "Нумерация элементов с единицы: у соседних элементов номера отличаются на $1$. При $K = 1$ подходит любая пара с разными индексами. Пара существует всегда, потому что $K < n$.\n",
        "\n",
        "Числа могут быть и отрицательными; ответ на единицу меньше нуля — это нормально.\n",
        "\n",
        "**Вход.** Первая строка: $n$ и $K$ ($2 \\le n \\le 2\\cdot 10^5$, $1 \\le K < n$). Вторая: $n$ чисел, $|a_i| \\le 10^9$.\n",
        "\n",
        "**Выход.** Одно целое — максимальная сумма подходящей пары.\n",
        "\n",
        "```\n",
        "-> 5 2\n",
        "-> 5 2 -1 0 3\n",
        "--\n",
        "<- 5\n",
        "```\n",
        "\n",
        "```\n",
        "-> 6 3\n",
        "-> 1 100 -50 2 3 -7\n",
        "--\n",
        "<- 103\n",
        "```\n",
        "\n",
        "```\n",
        "-> 4 2\n",
        "-> 3 -5 4 10\n",
        "--\n",
        "<- 13\n",
        "```\n",
        "\n",
        "```\n",
        "-> 4 1\n",
        "-> -1 -2 -3 -4\n",
        "--\n",
        "<- -3\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_hw_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",
        "- сохранили ноутбук: `File → Save`;\n",
        "- рядом с ноутбуком лежит `lab02_hw_tests.py`;\n",
        "- в ячейке решения есть `from lab02_hw_tests import test_taskN` (после перезапуска ядра выполните эту ячейку снова).\n",
        "\n",
        "Пришлите **этот** файл `.ipynb` семинаристу в личные сообщения до дедлайна.\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
}