{
  "cells": [
    {
      "cell_type": "markdown",
      "id": "intro",
      "metadata": {},
      "source": [
        "# Домашнее задание 3\n",
        "\n",
        "После семинара 3 решите пять задач. Сдаёте **этот** файл семинаристу.\n",
        "\n",
        "На больших тестах квадратный перебор не успеет: тестер даёт **TLE** (лимит 2 секунды на тест), не только «не тот ответ».\n",
        "\n",
        "Можно смотреть свой ноутбук семинара 3. Готовое решение копировать не стоит: тесты это не заменят, а на зачёте рядом никого не будет.\n",
        "\n",
        "ДЗ к лекции 3 (текст в LaTeX) — отдельно, лектору: это задание не заменяет.\n"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "jupyter",
      "metadata": {},
      "source": [
        "## Как устроен ноутбук\n",
        "\n",
        "Как на семинаре: ячейки **Markdown** и **Code**; командный режим — `Esc`, правка — `Enter`; `Shift+Enter` выполняет ячейку.\n",
        "\n",
        "Положите этот файл `.ipynb` и файл `lab03_hw_tests.py` **в одну папку**. Без файла тестов проверка не запустится. Откройте ноутбук из этой папки.\n"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "how_tests",
      "metadata": {},
      "source": [
        "## Ввод, вывод и тесты\n",
        "\n",
        "Решение — **функция без аргументов**: внутри `input` и `print`, как в контесте. Тест подставляет входы сам. **Не заполняйте поле ввода Jupyter.**\n",
        "\n",
        "В каждой задаче стоит заглушка: она что-то читает и печатает неверный ответ. Сначала запустите ячейку: увидите «не OK» или TLE, вход, «ожидалось» и «получено». Потом замените тело функции.\n",
        "\n",
        "Импорт тестов стоит **в каждой** ячейке с решением. Если перезапустите ядро, достаточно снова выполнить эту ячейку — отдельно «подключать библиотеку в начале» не обязательно, хотя общая ячейка ниже тоже есть.\n"
      ]
    },
    {
      "cell_type": "code",
      "id": "import_tests",
      "metadata": {},
      "execution_count": null,
      "outputs": [],
      "source": [
        "import sys\n",
        "from pathlib import Path\n",
        "\n",
        "sys.path[:0] = [str(Path.cwd())]\n",
        "\n",
        "from lab03_hw_tests import (\n",
        "    test_task1,\n",
        "    test_task2,\n",
        "    test_task3,\n",
        "    test_task4,\n",
        "    test_task5,\n",
        ")\n",
        "\n",
        "print('Тесты подключены')\n"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "t1_md",
      "metadata": {},
      "source": [
        "### Задача 1. Нарушения неубывания\n",
        "\n",
        "Дан массив из $n$ целых чисел. Сколько есть индексов $i$ ($1 \\le i < n$), для которых $a_i > a_{i+1}$?\n",
        "\n",
        "**Вход.** Первая строка: целое $n$ ($1 \\le n \\le 2\\cdot 10^5$). Вторая строка: $n$ целых чисел $a_i$ ($|a_i| \\le 10^9$).\n",
        "\n",
        "**Выход.** Одно целое число.\n",
        "\n",
        "```\n",
        "-> 5\n",
        "-> 1 2 2 4 9\n",
        "--\n",
        "<- 0\n",
        "```\n",
        "\n",
        "```\n",
        "-> 3\n",
        "-> 7 7 7\n",
        "--\n",
        "<- 0\n",
        "```\n",
        "\n",
        "```\n",
        "-> 5\n",
        "-> 5 4 3 2 1\n",
        "--\n",
        "<- 4\n",
        "```\n",
        "\n",
        "```\n",
        "-> 4\n",
        "-> 1 3 2 4\n",
        "--\n",
        "<- 1\n",
        "```\n",
        "\n",
        "```\n",
        "-> 1\n",
        "-> 0\n",
        "--\n",
        "<- 0\n",
        "```\n"
      ]
    },
    {
      "cell_type": "code",
      "id": "t1_code",
      "metadata": {},
      "execution_count": null,
      "outputs": [],
      "source": [
        "import sys\n",
        "from pathlib import Path\n",
        "\n",
        "sys.path[:0] = [str(Path.cwd())]\n",
        "from lab03_hw_tests import test_task1\n",
        "\n",
        "\n",
        "def task1():\n",
        "    n = int(input())\n",
        "    a = list(map(int, input().split()))\n",
        "    print(-1)\n",
        "\n",
        "\n",
        "test_task1(task1)\n"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "t2_md",
      "metadata": {},
      "source": [
        "### Задача 2. Порядок по модулю\n",
        "\n",
        "Дан массив из $n$ целых чисел. Выведите его элементы в таком порядке: по неубыванию $|a_i|$; если модули равны — по неубыванию самих чисел $a_i$.\n",
        "\n",
        "**Вход.** Первая строка: целое $n$ ($1 \\le n \\le 10^5$). Вторая строка: $n$ целых чисел $a_i$ ($|a_i| \\le 10^9$).\n",
        "\n",
        "**Выход.** $n$ целых чисел через пробел.\n",
        "\n",
        "```\n",
        "-> 5\n",
        "-> 5 -2 2 -5 0\n",
        "--\n",
        "<- 0 -2 2 -5 5\n",
        "```\n",
        "\n",
        "```\n",
        "-> 2\n",
        "-> -3 3\n",
        "--\n",
        "<- -3 3\n",
        "```\n",
        "\n",
        "```\n",
        "-> 3\n",
        "-> 0 0 0\n",
        "--\n",
        "<- 0 0 0\n",
        "```\n",
        "\n",
        "```\n",
        "-> 1\n",
        "-> 7\n",
        "--\n",
        "<- 7\n",
        "```\n"
      ]
    },
    {
      "cell_type": "code",
      "id": "t2_code",
      "metadata": {},
      "execution_count": null,
      "outputs": [],
      "source": [
        "import sys\n",
        "from pathlib import Path\n",
        "\n",
        "sys.path[:0] = [str(Path.cwd())]\n",
        "from lab03_hw_tests import test_task2\n",
        "\n",
        "\n",
        "def task2():\n",
        "    n = int(input())\n",
        "    a = list(map(int, input().split()))\n",
        "    print(0)\n",
        "\n",
        "\n",
        "test_task2(task2)\n"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "t3_md",
      "metadata": {},
      "source": [
        "### Задача 3. По последней цифре\n",
        "\n",
        "Дан массив из $n$ целых неотрицательных чисел. Упорядочьте его по неубыванию **последней десятичной цифры** каждого числа (то есть $a_i \\bmod 10$). Если последние цифры равны, относительный порядок этих элементов должен остаться таким же, как во входе.\n",
        "\n",
        "**Вход.** Первая строка: целое $n$ ($1 \\le n \\le 10^5$). Вторая строка: $n$ целых чисел $a_i$ ($0 \\le a_i \\le 10^9$).\n",
        "\n",
        "**Выход.** $n$ целых чисел через пробел.\n",
        "\n",
        "```\n",
        "-> 3\n",
        "-> 12 23 34\n",
        "--\n",
        "<- 12 23 34\n",
        "```\n",
        "\n",
        "```\n",
        "-> 3\n",
        "-> 25 5 15\n",
        "--\n",
        "<- 25 5 15\n",
        "```\n",
        "\n",
        "```\n",
        "-> 3\n",
        "-> 10 20 30\n",
        "--\n",
        "<- 10 20 30\n",
        "```\n",
        "\n",
        "```\n",
        "-> 1\n",
        "-> 0\n",
        "--\n",
        "<- 0\n",
        "```\n"
      ]
    },
    {
      "cell_type": "code",
      "id": "t3_code",
      "metadata": {},
      "execution_count": null,
      "outputs": [],
      "source": [
        "import sys\n",
        "from pathlib import Path\n",
        "\n",
        "sys.path[:0] = [str(Path.cwd())]\n",
        "from lab03_hw_tests import test_task3\n",
        "\n",
        "\n",
        "def task3():\n",
        "    n = int(input())\n",
        "    a = list(map(int, input().split()))\n",
        "    print(0)\n",
        "\n",
        "\n",
        "test_task3(task3)\n"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "t4_md",
      "metadata": {},
      "source": [
        "### Задача 4. $k$-й по неубыванию\n",
        "\n",
        "Дан массив из $n$ целых чисел из диапазона от $0$ до $1000$ включительно и число $k$. Если выписать элементы массива в неубывающем порядке, какое число стоит на месте $k$? Нумерация с единицы: при $k = 1$ это минимум массива.\n",
        "\n",
        "**Вход.** Первая строка: $n$ и $k$ ($1 \\le k \\le n \\le 2\\cdot 10^5$). Вторая строка: $n$ целых чисел $a_i$ ($0 \\le a_i \\le 1000$).\n",
        "\n",
        "**Выход.** Одно целое число.\n",
        "\n",
        "```\n",
        "-> 6 4\n",
        "-> 3 1 3 2 1 3\n",
        "--\n",
        "<- 3\n",
        "```\n",
        "\n",
        "```\n",
        "-> 5 1\n",
        "-> 7 7 7 7 7\n",
        "--\n",
        "<- 7\n",
        "```\n",
        "\n",
        "```\n",
        "-> 4 3\n",
        "-> 0 1000 0 5\n",
        "--\n",
        "<- 5\n",
        "```\n",
        "\n",
        "```\n",
        "-> 5 5\n",
        "-> 4 1 4 2 4\n",
        "--\n",
        "<- 4\n",
        "```\n"
      ]
    },
    {
      "cell_type": "code",
      "id": "t4_code",
      "metadata": {},
      "execution_count": null,
      "outputs": [],
      "source": [
        "import sys\n",
        "from pathlib import Path\n",
        "\n",
        "sys.path[:0] = [str(Path.cwd())]\n",
        "from lab03_hw_tests import test_task4\n",
        "\n",
        "\n",
        "def task4():\n",
        "    n, k = map(int, input().split())\n",
        "    a = list(map(int, input().split()))\n",
        "    print(0)\n",
        "\n",
        "\n",
        "test_task4(task4)\n"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "t5_md",
      "metadata": {},
      "source": [
        "### Задача 5. Точки\n",
        "\n",
        "Даны $n$ точек на плоскости с целыми координатами. Выведите их в таком порядке: по неубыванию $x$; при равных $x$ — по неубыванию $y$.\n",
        "\n",
        "Если у двух точек совпадают и $x$, и $y$, их взаимный порядок в ответе может быть любым.\n",
        "\n",
        "**Вход.** Первая строка: целое $n$ ($1 \\le n \\le 10^5$). Далее $n$ строк: в каждой два целых $x$ и $y$ ($|x|, |y| \\le 10^9$).\n",
        "\n",
        "**Выход.** $n$ строк `x y`.\n",
        "\n",
        "```\n",
        "-> 3\n",
        "-> 3 1\n",
        "-> 1 2\n",
        "-> 2 0\n",
        "--\n",
        "<- 1 2\n",
        "<- 2 0\n",
        "<- 3 1\n",
        "```\n",
        "\n",
        "```\n",
        "-> 2\n",
        "-> 1 5\n",
        "-> 1 2\n",
        "--\n",
        "<- 1 2\n",
        "<- 1 5\n",
        "```\n",
        "\n",
        "```\n",
        "-> 3\n",
        "-> 2 3\n",
        "-> 2 1\n",
        "-> 1 9\n",
        "--\n",
        "<- 1 9\n",
        "<- 2 1\n",
        "<- 2 3\n",
        "```\n",
        "\n",
        "```\n",
        "-> 1\n",
        "-> 0 0\n",
        "--\n",
        "<- 0 0\n",
        "```\n"
      ]
    },
    {
      "cell_type": "code",
      "id": "t5_code",
      "metadata": {},
      "execution_count": null,
      "outputs": [],
      "source": [
        "import sys\n",
        "from pathlib import Path\n",
        "\n",
        "sys.path[:0] = [str(Path.cwd())]\n",
        "from lab03_hw_tests import test_task5\n",
        "\n",
        "\n",
        "def task5():\n",
        "    n = int(input())\n",
        "    for _ in range(n):\n",
        "        input()\n",
        "        print(0, 0)\n",
        "\n",
        "\n",
        "test_task5(task5)\n"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "submit",
      "metadata": {},
      "source": [
        "## Сдача\n",
        "\n",
        "Перед отправкой проверьте:\n",
        "\n",
        "- сохранили ноутбук: `File → Save`;\n",
        "- рядом с ноутбуком лежит `lab03_hw_tests.py`;\n",
        "- в ячейке решения есть `from lab03_hw_tests import test_taskN` (после перезапуска ядра выполните эту ячейку снова).\n",
        "\n",
        "Пришлите **этот** файл `.ipynb` семинаристу в личные сообщения до дедлайна.\n",
        "\n",
        "Недорешенные задачи не мешают отправке: сдайте то, что успели. Красный тест у заглушки — нормально. TLE значит «слишком медленно», обычно квадрат там, где нужен линейный проход.\n",
        "\n",
        "ДЗ к лекции (LaTeX) сдаёте лектору, не в этот файл.\n"
      ]
    }
  ],
  "metadata": {
    "kernelspec": {
      "display_name": "Python 3",
      "language": "python",
      "name": "python3"
    },
    "language_info": {
      "name": "python",
      "pygments_lexer": "ipython3"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 5
}