{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "m_1",
   "metadata": {},
   "source": [
    "# Множества\n",
    "\n",
    "Осваиваем:\n",
    "- создание множеств `{...}`, `set()`, `frozenset()`;\n",
    "- добавление и удаление: `add`, `remove`, `discard`, `pop`;\n",
    "- проверку вхождения `in`;\n",
    "- операции над множествами: `|` (объединение), `&` (пересечение), `-` (разность), `^` (симметрическая разность);\n",
    "- методы `union`, `intersection`, `difference`, `symmetric_difference`;\n",
    "- проверки `issubset`, `issuperset`, `isdisjoint`;\n",
    "- длину `len`.\n",
    "\n",
    "**Важно:** множество хранит только **уникальные** элементы и **не сохраняет порядок**. Если нужен отсортированный вывод — используйте `sorted(set)`."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "m_2",
   "metadata": {},
   "source": [
    "## Часть 1. Создание множеств и базовые операции"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "m_5",
   "metadata": {},
   "source": [
    "**Задача 1. Встречалось ли число раньше.**\n",
    "\n",
    "Во входной строке записана последовательность целых чисел через пробел. Для каждого числа выведите `YES` (в отдельной строке), если это число ранее уже встречалось в последовательности, или `NO`, если не встречалось."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "m_6",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "m_7",
   "metadata": {},
   "source": [
    "**Задача 2. Уникальные слова.**\n",
    "\n",
    "Дана строка, состоящая из слов, разделенных пробелами (одним или несколькими). Выведите все **уникальные** слова (без повторений) в том порядке, в котором они впервые появляются в строке. Используйте множество для проверки, встречалось ли слово."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "m_8",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "m_10",
   "metadata": {},
   "source": [
    "**Задача 3. Пересечение множеств.**\n",
    "\n",
    "Даны два списка целых чисел. Выведите все числа, которые входят **и в первый, и во второй** список, в порядке возрастания. Решите двумя способами: через оператор `&` и через метод `intersection`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "m_11",
   "metadata": {},
   "outputs": [],
   "source": [
    "from random import randint\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "m_12",
   "metadata": {},
   "source": [
    "**Задача 4. Симметрическая разность.**\n",
    "\n",
    "Даны два множества целых чисел. Выведите в порядке возрастания все элементы, которые входят **ровно в одно** из них (то есть есть в первом, но нет во втором, или есть во втором, но нет в первом). Решите через `^` и через `symmetric_difference`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "m_13",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "m_14",
   "metadata": {},
   "source": [
    "**Задача 5. Проверка подмножества.**\n",
    "\n",
    "Даны два множества целых чисел `A` и `B`. Проверьте:\n",
    "1. является ли `A` подмножеством `B` (каждый элемент `A` есть в `B`, `A` $\\subseteq$ `B`);\n",
    "2. является ли `B` надмножеством `A` (`B` $\\supseteq$ `A`);\n",
    "3. есть ли у множеств общие элементы (обратное к `isdisjoint` — возвращает `True`, если у множеств нет общих элементов).\n",
    "\n",
    "Используйте `issubset`, `issuperset`, `isdisjoint`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "m_15",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "m_16",
   "metadata": {},
   "source": [
    "## Часть 2. Классические задачи"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "m_17",
   "metadata": {},
   "source": [
    "**Задача 6. Кубики.**\n",
    "\n",
    "Аня и Боря любят играть в разноцветные кубики, причём у каждого из них свой набор, и в каждом наборе все кубики различны по цвету. Дети занумеровали все цвета случайными числами от 0 до $10^8$.\n",
    "\n",
    "В первой строке входных данных записаны числа $N$ и $M$ — число кубиков у Ани и Бори. В следующих $N$ строках заданы номера цветов кубиков Ани, в последних $M$ строках — номера цветов Бори.\n",
    "\n",
    "Найдите три множества: номера цветов кубиков, которые есть в обоих наборах; номера цветов кубиков, которые есть только у Ани, и номера цветов кубиков, которые есть только у Бори. Для каждого из множеств выведите сначала количество элементов в нём, а затем сами элементы, отсортированные по возрастанию."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "m_18",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "m_19",
   "metadata": {},
   "source": [
    "**Задача 7. Угадай число.**\n",
    "\n",
    "Август и Беатриса играют в игру. Август загадал натуральное число от 1 до $n$. Беатриса пытается угадать это число, для этого она называет некоторые множества натуральных чисел. Август отвечает Беатрисе `YES`, если среди названных ей чисел есть задуманное, или `NO` в противном случае.\n",
    "\n",
    "После нескольких заданных вопросов Беатриса запуталась и просит помочь ей определить, какие числа мог задумать Август.\n",
    "\n",
    "**Формат ввода:** сначала $n$ — максимальное число. Далее каждая пара строк содержит вопрос Беатрисы (числа через пробел) и ответ Августа (`YES` или `NO`). Ввод завершается строкой `HELP`.\n",
    "\n",
    "**Формат вывода:** все числа, которые мог загадать Август, в порядке возрастания через пробел."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "m_20",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "m_21",
   "metadata": {},
   "source": [
    "**Задача 8. Полиглоты.**\n",
    "\n",
    "Каждый из $N$ школьников некоторой школы знает $M_i$ языков. Определите, какие языки знают **все** школьники, и какие языки знает **хотя бы один** из школьников.\n",
    "\n",
    "**Формат ввода:** $N$, затем $N$ блоков: в каждом сначала $M_i$ — количество языков $i$-го школьника, а затем $M_i$ строк с названиями языков.\n",
    "\n",
    "**Формат вывода:** сначала количество языков, которые знают все школьники, затем сами языки (по одному в строке). Потом количество языков, которые знает хотя бы один, и сами языки."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "m_22",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "m_23",
   "metadata": {},
   "source": [
    "## Часть 3. Прикладные задачи"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "m_24",
   "metadata": {},
   "source": [
    "**Задача 9. Общие буквы двух слов.**\n",
    "\n",
    "Даны два слова (каждое состоит **только** из русских строчных букв). Выведите в **алфавитном порядке** все буквы, которые есть **и в первом, и во втором** слове, без повторений. Если общих букв нет — выведите пустую строку (или сообщение)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "m_25",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "m_26",
   "metadata": {},
   "source": [
    "**Задача 10. Общие цифры двух чисел.**\n",
    "\n",
    "Даны две **строки**, представляющие собой натуральные числа. Выведите в порядке возрастания все цифры, которые встречаются в записи **обоих** чисел. Например, для `12345` и `3547` — `3 4 5`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "m_27",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "m_28",
   "metadata": {},
   "source": [
    "**Задача 11. Решето Эратосфена через множество.**\n",
    "\n",
    "Дано целое $n \\geqslant 0$. Найдите все простые числа от 2 до $n$, используя **множество**.\n",
    "\n",
    "**Указание**: заведите множество всех чисел от 2 до $n$. Затем для каждого простого $i$ удаляйте из множества все его кратные, начиная с $i \\cdot i$. В конце множество содержит только простые числа."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "m_29",
   "metadata": {},
   "outputs": [],
   "source": [
    "from math import isqrt\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "m_30",
   "metadata": {},
   "source": [
    "## Часть 4. frozenset — неизменяемое множество\n",
    "\n",
    "Обычное множество `set` **изменяемо**: в него можно добавлять и удалять элементы. Из-за этого оно **не хешируется** — его нельзя положить внутрь другого `set` или использовать как ключ словаря:\n",
    "\n",
    "```python\n",
    "{ {1, 2}, {3, 4} }   # TypeError: unhashable type: 'set'\n",
    "```\n",
    "\n",
    "`frozenset` — это «замороженное» множество: после создания его нельзя изменить, поэтому оно **хешируемо** и его можно класть внутрь множеств и словарей. Все операции над множествами (`|`, `&`, `-`, `^`) работают и с `frozenset` — результатом будет новый `frozenset`."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "m_31",
   "metadata": {},
   "source": [
    "**Задача 12. Уникальные наборы.**\n",
    "\n",
    "Дан список списков целых чисел. Каждый внутренний список описывает **набор** — порядок элементов в нём не важен, и повторы тоже не важны. Нужно найти все **уникальные наборы** и вывести их количество и сами наборы.\n",
    "\n",
    "**Почему нужен именно `frozenset`:** чтобы собрать уникальные наборы в `set`, каждый набор должен быть хешируемым. Обычный `set` — нет, а `frozenset` — да. Поэтому используйте `{frozenset(inner) for inner in data}`.\n",
    "\n",
    "**Проверка:** для `[[1,2,3],[3,2,1],[1,2],[2,1,3],[4,5],[5,4]]` должно получиться **3** уникальных набора: `{1,2,3}`, `{1,2}`, `{4,5}`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "m_32",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "m_33",
   "metadata": {},
   "source": [
    "**Замечание.** `frozenset` поддерживает те же операции, что и `set`, кроме изменяющих:\n",
    "\n",
    "- `fs | other`, `fs & other`, `fs - other`, `fs ^ other` — работают;\n",
    "- `fs.union(...)`, `fs.intersection(...)` и т.д. — работают;\n",
    "- `fs.add(...)`, `fs.remove(...)`, `fs.discard(...)`, `fs.pop()`, `fs.clear()` — **не работают** (их нет у `frozenset`).\n",
    "\n",
    "Если бы в задаче 12 использовался обычный `set`, компилятор выдал бы `TypeError` ещё на этапе создания внешнего множества."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python [conda env:base] *",
   "language": "python",
   "name": "conda-base-py"
  },
  "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.13.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}