Множества

Множество в языке Питон — это структура данных, эквивалентная множствам в математике. Множество может состоять из различных элементов, порядок элементов в множестве неопределен. В множество можно добавлять и удалять элементы, можно перебирать элементы множества, можно выполнять операции над множествами (объединение, пересечение, разность). Можно проверять принадлежность элементу множества.

В отличии от массивов, где элементы хранятся в виде последовательного списка, в множествах порядок хранения элементов неопределен (более того, элементы множества храняться не подряд, как в списке, а при помощи хитрых алгоритмов). Это позволяет выполнять операции типа “проверить принадлежность элемента множеству” быстрее, чем просто перебирая все элементы множества.

Задание множеств

Множество задается перечислением всех его элементов в фигурных скобках. Например:

A = {1, 2, 3}

Исключением явлеется пустое множество, которое можно создать при помощи функции set(). Если функции set передать в качестве параметра список, строку или кортеж, то она вернет множество, составленное из элементов списка, строки, кортежа. Например:

A = set('qwerty')
print(A)

выведет {'e', 'q', 'r', 't', 'w', 'y'}.

Каждый элемент может входить в множество только один раз, порядок задания элементов не важен. Например, программа:

A = {1, 2, 3}
B = {3, 2, 3, 1}
print(A == B)

выведет True, так как A и B — равные множества.

Каждый элемент может входить в множество только один раз. set('Hello') вернет множество из четырех элементов: {'H', 'e', 'l', 'o'}.

Работа с элементами множеств

Узнать число элементов в множестве можно при помощи функции len.

Перебрать все элементы множества (в неопределенном порядке!) можно при помощи цикла for:

C = {1, 2, 3, 4, 5}
for elem in C:
    print(elem)

Проверить, принадлежит ли элемент множеству можно при помощи операции in, возвращающей значение типа bool:

i in A

Аналогично есть противоположная операция not in.

Для добавления элемента в множество есть метод add:

A.add(x)

Для удаления элемента x из множества есть два метода: discard и remove. Их поведение различается только в случае, когда удаляемый элемент отсутствует в множестве. В этом случае метод discard не делает ничего, а метод remove генерирует исключение KeyError.

Наконец, метод pop удаляет из множества один случайный элемент и возвращает его значение. Если же множество пусто, то генерируется исключение KeyError.

Из множества можно сделать список при помощи функции list.

Операции с множествами

С множествами в питоне можно выполнять обычные для математики операции над множествами.

A \| B A.union(B)	Возвращает множество, являющееся объединением множеств `A` и `B`.
A \|= B A.update(B)	Добавляет в множество `A` все элементы из множества `B`.
A & B A.intersection(B)	Возвращает множество, являющееся пересечением множеств `A` и `B`.
A &= B A.intersection_update(B)	Оставляет в множестве `A` только те элементы, которые есть в множестве `B`.
A - B A.difference(B)	Возвращает разность множеств `A` и `B` (элементы, входящие в `A`, но не входящие в `B`).
A -= B A.difference_update(B)	Удаляет из множества `A` все элементы, входящие в `B`.
A ^ B A.symmetric_difference(B)	Возвращает симметрическую разность множеств `A` и `B` (элементы, входящие в `A` или в `B`, но не в оба из них одновременно).
A ^= B A.symmetric_difference_update(B)	Записывает в `A` симметрическую разность множеств `A` и `B`.
A <= B A.issubset(B)	Возвращает `true, если A является подмножеством B.`
A >= B A.issuperset(B)	Возвращает `true, если B является подмножеством A.`
A < B	Эквивалентно `A <= B and A != B`
A > B	Эквивалентно `A >= B and A != B`

Упражнения

Во всех упражнениях этого листка ввод-вывод может быть как стандартным, так и файловым (input.txt/output.txt).

A: Количество различных чисел

Дан список чисел, который могут содержать до 100000 чисел каждый. Определите, сколько в нем встречается различных чисел.

Ввод	Вывод
1 2 3 2 1	3

Примечание. Эту задачу на Питоне можно решить в одну строчку.

B: Количество совпадающих

Даны два списка чисел, которые могут содержать до 100000 чисел каждый. Посчитайте, сколько чисел содержится одновременно как в первом списке, так и во втором.

Ввод	Вывод
1 2 3 4 3 2	2

Примечание. Эту задачу на Питоне можно решить в одну строчку.

С: Пересечение списков

Даны два списка чисел, которые могут содержать до 100000 чисел каждый. Выведите все числа, которые входят как в первый, так и во второй список в порядке возрастания.

Ввод	Вывод
1 2 3 4 3 2	2 3

Примечание. И даже эту задачу на Питоне можно решить в одну строчку.

D: Встречалось ли число раньше

Во входной строке записана последовательность чисел через пробел. Для каждого числа выведите слово YES (в отдельной строке), если это число ранее встречалось в последовательности или NO, если не встречалось.

Ввод	Вывод
1 2 3 2 3 4	NO NO NO YES YES NO

E: Кубики

Аня и Боря любят играть в разноцветные кубики, причем у каждого из них свой набор и в каждом наборе все кубики различны по цвету. Однажды дети заинтересовались, сколько существуют цветов таких, что кубики каждого цвета присутствуют в обоих наборах. Для этого они занумеровали все цвета случайными числами. На этом их энтузиазм иссяк, поэтому вам предлагается помочь им в оставшейся части.

Номер любого цвета — это целое число в пределах от 0 до 10⁹. В первой строке входного файла записаны числа N и M — количество кубиков у Ани и Бори соответственно. В следующих N строках заданы номера цветов кубиков Ани. В последних M строках номера цветов кубиков Бори.

Выведите сначала количество, а затем отсортированные по возрастанию номера цветов таких, что кубики каждого цвета есть в обоих наборах, затем количество и отсортированные по возрастанию номера остальных цветов у Ани, потом количество и отсортированные по возрастанию номера остальных цветов у Бори.

Ввод	Вывод
4 3 0 1 10 9 1 3 0	2 0 1 2 9 10 1 3

F: Количество слов в тексте

Во входном файле (вы можете читать данные из файла input.txt записан текст. Словом считается последовательность непробельных символов идущих подряд, слова разделены одним или большим числом пробелов,

Определите, сколько различных слов содержится в этом тексте.

Ввод	Вывод
She sells sea shells on the sea shore; The shells that she sells are sea shells I'm sure. So if she sells sea shells on the sea shore, I'm sure that the shells are sea shore shells.	19

G: Угадай число

Август и Беатриса играют в игру. Август загадал натуральное число от 1 до n. Беатриса пытается угадать это число, для этого она называет некоторые множества натуральных чисел. Август отвечает Беатрисе YES, если среди названных ей чисел есть задуманное или NO в противном случае. После нескольких заданныъх вопросов Беатриса запуталась в том, какие вопросы она задавала и какие ответы получила и просит вас помочь ей определить, какие числа мог задумать Август.

Первая строка входных данных содержит число n — наибольшее число, которое мог загадать Август. Далее идут строки, содержащие вопросы Беатрисы. Каждая строка представляет собой набор чисел, разделенных пробелами. После каждой строки с вопросом идет ответ Августа: YES или NO.

Наконец, последняя строка входных данных содержит одно слово HELP. Вы должны вывести (через пробел, в порядке возрастания) все числа, которые мог задумать Август.

Ввод	Вывод
10 1 2 3 4 5 YES 2 4 6 8 10 NO HELP	1 3 5

H: Угадай число - 2

Август и Беатриса продолжают играть в игру, но Август начал жульничать. На каждый из вопросов Беатрисы он выбирает такой вариант ответа YES или NO, чтобы множество возможных задуманных чисел оставалось как можно больше. Например, если Август задумал число от 1 до 5, а Беатриса спросила про числа 1 и 2, то Август ответит NO, а если Беатриса спросит про 1, 2, 3, то Август ответит YES.

Если же Бетриса в своем вопросе перечисляет ровно половину из задуманных чисел, то Август из вредности всегда отвечает NO.

Наконец, Август при ответе учитывает все предыдущие вопросы Беатрисы и свои ответы на них, то есть множество возможных задуманных чисел уменьшается.

Вам дана последовательность вопросов Беатрисы. Приведите ответы Августа на них.

Первая строка входных данных содержит число n — наибольшее число, которое мог загадать Август. Далее идут строки, содержащие вопросы Беатрисы. Каждая строка представляет собой набор чисел, разделенных пробелами. Последняя строка входных данных содержит одно слово HELP.

Для каждого вопроса Беатрисы выведите ответ Августа на этот вопрос. После этого выведите (через пробел, в порядке возрастания) все числа, которые мог загадать Август после ответа на все вопросы Беатрисы.

Ввод	Вывод
10 1 2 3 4 5 2 4 6 8 10 HELP	NO YES 6 8 10

I: Полиглоты

Каждый из \(N\) школьников некоторой школы знает \(M_i\) языков. Определите, какие языки знают все школьники и языки, которые знает хотя бы один из школьников.

Первая строка входных данных содержит количество школьников \(N\). Далее идет \(N\) чисел \(M_i\), после каждого из чисел идет \(M_i\) строк, содержищих названия языков, которые знает \(i\)-й школьник. Длина названий языков не превышает 1000 символов, количество различных языков не более 1000. \(1 \le N \le 1000\), \(1 \le M_i \le 500\).

Ввод	Вывод
3 3 Russian English Japanese 2 Russian English 1 English	1 English 3 Russian Japanese English

J: Забастовки

Политическая жизнь одной страны очень оживленная. В стране действует K политических партий, каждая из которых регулярно объявляет национальную забастовку. Дни, когда хотя бы одна из партий объявляет забастовку, при условии, что это не суббота или воскресенье (когда и так никто не работает), наносят большой ущерб экономике страны.

\(i\)-я партия объявляет забастовки строго каждые \(b_i\) дней, начиная с дня с номером \(a_i\). То есть \(i\)-я партия объявляет забастовки в дни \(a_i\), \(a_i+b_i\), \(a_i+2b_i\) и т.д. Если в какой-то день несколько партий объявляет забастовку, то это считается одной общенациональной забастовкой.

В календаре страны \(N\) дней, пронумерованных от \(1\) до \(N\). Первый день года является понедельником, шестой и седьмой дни недели — выходные, неделя состоит из семи дней.

Программа получает на вход число дней в году \(N\) \((1\le N\le10^6)\) и число политических партий \(K\) \((1\le K\le100)\). Далее идет \(K\) строк, описывающие графики проведения забастовок. \(i\)-я строка содержит числа \(a_i\) и \(b_i\) \((1\le a_i, b_i\le N)\).

Выведите единственное число: количество забастовок, произошедших в течение года.

Ввод	Вывод
19 3 2 3 3 5 9 8	8

Примечание. Первая партия объявляет забастовки в дни 2, 5, 8, 11, 14, 17. Вторая партия объявляет забастовки в дни 3, 8, 13, 18. Третья партия — в дни 9 и 17. Дни номер 6, 7, 13, 14 являются выходными. Таким образом, общенациональные забастовки пройдут в дни 2, 3, 5, 8, 9, 11, 17, 18.