{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "d_1",
   "metadata": {},
   "source": [
    "# Словари\n",
    "\n",
    "Осваиваем:\n",
    "- создание словарей `{...}`, `dict()`;\n",
    "- доступ к элементам `d[key]`, безопасный доступ `d.get(key, default)`;\n",
    "- добавление и изменение `d[key] = value`, удаление `del`, `pop`;\n",
    "- проверка вхождения `key in d`;\n",
    "- перебор `d.items()`, `d.keys()`, `d.values()`;\n",
    "- сортировку словаря по ключу и по значению;\n",
    "- вложенные словари;\n",
    "- `collections.Counter` и `collections.defaultdict`.\n",
    "\n",
    "**Важно:** словарь хранит пары «ключ → значение», ключи уникальны и **хешируемы**, порядок вставки сохраняется (Python 3.7+). Если нужен порядок — сортируйте явно."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d_2",
   "metadata": {},
   "source": [
    "## Часть 1. Создание словаря и доступ к элементам"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d_3",
   "metadata": {},
   "source": [
    "**Задача 1. Номер появления слова.**\n",
    "\n",
    "Во входной строке записан текст. **Словом** считается последовательность непробельных символов, слова разделены одним или несколькими пробелами.\n",
    "\n",
    "Для каждого слова определите, сколько раз оно встречалось **до этого** в тексте, и выведите это число.\n",
    "\n",
    "*Пример:* `one two one two three one` → `0 0 1 1 0 2`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d_4",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "d_5",
   "metadata": {},
   "source": [
    "**Задача 2. Словарь синонимов.**\n",
    "\n",
    "Дан словарь, состоящий из пар слов. Каждое слово является синонимом к парному ему слову. Все слова в словаре различны.\n",
    "\n",
    "Для одного слова, введённого пользователем, определите его синоним.\n",
    "\n",
    "**Формат ввода:** сначала $N$ — количество пар, затем $N$ пар слов (по одному слову в строке), потом одно слово для поиска.\n",
    "\n",
    "**Формат вывода:** синоним введённого слова или `Не найдено`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d_6",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "d_8",
   "metadata": {},
   "source": [
    "**Задача 3. Самое частое слово.**\n",
    "\n",
    "Дан текст, состоящий из слов, разделенных пробелами (одним или несколькими). Найдите слово, которое встречается в нём чаще всего. При равенстве частот выберите то, которое идёт раньше по алфавиту.\n",
    "\n",
    "**Подсказка:** Используем `Counter` — это «словарь счётчиков» из стандартной библиотеки. По сути это `dict`, у которого значения — числа (счётчики), плюс удобные методы вроде `most_common`. Создаётся из любого итерируемого объекта: `Counter(['a', 'b', 'a'])` → `Counter({'a': 2, 'b': 1})`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d_9",
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d_10",
   "metadata": {},
   "source": [
    "**Задача 4. Выборы.**\n",
    "\n",
    "В выборах участвуют несколько кандидатов. Дана строка — фамилии кандидатов, разделенные пробелами, за которых проголосовали избиратели. Определите, кто победил, и выведите фамилии всех победителей (если несколько кандидатов набрали одинаковое максимальное число голосов) в алфавитном порядке.\n",
    "\n",
    "**Указание:** Без `Counter`.\n",
    "\n",
    "*Пример:* `Петров Иванов Сидоров Иванов Петров Степанов` → `Иванов` `Петров`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d_11",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "d_12",
   "metadata": {},
   "source": [
    "**Задача 5. Продажи.**\n",
    "\n",
    "Дана база продаж в виде строк «Фамилия_покупателя Товар Количество». Для каждого покупателя посчитайте, сколько **всего единиц товара** он купил.\n",
    "\n",
    "**Формат ввода:** $N$ — количество записей, затем $N$ строк вида `Фамилия_покупателя Товар Количество`.\n",
    "\n",
    "**Формат вывода:** для каждого покупателя в алфавитном порядке выведите `Фамилия_покупателя Количество`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d_13",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "d_14",
   "metadata": {},
   "source": [
    "## Часть 2. Вложенные словари и множества как значения"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d_15",
   "metadata": {},
   "source": [
    "**Задача 6. Страны и города.**\n",
    "\n",
    "Дан список стран и городов каждой страны. Затем даны названия городов. Для каждого города укажите, в какой стране он находится.\n",
    "\n",
    "**Формат ввода:** $N$ — количество стран; далее $N$ строк вида `Страна Город1 Город2 ...`; затем $M$ — количество запросов; далее $M$ строк — названия городов.\n",
    "\n",
    "**Формат вывода:** для каждого запроса — название страны."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d_16",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "d_17",
   "metadata": {},
   "source": [
    "**Задача 7. Права доступа.**\n",
    "\n",
    "Для каждого файла известно, с какими действиями можно к нему обращаться:\n",
    "- `W` — запись, `R` — чтение, `X` — запуск.\n",
    "\n",
    "**Формат ввода:** $N$ — количество файлов; далее $N$ строк вида `имя_файла операции`; затем $M$ — количество запросов; далее $M$ строк вида `операция имя_файла`, где операция — одно из слов `read`, `write`, `execute`.\n",
    "\n",
    "**Формат вывода:** `OK`, если такой файл существует и операция допустима, иначе `Access denied`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d_18",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "d_20",
   "metadata": {},
   "source": [
    "**Задача 8. Инверсия словаря.**\n",
    "\n",
    "Дан словарь. Постройте **обратный словарь**, в котором ключи и значения поменялись местами.\n",
    "\n",
    "**Важно:** значения исходного словаря могут повторяться — в этом случае обратный словарь должен содержать в значении **список** исходных ключей.\n",
    "\n",
    "**Пример:** `{'a': 1, 'b': 2, 'c': 1}` → `{1: ['a', 'c'], 2: ['b']}`.\n",
    "\n",
    "Решите двумя способами: через `defaultdict(list)` и через обычный словарь с `setdefault`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d_21",
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import defaultdict\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d_22",
   "metadata": {},
   "source": [
    "**Задача 9. Слияние словарей с суммированием.**\n",
    "\n",
    "Даны два словаря со строковыми ключами и числовыми значениями. Постройте новый словарь, в котором ключи — объединение ключей обоих словарей, а значения — **сумма** значений по этому ключу в каждом из словарей (если ключ отсутствует в одном из них, берётся значение из другого).\n",
    "\n",
    "**Пример:** `{'a': 1, 'b': 2}` + `{'b': 3, 'c': 4}` → `{'a': 1, 'b': 5, 'c': 4}`.\n",
    "\n",
    "Решите через `d1 | d2` (объединение ключей) и цикл. В конце отсортируйте вывод по ключу."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d_23",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "d_24",
   "metadata": {},
   "source": [
    "**Задача 10. Группировка слов по первой букве.**\n",
    "\n",
    "Дана строка, содержащая слова, разделенные пробелами (одним или несколькими), сформируйте список слов. Постройте словарь, в котором ключ — первая буква слова, а значение — **список** слов, начинающихся с этой буквы (в порядке появления).\n",
    "\n",
    "**Пример:** `'мама мыла раму мышь рама'` → `['мама', 'мыла', 'раму', 'мышь', 'рама']` → `{'м': ['мама', 'мыла', 'мышь'], 'р': ['раму', 'рама']}`.\n",
    "\n",
    "Выведите ключи в алфавитном порядке, а для каждого ключа — его слова."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d_25",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "d_27",
   "metadata": {},
   "source": [
    "**Задача 11. Родословная: подсчёт уровней.**\n",
    "\n",
    "В генеалогическом древе у каждого человека, кроме родоначальника, есть ровно один родитель. Каждому элементу дерева сопоставляется целое неотрицательное число — **высота**. У родоначальника высота равна 0, у любого другого элемента — на 1 больше, чем у его родителя.\n",
    "\n",
    "**Формат ввода:** $N$ — число элементов; далее $N-1$ строка вида `имя_потомка имя_родителя`.\n",
    "\n",
    "**Формат вывода:** для каждого элемента в лексикографическом порядке выведите `имя высота`.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ced6b432-899c-41a6-8d87-b1ea518256c3",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.9.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}