Ближайший ноль.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ограничение времени\t1 секунда  \n",
    "Ограничение памяти\t64Mb  \n",
    "\n",
    "Ввод\tстандартный ввод или input.txt  \n",
    "Вывод\tстандартный вывод или output.txt  \n",
    "\n",
    "Тимофей ищет место, чтобы построить себе дом. Улица, на которой он хочет жить, имеет длину n, то есть состоит из n одинаковых идущих подряд участков. Каждый участок либо пустой, либо на нём уже построен дом.\n",
    "\n",
    "Общительный Тимофей не хочет жить далеко от других людей на этой улице. Поэтому ему важно для каждого участка знать расстояние до ближайшего пустого участка. Если участок пустой, эта величина будет равна нулю — расстояние до самого себя.\n",
    "\n",
    "Помогите Тимофею посчитать искомые расстояния. Для этого у вас есть карта улицы. Дома в городе Тимофея нумеровались в том порядке, в котором строились, поэтому их номера на карте никак не упорядочены. Пустые участки обозначены нулями.\n",
    "\n",
    "Формат ввода\n",
    "В первой строке дана длина улицы —– n (1 ≤ n ≤ 10**6). В следующей строке записаны n целых неотрицательных чисел — номера домов и обозначения пустых участков на карте (нули). Гарантируется, что в последовательности есть хотя бы один ноль. Номера домов (положительные числа) уникальны и не превосходят 109.\n",
    "\n",
    "Формат вывода\n",
    "Для каждого из участков выведите расстояние до ближайшего нуля. Числа выводите в одну строку, разделяя их пробелами."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import Tuple, List\n",
    "\n",
    "\n",
    "def read_input() -> Tuple[int, List[str]]:\n",
    "    \"\"\"Считывает ввод в переменные.\"\"\"\n",
    "    PLOT_COUNT = int(input())\n",
    "    plots = input().split()\n",
    "    return PLOT_COUNT, plots\n",
    "\n",
    "\n",
    "def zero_distance(arr: List[str], PLOT_COUNT: int) -> List[int]:\n",
    "    \"\"\"Высчитывает дистанцию до ближайшего нулевого участка.\"\"\"\n",
    "    zero_pointer = PLOT_COUNT\n",
    "    answer = []\n",
    "    for i in range(PLOT_COUNT):\n",
    "        if arr[i] == '0':\n",
    "            answer.append(0)\n",
    "            zero_pointer = 1\n",
    "        else:\n",
    "            answer.append(zero_pointer)\n",
    "            zero_pointer += 1\n",
    "\n",
    "    zero_pointer = PLOT_COUNT\n",
    "    miss_elements = 0\n",
    "\n",
    "    for i in range(PLOT_COUNT-1, -1, -1):\n",
    "        if miss_elements:\n",
    "            miss_elements -= 1\n",
    "            continue\n",
    "        if answer[i] == 0:\n",
    "            zero_pointer = 1\n",
    "        else:\n",
    "            if zero_pointer == answer[i]:\n",
    "                miss_elements = zero_pointer - 1\n",
    "                continue\n",
    "            answer[i] = min(zero_pointer, answer[i])\n",
    "            zero_pointer += 1\n",
    "\n",
    "    return answer\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    PLOT_COUNT, plots = read_input()\n",
    "    answer = zero_distance(plots, PLOT_COUNT)\n",
    "    print(*answer)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.6"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "916dbcbb3f70747c44a77c7bcd40155683ae19c65e1c03b4aa3499c5328201f1"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}