Множества


Плюсануть
Поделиться
Класснуть
Запинить


Условие задачи Прогресс
ID 30685. Отрезки
Темы: Множества   

Имеется прямая, покрашенная в белый цвет. На нее добавляют n черных отрезков один за другим.
Определите количество компонент связности из черных отрезков (то есть количество черных отрезков в объединении) после каждого добавления отрезка.
В частности, считайте, что если один отрезок заканчивается в точке x, а другой отрезок начинается в точке x, то эти два отрезка лежат в одной компоненте связности.
 
Входные данные
В первой строке следует целое число n (1 ≤ n ≤ 200 000) — количество отрезков.
i-я из следующих n строк содержит два целых числа li и ri (1 ≤ li < ri ≤ 109) — координаты левого и правого концов отрезка номер i. Отрезки перечислены в порядке их добавления на белую прямую.
 
Выходные данные
Выведите n целых чисел — количество компонент связности из черных отрезков после каждого добавления отрезка.

 
Примеры
№ Входные данные Выходные данные
1
3
1 3
4 5
2 4
 1 2 1
2
9
10 20
50 60
30 40
70 80
90 100
60 70
10 40
40 50
80 90
 1 2 3 4 5 4 3 2 1

 
 
ID 33106. Использование SET
Темы: Множества   

Напишите программу, которая будет выполнять последовательность запросов вида ADD num, PRESENT num и COUNT (без параметра). Программу обязательно следует писать с использованием шаблонного типа set.
 
Выполнение каждого запроса вида ADD num должно добавлять элемент num во множество (если такой элемент уже есть, добавление ещё одной копии не изменяет множество), на экран при этом ничего не выводится.
 
При выполнении каждого запроса вида PRESENT num должно выдаваться сообщение «YES» или «NO» (большими буквами, в отдельной строке), соответственно тому, есть ли такой элемент во множестве; значение множества при этом не изменяется.
 
При выполнении каждого запроса вида COUNT должна выдаваться на экран в отдельной строке текущее количество различных элементов в множестве; значение множества при этом не изменяется.
 
Входные данные
В первой строке стандартного входного потока задано количество запросов N (1 < N < 100000), далее следуют N строк, каждая из которых содержит по одному запросу согласно описанного формата.
 
Значения чисел не превышают по модулю 100000000.
 
Выходные данные
Выводите на стандартный выход (экран) в отдельных строках результаты запросов PRESENT и COUNT; на запросы ADD ничего выводить не надо.

 
Примеры
№ Входные данные Выходные данные
1
7
ADD 5
ADD 7
COUNT
PRESENT 3
PRESENT 5
ADD 3
COUNT
2
NO
YES
3

ID 37688. Тренировка памяти
Темы: Множества   

Дениска решил тренировать память Мишки. Для этого он решил называть некоторые числа. А Мишка для каждого числа должен говорить слово YES, если это число ранее уже называлось Дениской или NO, если не называлось. Помогите Дениске потренировать Мишку, напишите программу, которая бы показывала какой ответ должен произносить Мишка.

Входные данные
Вводится список чисел. Все числа списка находятся на одной строке.

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

Примеры
№ Входные данные Выходные данные
1 1 2 3 2 3 4 NO
NO
NO
YES
YES
NO

ID 37687. Сортировка множеств
Темы: Множества   

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

Программу на Python попробуйте написать в одну строчку.


Входные данные 
Вводятся два списка чисел. Все числа каждого списка находятся на отдельной строке.

Выходные данные 
Выведите ответ на задачу.

 
Примеры
№ Входные данные Выходные данные
1 1 3 2
5 1 2		 1 2

ID 37689. Игра с числами
Темы: Множества   

Игры с числами для Дениски с Мишкой стали самыми любимыми. Теперь они играют следующим образом. 
Дениска дает Мишке следующие команды:
1) запомнить a - после этой команды Мишка должен запомнить очередное число a
2) забыть a - после этой команды Мишка забывает о том, что число a было (Дениска всегда называет число a, которое раньше точно было)
Играет продолжается некоторое число шагов, которое заранее обговаривается. После всех шагов Мишка должен в порядке возрастания назвать все уникальные числа, которые он запомнил.

Входные данные
На вход подается число N (\(1 <= N <= 100000\)) - количество шагов в игре. В следующих N строках содержатся  команды в следующем формате:
символ ‘+’ (запомнить число) или ‘-’ (забыть число) и через пробел число a (\(1 <= a <= 1000000000\)).
Гарантируется, что если число a необходимо забыть, то до этого оно уже встречалось с командой '+' и не забывалось. 

Выходные данные
Требуется вывести все уникальные числа (по возрастанию), которые в итоге запомнил Мишка после выполнения всех запросов или -1, если таких чисел в итоге не оказалось.
 

Примеры
№ Входные данные Выходные данные
1
3
+ 1
+ 2
- 1
 2
2
3
+ 1
+ 1
- 1
 -1
3
3
+ 1
+ 1
+ 1
 1

 
ID 37690. Близость мыслей
Темы: Множества   

Дениска и Мишка записывают свои наборы чисел. Причем у каждого мальчика все числа различны. Затем ребята определяют на сколько близко сходятся их мысли, то есть сколько чисел присутствуют в обоих наборах, и по сколько различных в каждом наборе. 

Входные данные
В первой строке входного файла записаны числа N и M — количество чисел у Дениски и Мишки соответственно. В следующих N строках заданы числа Дениски. В последних M строках - числа Мишки.

Выходные данные 
Выведите сначала количество, а затем отсортированные по возрастанию числа такие, которые есть в обоих наборах, затем количество и отсортированные по возрастанию остальные числа из набора Дениски, потом количество и отсортированные по возрастанию числа из набора Мишки.
 
Примеры
№ Входные данные Выходные данные
1 4 3
0
1
10
9
1
3
0		 2
0 1
2
9 10
1
3

ID 37685. Методы работы с множествами
Темы: Множества   

Дениска думает, что он может сказать сколько уникальных чисел в последовательности, которую придумал Мишка. Помогите Дениске. Напишите для него программу, которая выполнит все вычисления за него.

(На языке Python программу можно написать в одну строчку. Попробуйте!)

Входные данные
На вход подается последовательность чисел.

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

 

Примеры
№ Входные данные Выходные данные
1 4 5 7 2 3 3 2  5

ID 37699. Шарики на день рождения
Темы: Множества   

На дне рождения у Мишки присутствовало n детей. Каждый ребенок получил в подарок по m воздушных шариков. Цвет шарика условно задан некоторым натуральным числом. 
Определите, есть ли шарики одинакового цвета у всех детей, если есть выведите номера этих цветов в порядке возрастания, в противном случае выведите -1.

Входные данные
В первой строке задаются числа n (\(0 < n <= 100\)) и m (\(1 <= m <= 50\)). Далее идут n строк по m чисел в каждой - номера цветов воздушных шариков у i-го ребенка. Цвет кодируется натуральным числом не превышающим 20.

Выходные данные
Выведите на экран в порядке возрастания номера совпадающих у всех ребят цветов, если таких нет выведите -1.

 

Примеры
№ Входные данные Выходные данные
1 5 6
1 4 1 3 5 5
3 5 1 4 4 4
5 2 3 1 1 1
4 2 5 4 1 5
5 1 3 2 3 5		 1 5
2 2 2
1 2
3 4		 -1

 
ID 37701. Гласные или согласные
Темы: Множества   

Миша переписываясь с друзья в whatsapp, решил определить, каких символов в его последнем сообщении больше - латинских гласных или латинских согласных? При подсчете он учитывает и прописные, и строчные буквы (одни и те же строчные и прописные буквы считаются различными), одинаковые буквы считаются один раз.

Входные данные: строка, содержащая буквы и пробелы. Других символов в ней нет.
Выходные данные: выведите слово vowels, если больше гласных, consonants - если согласных, и знак = в случае равенства

Алфавит (гласные буквы выделены жирным):
Aa Bb Cc Dd Ee Ff Gg Hh Ii Jj Kk Ll Mm Nn Oo Pp Qq Rr Ss Tt Uu Vv Ww Xx Yy Zz


Примеры
№ Входные данные Выходные данные
1 its sunny today vowels
2 Hello how are you =

 
ID 37686. Работа с множествами. Методы - 2
Темы: Множества   

Мишка решил проверить способности Дениски на других задачах. Например, решил проверить сможет ли Дениска из двух списков чисел быстро посчитать количество чисел, которые встречаются одновременно в обоих. Как мы знаем Дениска любит хвастаться и сказал, что запросто это сделает. Вас же он просит написать для него программу. 
На языке Python это можно сделать в одну строчку.

Входные данные
Вводятся два списка чисел. Все числа каждого списка находятся на отдельной строке.

Выходные данные
Выведите ответ на задачу.

 

Примеры
№ Входные данные Выходные данные
1 1 3 2
5 1 2		 2

ID 37700. Две строки
Темы: Множества   

Маша и Даша пишут друг другу сообщения через whatsapp. Затем они решили определить символы (учитывая регистр), которые есть в сообщении Маши, но нет в сообщении Даши. Напишите программу, которая сделает это за девочек 

Входные данные: в первой строке задается сообщение Маши, во второй - Даши
Выходные данные: выведите ответ на задачу. Символы выводить в алфавитном порядке.

 

Примеры
№ Входные данные Выходные данные
1 Hallo
Hi		 a l o

 
ID 33107. Количество различных чисел
Темы: Множества   

Даша записывает различные числа, но иногда забывает и пишет повторяющиеся. Маша хочет определить, сколько различных чисел записала Даша. Автоматизируйте вычисления Маши.
 
Входные данные: Вводится список целых чисел. Все числа списка находятся на одной строке. Всего чисел не более 100000.
Выходные данные: Выведите ответ на задачу.

 

Примеры
№ Входные данные Выходные данные
1 1 2 3 2 1 3

 
ID 33293. Встречалось ли число раньше
Темы: Множества   

Даша записывает определенное количество чисел, а Маша следит за тем повторялось ли уже записанное число или нет. Если повторялось Маша говорит YES, если нет - NO. Маша устала и хочет, чтобы вы автоматизировали ее работу. Помогите ей. 

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

 

Примеры
№ Входные данные Выходные данные
1 6
1 2 3 2 3 4
NO
NO
NO
YES
YES
NO

ID 37703. Оценки по информатике
Темы: Множества   

Маша, Даша и Миша получили некоторое количество оценок по информатике. Маша и Даша хотят посмотреть какие из оценок встречались у них, но не встречались у Миши. Напишите программу для решения этой задачи.

Входные данные: в первой строке задается число N (\(0 < N <=100\)) - количество оценок каждого ребенка. 
Далее идет 3 строки по N чисел в каждой - оценки Маши, Даши и Миши соответственно. Оценки у ребят в школе выставляются по 100 бальной шкале.
Выходные данные: выведите на экран оценки, которые встречались у Маши и Даши, но не встречались у Миши. Оценки выводите в порядке возрастания. Если таких оценок нет, вывести -1

 

Примеры
№ Входные данные Выходные данные
1 5
5 4 6 4 5
5 2 3 6 6
5 5 2 1 2		 3 4 6

 
ID 37704. Мишины оценки
Темы: Множества   

Маша, Даша и Миша получили некоторое количество оценок по информатике. Маша и Даша хотят посмотреть какие из оценок встречались у Миши, но не встречались у них. Напишите программу для решения этой задачи.

Входные данные: в первой строке задается число N (\(0 < N <=100\)) - количество оценок каждого ребенка. 
Далее идет 3 строки по N чисел в каждой - оценки Маши, Даши и Миши соответственно. Оценки у ребят в школе выставляются по 100 бальной шкале.
Выходные данные: выведите на экран оценки, которые встречались у Миши, но не встречались у Маши и Даши. Оценки выводите в порядке возрастания. Если таких оценок нет, вывести -1

 

Примеры
№ Входные данные Выходные данные
1 5
5 4 6 4 5
5 2 3 6 6
5 5 2 1 2		 1

 
ID 37705. Карточки для Даши
Темы: Множества   

Маша предлагает Даше сыграть в следующую игру. Маша пишет на листочке число, а перед Дашей лежат карточки с цифрами от 0 до 9. Задача Даши выбрать себе такие карточки, на которых записаны цифры, которые не используются в записи числа Маши.

Входные данные: на вход подается натуральное число, не превыщающее 109
Выходные данные: выведите на экран в порядке возрастания карточки, которые должна взять Даша. Если в числе Маши используются все цифры от 0 до 9, то выведите -1

 

Примеры
№ Входные данные Выходные данные
1 2007 1 3 4 5 6 8 9

 
ID 37706. Карточки для Миши
Темы: Множества   

Маша предлагает Мише сыграть в следующую игру. Маша пишет на листочке два числа, а перед Мишей лежат карточки с цифрами от 0 до 9. Задача Миши выбрать себе такие карточки, на которых записаны цифры, которые используются для записи как первого числа, так и второго.

Входные данные: на вход подаются два натуральных числа, не превыщающие 109. Каждое число в отдельной строке
Выходные данные: выведите на экран в порядке возрастания карточки, которые должен взять Миша. Если Миша не может взять ни одной карточки, то выведите -1

 

Примеры
№ Входные данные Выходные данные
1 514
233		 -1
2 1248
3472		 2 4

 
ID 37707. Игра для Маши
Темы: Множества   

Даша предлагает Маше сыграть в следующую игру. Даша пишет на листочке одно число, а задача Маши записать другое число, используя только цифры, которые есть в числе Даши. Напишите программу, которая выводит цифры, используемые Машей для записи своего числа, если Маша выполнила условие Даши, в противном случае выведите на экран слово losing

Входные данные: на вход подаются два натуральных числа (сначала число Даши, затем число Маши), не превыщающие 109. Каждое число в отдельной строке
Выходные данные: выведите в порядке возрастания требуемые цифры, или слово losing

 

Примеры
№ Входные данные Выходные данные
1 5112648
1246		 1 2 4 6
2 64141
1246		 losing

 
ID 37708. Тренировки
Темы: Множества   

Внешкольная жизнь Маши, Даши и Миши очень насыщенная. Все вместе дети посещают \(K\) кружков. Дни, когда работает какой-либо кружок, родителям после работы приходится отвозить ребят на тренировки. Если дни занятий не выходные (суббота или воскресенье), то такие дни считаются загруженными.
Все кружки работают через определенное число дней. i-й кружок работает каждый \(b_i\) день, начиная с дня c номером \(a_i\). То есть i-й кружок работает в дни \(a_i\), \(a_i+b_i\), \( a_i+2b_i\) и т.д. 
В календаре дополнительных занятий \(N\) дней, пронумерованных от 1 до \(N\). Первый день всегда понедельник, шестой и седьмой дни - выходные, неделя состоит из семи дней.

Входные данные: программа получает на вход число дней в календаре \(N\) (\(1<=N<=10^6\)) и число кружков \(K\) (\(1<=K<=100\)). Далее идет \( K\) строк, описывающие графики проведения тренировок. \(i\)-я строка содержит числа \(a_i\) и \(b_i\) (\(1<=a_i,b_i<=N\)).

Выходные данные: выведите единственное число: количество загруженных дней у родителей в течение всего календаря занятий.

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

 

Примеры
№ Входные данные Выходные данные
1 19 3
2 3
3 5
9 8		 8

 
ID 37877. Первое впечатление может быть обманчивым
Темы: Множества   

Нани с первых минут невзлюбила Стича и даже боялась оставаться вместе с ним в одном доме. Но спустя время она разглядела в малыше добрую душу и приняла его в свою семью. Вместе со Стичем пришлось приютить и его создателя Джамбо, которому пришлось остаться на Земле. 
Чтобы запомнить имена новых знакомых инопланетян, Джамбо вносит их в компьютер. Имена инопланетянин могут содержать самые различные символы, но всегда удоавлетворяют особым правилам. Правила следующие: все имена содержат только латинские буквы (заглавные и строчные), цифры и знак подчёркивания. Имя всегда начинается либо с буквы, либо со знака подчеркивания. Другие символы в именах отсутствуют. 
Напишите для Джамбо программу, которая бы проверяла правильно ли он занес в компьютер имя очередного знакомого.

Входные данные
На вход программы подаётся символьная строка - имя, которое Джамбо занес в компьютер.

Выходные данные
Программа должна вывести ответ 'YES', если строка представляет собой имя, составленное по правилам задачи, и 'NO' в противном случае.  

 

Примеры
№ Входные данные Выходные данные
1 
Abc123
 
YES
2 
Abc[a!
 
NO

 
ID 38122. Acowdemia III
Темы: Множества    Жадный алгоритм   

Фермер Джон открыл пастбище с целью помочь Беси и её друзьям.
Пастбище ФД можно рассматривать как большую 2D-решётку квадратных ячеек. Каждая ячейка помечена таким образом:

  • C если в ячейке корова
  • G если в ячейке трава
  • . если в ячейке нет ни коровы, ни травы
Для того, чтобы две различные коровы стали друзьями, коровы должны встретиться в ячейке с травой, которая горизонтально или вертикально соседствует с каждой из них. Во время этого процесса они съедают траву в этой ячейке, поэтому другая пара коров уже не сможет использовать эту ячейку как место встречи. Любая корова может подружиться более чем с одной другой коровой, но никакая пара коров не может встретиться и стать друзьями более одного раза.

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

ФОРМАТ ВВОДА:
Первая строка содержит N и M.
Каждая из следующих N строк содержит M символов, описывая пастбище.

ФОРМАТ ВЫВОДА:
Определите максимальное количество пар коров, которые могут стать друзьями.
 
№ Входные данные Выходные данные
1 4 5
.CGGC
.CGCG
CGCG.
.CC.C
 4

Если мы пометим корову в строке i и столбце j координатами (i,j), тогда в этом примере есть коровы в (1,2), (1,5), (2,2), (2,4), (3,1), (3,3), (4,2), (4,3), and (4,5). Один из способов, чтобы 4 коровы стали друзьями таков:

Коровы из (2,2) и (3,3) едят траву в (3,2).
Коровы из (2,2) и (2,4) едят траву в (2,3).
Коровы из (2,4) и (3,3) едят траву в (3,4).
Коровы из (2,4) и (1,5) едят траву в (2,5).
ID 42269. Космическая дорожная карта
Темы: Множества   

Дениска хочет отправиться в космическое путешествие на кораблях с варп-двигателями. Для этого он купил космическую дорожную карту. На первой открытой межгалактической варп-линии, управляемой МТК (Межзвездной транспортной компанией), есть N станций. i-я станция (1<=i<=N) от начальной станции называется Si.
Обычные космические корабли останавливаются на всех станциях, в то время как варп-корабли (космические корабли с варп-двигателями) останавливаются только на M (M <= N) станциях, а j-я станция (1 <= j <= M) - это станция с именем Tj.
Здесь гарантируется, что T1 = S1 и TM = SN , то есть варп-корабли останавливаются как на начальной, так и на конечной станциях.
Дениска хочет прокатиться на варп-корабле. Для каждой из N станций определите, сможет ли Дениска попасть на эту станции на варп-корабле.

Входные данные
Программа получает на вход три строки. Первая строка содержит два целых числа N и M (2 <= M <= N <=105). Вторая строка содержит N различных слов Si (1 <= i <= N, ), разделенных пробелом - название станций, на которых останавливаются обычные космические корабли. Третья строка содержит M различных слов Tj (1 <= j <= M, ), разделенных пробелом - название станций, на которых останавливаются варп-корабли. Все слова в третьей строке (T1,...,TM) получается путем удаления нуля или более строк из (S1,...,SN) и выстраиваем оставшихся слов в ряд, не меняя порядок. 

Выходные данные
Выведите N строк. i-я строка (1<= i <=N) должна содержать Yes, если Дениска доберется на варп-корабле до i-й станции от начальной станции, иначе - No.
 
 

Примеры
№ Входные данные Выходные данные
1 
5 3
andoria kanda badjor betazed ueno
andoria badjor ueno
 
Yes
No
Yes
No
Yes
2 
7 7
a b c d e f g
a b c d e f g
 
Yes
Yes
Yes
Yes
Yes
Yes
Yes

ID 37709. Соблюдайте дистанцию!
Темы: Множества   

Во время пандемии 2020 года, в школе Маши, Даши и Миши переоборудовали столовую с учетом требований соблюдения дистанции. Для каждого класса все столы были одноместные и расставлялись в виде сетки, состоящей из \(N\) рядов, пронумерованных от \(1\) до \(N\), и двух столбцов, пронумерованных от \(1\) до \(2\). Расстояние между столами \((R_a, C_a)\) и \((R_b, C_b)\) равно евклидому расстоянию между центрами соответствующих клеток, а именно \(\sqrt {(R_a - R_b)^2 + (C_a - C_b)^2}\)
Каждый ученик класса, приходя в столовую, размещается как можно дальше от других учеников. Точнее говоря, дежурный класса назначает ученику свободное место, расстояние от которого до ближайшего занятого места максимально. Если имеется более одного такого места, то дежурный всегда назначает место с номером в меньшем ряду, а если есть несколько таких мест, он выбирает место с наименьшим столбцом. После того, как дежурный назначил место, учащийся должен сидеть только за этим столом до окончания обеда, после обеда учащийся покидает столовую, сообщая об этом дежурному. Если в столовой никого нет, то входящему учащемуся всегда назначается место в ряду 1 и столбце 1. 
В школе Маши, Даши и Миши все ученики прилежные и всегда занимают те места, которые им были указаны.
Но так как дежурные иногда задерживаются на уроках, они просят Вас написать программу, которая учитывая последовательность событий и тип каждого события, автоматически назначала бы место для учащегося. Изначально столовая пуста.
События нумеруются от \(1\) до \(M\) в том порядке, в котором они происходят. Существует два вида событий: событие типа "E" соответствует учащемуся, купившему обед, и которому нужен стол, а событие типа "L" соответствует учащемуся, который закончил обедать и освободил вышел из-за стола. Для события типа "L" также дается число P - оно указывает, что уходящий ученик - это тот, который купил обед во время события P.
Гарантируется, что в столовой всегда будет хотя бы одно свободное место, когда учащийся купил для себя обед.

Входные данные: Первая строка содержит два целых числа N и M (1 <= N <= 150000, 1 <= M <= 30000), количество рядов в словой и количество событий. Следующие M строк содержат описание событий, K-я из этих строк содержит описание события K - либо символ «E», либо символ «L», за которым следует целое число Pk (1 <= Pk < K). Гарантируется, что событие Pk относится к типу «E», и ни один учащийся не будет пытаться уйти из столовой дважды.
Выходные данные: Для каждого события типа «E» в том порядке, в котором они произошли, выведите строку и номер столбца места, на которое должен сесть учащийся

 

Примеры
№ Входные данные Выходные данные
1 3 7
E
E
E
L 2
E
L 1
E		 1 1
3 2
1 2
3 1
1 1
2 13 9
E
E
E
E
E
E
E
E
E		 1 1
13 2
7 1
4 2
10 1
2 2
3 1
5 1
6 2
3 10 9
E
E
E
E
L 3
E
E
L 6
E		 1 1
10 2
5 2
7 1
4 2
2 2
4 1
 

 
ID 43374. Задачи для тренировки
Темы: Множества   

Алиса и Юля, ученицы 6-В класса одной из московских школ, вместе готовятся к олимпиаде по программированию. Для того, чтобы хорошо выступить на олимпиады, они должны решить все задачи тренировочного контеста.

Всего у девочек n задач. Алиса может точно решить p задач контеста. А Юля может решить только q задач этого же контеста. У вас есть информация о номерах задач, которые может решить Алиса, и номера задач, которые может решить Юля. Смогут ли девочки решить все задачи этого контеста и хорошо выступить на олимпиаде, если объединят свои усилия и будут решать контекст вместе?

 

Входные данные

В первой строке записано единственное целое число n (1 <=  n <= 100).

В следующей строке сначала записано целое число p (0 <= p <=n), затем следуют p различных целых чисел a1, a2, ..., ap (1 <= ai<= n). Эти числа обозначают номера задач, которые может решить Алиса. В следующей строке содержатся номера задач, которые может решить Юля, в аналогичном формате. Предполагается, что задачи пронумерованы от 1 до n.


Выходные данные

Если подружки могут решить все задачи вместе, выведите «I'm winner!». Если это невозможно, выведите «Oh!» (без кавычек) и с новой строки задачи, которые девочки решить не могут (номера задач следует выводить в порядке возрастания через один пробел).

 
Примеры
№ Входные данные Выходные данные
1 
4
3 1 2 3
2 2 4
 I'm winner!
2 
5
3 1 2 3
2 2 3
 Oh!
4 5

ID 43377. Только различные слова
Темы: Множества   

Маша читает книги чаще всего в электронном виде. Сегодня она захотела узнать, сколько в книге, которую она сейчас читает, различных слов. Помогите Маше написать для этого программу.
 Словом считается последовательность непробельных символов, идущих подряд, слова разделены одним или большим числом пробелов.
Знаками препинания .,;:-?! необходимо пренебречь. Регистр написания символов не учитывается.


Входные данные
Программа получает на строку текста.

Выходные данные
Выведите количество различных слов в этой строке.
 
 

Примеры
№ Входные данные Выходные данные
1 This is my book! 4
2 The next day, business began to pick up. Not dramatically, but bit by bit. A sack of potatoes here... 18

ID 43376. Не больше двух
Темы: Множества   

Маша, Даша и Миша собирают карточки с числами. У каждого из них уже есть по n карточек. На каждой карточке написано число, не превышающее 10. Вас интересует какие числа встречаются, но не более, чем у двоих из ребят?
Напишите программу для нахождения ответа на этот вопрос.
 

Входные данные
В первой строке записано натуральное число n - количество карточек у каждого ребенка. В каждой из трех следующих строк записаны по n неотрицательных целых чисел, не превышающих 10, разделенных пробелом. Во второй строке - числа на карточках Маши, в третьей - Даши, в четвертой - Миши.

Выходные данные
Выведите на экран одну строку - множество чисел в порядке возрастания, разделенных пробелами, которые встречаются, но не более чем у двоих из ребят.

 
Примеры
№ Входные данные Выходные данные
1 
4
0 8 9 5 
6 7 3 7 
4 3 5 5
 
0 3 4 5 6 7 8 9
2 
3
1 2 3
1 2 3
4 5 6
 
1 2 3 4 5 6

ID 38364. Черепахи
Темы: Одномерные массивы    Множества   

Широко известна следующая задача для младших школьников. Три черепахи ползут по дороге. Одна черепаха говорит: “Впереди меня две черепахи”. Другая черепаха говорит: “Позади меня две черепахи”. Третья черепаха говорит: “Впереди меня две черепахи и позади меня две черепахи”. Как такое может быть? Ответ: третья черепаха врет!

По дороге одна за другой движутся N черепах. Каждая черепаха говорит фразу вида: “Впереди меня ai черепах, а позади меня bi черепах”. Ваша задача определить самое большое количество черепах, которые могут говорить правду.

Входные данные
В первой строке вводится целое число N (1 ≤ N ≤ 10000) . Далее следуют N строк, содержащих целые числа ai и bi, по модулю не превосходящие 10000, описывающие высказывание i-ой черепахи.

Данные о высказываниях черепах приведены в произвольном порядке, то есть первое высказывание не обязательно соответствует черепахе, идущей во главе колонны, второе - не обязательно следующей за ней и так далее

Выходные данные
Выведите целое число M – максимальное количество черепах, которые могут говорить правду.
 

Примеры
№ Входные данные Выходные данные
1 3
2 0
0 2
2 2		 2

ID 43786. Нет такой оценки!
Темы: Множества   

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

Входные данные
На вход программе подаются оценки трех учеников, разделенные символом пробела (оценки каждого ученика на отдельной строке, оценки записаны по 10-бальной шкале: от 0 до 10).

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

 

Примеры
№ Входные данные Выходные данные
1 
1 5 4 2 5 6 6 2 3 3 5 2
2 3 5 1 2 1 2 6 7 1 1 6
1 4 6 8 8 7 0 6 0 3 8 1
 
9 10

ID 30684. Множества в C++
Темы: Standard Template Library    Множества   

Входные данные
Дано число N (1 <= N <= 100000) – кол-во запросов. В следующих N строках содержится символ ‘+’ или ‘-’ и число a (1 <= a <= 1000000000). Если символ – ‘+’, то число a добавляется в множество, иначе – удаляются все значения a, которые были добавлены ранее.
Гарантируется, что при удалении числа, оно содержится в множестве.

Выходные данные
Требуется вывести в порядке возрастания все уникальные элементы в множестве после выполнения всех запросов или «-1», если в множестве нет элементов.

 

Примеры
№ Входные данные Выходные данные
1
3
+ 1
+ 2
- 1
 2
2
3
+ 1
+ 1
- 1
 -1
3
3
+ 1
+ 1
+ 1
 1