Множества


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


Условие задачи Прогресс
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 попробуйте написать в одну строчку.


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

Формат выходных данных 
Выведите ответ на задачу.
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 (2 ≤ N,M ≤ 1000).
Каждая из следующих 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

ID 47196. Пересечение массивов
Темы: Множества   

Даны два целочисленных массива nums1 и nums2. Сформируйте третий массив путем пересечения элементов заданных двух массивов. Каждый элемент результирующего массива должен быть уникальным. Элементы должны быть выведены в порядке возрастания.

Входные данные
В первой строке записано число n - количество элементов массива nums1. Вторая строка содержит n чисел nums1i - элементы массива. Треться строка содержит число m - количество элементов массива nums2. Четвертая строка содержит m чисел nums2i - элементы массива.

Ограничения

  • 1 <= длина массива nums1 и длина массива nums2 <= 1000
  • 0 <= nums1i, nums2i <= 1000


Выходные данные
Выведите результирующий массив. Все элементы должны быть выведены в одной строке через пробел в порядке возрастания.
 
 
Примеры
№ Входные данные Выходные данные
1 
3
4 9 5 
5
9 4 9 8 4
 
4 9

ID 47197. Объединение массивов
Темы: Множества   

Даны два целочисленных массива nums1 и nums2. Сформируйте третий массив путем объединения элементов заданных двух массивов. Каждый элемент результирующего массива должен быть уникальным. Элементы должны быть выведены в порядке возрастания.

Формат входных данных 
В первой строке записано число n - количество элементов массива nums1. Вторая строка содержит n чисел nums1i - элементы массива. Треться строка содержит число m - количество элементов массива nums2. Четвертая строка содержит m чисел nums2i - элементы массива.

Ограничения

  • 1 <= длина массива nums1 и длина массива nums2 <= 1000
  • 0 <= nums1i, nums2i <= 1000

Формат выходных данных 
Выведите результирующий массив. Все элементы должны быть выведены в одной строке через пробел. 
ID 47198. Удаление элементов, которые есть во втором массиве
Темы: Множества   

Даны два целочисленных массива nums1 и nums2. Удалите из массива nums1 элементы, которые есть в nums2. Выведите все уникальные элементы массива nums1 после удаления. Элементы должны быть выведены в порядке возрастания.

Программа не должна содержать каких-либо дополнительных массивов или других переменных, кроме указанных двух.

Входные данные
В первой строке записано число n - количество элементов массива nums1. Вторая строка содержит n чисел nums1i - элементы массива. Треться строка содержит число m - количество элементов массива nums2. Четвертая строка содержит m чисел nums2i - элементы массива.

Ограничения

  • 1 <= длина массива nums1 и длина массива nums2 <= 1000
  • 0 <= nums1i, nums2i <= 1000


Выходные данные
Выведите результирующий массив. Все элементы должны быть выведены в одной строке через пробел.
 
 
Примеры
№ Входные данные Выходные данные
1 
3
4 9 5 
5
9 4 9 8 4
 
5

ID 47199. Элементы первого и второго массива, но не в обоих сразу
Темы: Множества   

Даны два целочисленных массива nums1 и nums2. Обновите элементы массива nums1, оставив только уникальные среди тех, которые присутствуют в массиве nums1 и в nums2, но не в обоих сразу. Выведите все уникаьлные элементы массива nums1 после обновления. Элементы должны быть выведены в порядке возрастания.

Программа не должна содержать каких-либо дополнительных массивов или других переменных, кроме указанных двух.

Входные данные
В первой строке записано число n - количество элементов массива nums1. Вторая строка содержит n чисел nums1i - элементы массива. Треться строка содержит число m - количество элементов массива nums2. Четвертая строка содержит m чисел nums2i - элементы массива.

Ограничения

  • 1 <= длина массива nums1 и длина массива nums2 <= 1000
  • 0 <= nums1i, nums2i <= 1000


Выходные данные
Выведите результирующий массив. Все элементы должны быть выведены в одной строке через пробел.
 
 
Примеры
№ Входные данные Выходные данные
1 
3
4 9 5 
5
9 4 9 8 4
 
5 8

ID 47200. Элементы, которых нет в другом массиве
Темы: Множества   

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

Формат входных данных 
В первой строке записано число n - количество элементов массива nums1. Вторая строка содержит n чисел nums1i - элементы массива. Треться строка содержит число m - количество элементов массива nums2. Четвертая строка содержит m чисел nums2i - элементы массива.

Ограничения

  • 1 <= длина массива nums1 и длина массива nums2 <= 1000
  • 0 <= nums1i, nums2i <= 1000

Формат выходных данных 
Выведите результирующий массив. Все элементы должны быть выведены в одной строке через пробел.
ID 27098. Шифрование
Темы: Задача на реализацию    Множества    Структуры данных   

Одним из самых простых способов шифрования открытого текста является шифр простой замены. Он состоит в том, что каждая буква в алфавите, которым написано открытое сообщение, заменяется на какой-то другой символ, например, другую букву того же алфавита. Пусть дана таблица замены, использующая для замены только 33 буквы русского алфавита в верхнем регистре (заглавные буквы):
   

Сообщение Шифртекст Сообщение Шифртекст Сообщение Шифртекст
А Г К Т Х З
Б Ш Л Х Ц Ж
В Ы М Я Ч Л
Г О Н Ь Ш Ё
Д Э О Ф Щ Н
Е Ц П У Ъ Д
Ё М Р К Ы Е
Ж Ъ С Ю Ь Б
З Щ Т Р Э Ч
И А У П Ю И
Й В Ф С Я Й

Если применить замену, заданную такой таблицей, к слову «ДОМ», получится зашифрованный текст «ЭФЯ». Если применить замену к полученному результату, из «ЭФЯ» получится «ЧСЙ», а из «ЧСЙ» таким способом можно получить текст «ЛЮВ». Известно, что через некоторое количество применений замены полученный результат совпадет с исходным словом «ДОМ», после чего результаты замены начнут повторяться. Определите, сколько различных шифртекстов (включая совпадающий с исходным словом) можно получить из произвольного заданного слова по произвольно заданной таблице замены таким способом.

Рекомендации.
До начала работы над программной реализацией постарайтесь найти ответы на следующие вопросы:
1. Сколько различных зашифрованных текстов (включая и совпадающий с открытым текстом) можно получить одной операцией замены из открытого текста с n различными буквами, используя все возможные таблицы замены.
2.Можно ли получить все возможные зашифрованные тексты (число которых установлено в пункте 1), применяя к результату зашифрования операцию замены символов по одной и той же таблице неограниченное число раз.

Формат ввода:
В первой строке задана строка с  алфавитом используемых символов. Во второй строке задана последовательность заглавных букв, заменяющих буквы, стоящие в алфавитном порядке (таблица замены). Например, приведенной выше таблице соответствует строка «ГШЫОЭЦМЪЩАВТХЯЬФУКЮРПСЗЖЛЁНДЕБЧИЙ». В следующей строке задано слово, являющееся открытым текстом – в верхнем регистре (заглавными буквами) без пробелов. Например, слово «КРИПТОАНАЛИЗ».
Каждая из этих строк заканчивается либо символами с кодами 13, 10 (окончание строк DOS – для Pascal ABC .NET), либо символом с кодом 10 (окончание строк Unix) в зависимости от выбранного при сдаче программы типа конца строк. Никаких других символов в двух входных строка не встречается.
Русский текст задан в кодировке Windows-1251 (cp1251). В ней заглавные русские буквы от "А" до "Я" кроме буквы "Ё" имеют коды от 192 (шестнадцатеричное C0) до 223 (шестнадцатеричное DF). Буква "Ё" имеет код 168 (шестнадцатеричное A8). Русские буквы (кроме "Ё") упорядочены по алфавиту.

Формат вывода:
В единственной строке выведите число, соответствующее количеству различных возможных шифртекстов, которые можно получить из заданного открытого текста с помощью заданной таблицы замены.
 
Ввод Вывод
АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ
ГШЫОЭЦМЪЩАВТХЯЬФУКЮРПСЗЖЛЁНДЕБЧИЙ
КРИПТОАНАЛИЗ		 42
АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ
УКЮРПСЗЖЛЁНДЕБЧИЙГШЫОЭЦМЪЩАВТХЯЬФ
СВЕРХСЕКРЕТНО		 154

ID 47637. Паровозики на числовой прямой
Темы: Информатика    Множества   

Паровозики стоят на железной дороге параллельно друг другу на параллельных участках пути. Условно весь участок железной дороги можно представить в виде числовой прямой. В этом случае i-й паровозик на данной числовой прямой покрывает некоторое количество заданных целых точек (от точки starti до точки endi, включая данные точки).

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

Входные данные
В первой строке записано число N - количество паровозиков на железной дороге. В следующих N строках записаны по 2 числа (starti, endi)  - тоски начала и конца i-го паровозика. 

Ограничения

1 <= N <= 100
1 <= starti <= endi <= 100


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

Примеры
№ Входные данные Выходные данные Примечания
1 
3
3 6
1 5
4 7
 
7
 Все точки от 1 до 7 покрыты хотя бы одним паровозиком. Поэтому ответ 7.

ID 27218. Bovine Genomics
Темы: Строки    Хеш    Множества   

У Фермера Джона NN коров с пятнами и NN коров без пятен. Пройдя курс генетики, ФД убеждён, что пятна у коров вызваны мутацией генов.
За большие деньги ФД зафиксировал геномы своих коров. Каждый геном это строка длиной MM, состоящая из символов A, C, G, T. Когда он выписал все геномы у него получилась такая таблица, N=3 и M=8:
 
Позиция  :                   1 2 3 4 5 6 7 8
 
Пятнистая корова 1:  A A T C C C A T
Пятнистая корова 2:  A C T T G C A A
Пятнистая корова 3:  G G T C G C A A
 
Корова без пятен 1:  A C T C C C A G
Корова без пятен 2:  A C T C G C A T
Корова без пятен 3:  A C T T C C A T

Посмотрев внимательно на эту таблицу, он заметил, что последовательность от позиции 2 до позиции 5 успешна, чтобы объяснять пятнистость. То есть, рассматривая символы в этих позициях (2…5), ФД может предсказать какие из его коров пятнистые, а какие нет. Например, если он видит символы GTCG в этих позициях, он знает, что корова будет пятнистая.
 
Помогите ФД определить длину кратчайшей последовательности позиций, которая может объяснить пятнистость.
 
ФОРМАТ ВВОДА:
 
Первая строка ввода содержит N (1≤N≤500) и M (3≤M≤500). Каждая из N следующих строк содержит по M символов. Эти символы описывают геномы пятнистых коров. Следующие N строк описывают геномы коров без пятен. Никакая пятнистая корова на имеет точно такой же геном, как корова без пятен.
 
ФОРМАТ ВЫВОДА:
 
Пожалуйста, выведите длину кратчайшей последовательности позиций, достаточной для объяснения пятнистости. Последовательность позиций объясняет пятнистость, если по ней можно предсказывать абсолютно точно пятнистая или нет любая из коров ФД.
 
Ввод Вывод
3 8
AATCCCAT
ACTTGCAA
GGTCGCAA
ACTCCCAG
ACTCGCAT
ACTTCCAT
 4


 
ID 49316. Угадай число
Темы: Множества   

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


Формат входных данных

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

Наконец, последняя строка входных данных содержит одно слово HELP.


Формат выходных данных

Вы должны вывести (через пробел, в порядке возрастания) все числа, которые мог задумать Август.
ID 33123. Лифт
Темы: Задача на реализацию    Сортировка событий    Использование сортировки    Множества    Структуры данных   

В современном многоэтажном офисе крупной компании установлен новый лифт. В
компании работает n сотрудников. Для проверки эффективности системы управления
лифтом требуется провести моделирование его работы в конце рабочего дня, когда все
сотрудники должны покинуть здание и спуститься на первый этаж.
В здании m этажей, пронумерованных от 1 до m снизу-вверх. Известно, что i-й
сотрудник подходит к лифту в секунду ti на этаже ai, чтобы спуститься на первый этаж.
На каждом этаже могут находиться люди, ожидающие лифт. Когда очередной
сотрудник подходит к лифту, он вызывает лифт, если на этом этаже лифт еще не вызван,
либо присоединяется к ожидающим лифт. Таким образом, помимо вызвавшего лифт, вместе
с ним лифт могут ожидать и другие сотрудники.
В каждый момент времени не более одного вызова является активным.
Изначально лифт свободен и находится на первом этаже. Когда поступает первый
вызов, этот вызов становится активным и лифт отправляется на соответствующий этаж. Если
несколько вызовов поступает одновременно, активным становится вызов от сотрудника с
меньшим номером.
Лифт перемещается между этажами со скоростью один этаж в секунду. Когда лифт
оказывается на этаже, откуда был сделан активный вызов, в него заходят все, кто уже
ожидает лифт на этом этаже, и лифт отправляется вниз на первый этаж, со скоростью один
этаж в секунду.
При движении вниз лифт останавливается на тех этажах, в которых был сделан вызов
на момент проезда лифта мимо этого этажа. Все ожидающие лифт сотрудники заходят в него
и вызов на этом этаже сбрасывается. Когда лифт завершает движение на первом этаже, все
люди выходят из лифта, а лифт ожидает следующего вызова.
Если в момент, когда лифт освободился, есть хотя бы один необслуженный вызов,
активируется вызов, который поступил раньше других. Если несколько вызовов поступило
одновременно, активируется вызов от сотрудника с меньшим номером. Лифт продолжает
обслуживание описанным образом, пока все n сотрудников не окажутся на первом этаже.
Будем считать, что люди входят и выходят из лифта мгновенно. Каждую секунду
сначала люди подходят и вызывают лифт, а затем выполняются соответствующие действия
(лифт перемещается на соседний этаж, в него входят или из него выходят люди, принимается
решение, на какой вызов лифт должен отреагировать).
Требуется написать программу, которая по описанию вызовов лифта для каждого
сотрудника определяет, в какой момент этот сотрудник окажется на первом этаже.

Формат входных данных
Первая строка входных данных содержит целые числа n и m — количество людей,
вызывающих лифт, и количество этажей в здании (1 ≤ n ≤ 105, 2 ≤ m ≤ 109).
Следующие n строк описывают сотрудников, i-я из этих строк содержит два целых
числа ti и ai — секунду, в которую i-й сотрудник подходит к лифту, и номер этажа, на
котором это происходит (1 ≤ t1 ≤ t2 ≤ … ≤ tn ≤ 109, 2 ≤ ai ≤ m)
 
Формат выходных данных
Выходные данные должны содержать n целых чисел, для каждого сотрудника
требуется вывести секунду, в которую он выйдет из лифта на первом этаже.
 
Ввод Вывод
5 4
2 3
2 4
5 2
5 3
9 3
 
6
12
6
12
12

 
Пояснение к примеру
Пример работы лифта по шагам показан в следующей таблице. 


Использованные в пояснении к примеру обозначения
ID 33128. Обработка больших данных
Темы: Структуры данных    Множества    Динамическое программирование   

В научной лаборатории разрабатывается новая архитектура суперкомпьютера,
позволяющая эффективно обрабатывать большие объемы данных.
Суперкомпьютер имеет 2k ячеек памяти, пронумерованных от 0 до 2k– 1. Отрезком
[L, R] называется последовательность подряд идущих ячеек памяти с номерами от L до R,
включительно.
Некоторые отрезки памяти являются корректными. Отрезок памяти [L, R] является
корректным, если его длина (R – L + 1) равна 2i для некоторого i, а число L делится на 2i.
Например, если k = 3, то ячейки памяти пронумерованы от 0 до 7, а корректными являются
отрезки [0, 7], [0, 3], [4, 7], [0, 1], [2, 3], [4, 5], [6, 7], [0, 0], [1, 1], [2, 2], [3, 3], [4, 4], [5, 5], [6,
6] и [7, 7].
Ключевой операцией в новой архитектуре является операция STORE, которая за одно
действие присваивает одно и то же значение всем ячейкам памяти некоторого корректного
отрезка.
Исходно все ячейки памяти содержат значение 0. В лаборатории планируют запустить
на суперкомпьютере программу обработки данных, но перед её запуском необходимо
инициализировать память определенным образом. А именно: первые с1 ячеек памяти
необходимо заполнить значениями v1, следующие c2 ячеек — значениями v2, и так далее,
последние cn ячеек памяти необходимо заполнить значениями vn, где 1 ≤ vi ≤ m.
Ученым надо выяснить, какое минимальное количество операций STORE необходимо
выполнить, чтобы проинициализировать память требуемым образом.
Например, если k = 3, n = 3, m = 2, c1 = 1, v1 = 1, c2 = 2, v2 = 2, c3 = 5, v3 = 1, то итоговое
содержимое памяти должно быть следующим: [1, 2, 2, 1, 1, 1, 1, 1]. В этом случае для
инициализации памяти достаточно трех операций STORE:
- STORE([0, 7], 1), после этой операции все ячейки памяти содержат значение 1;
- STORE([1, 1], 2), после этой операции содержимое памяти [1, 2, 1, 1, 1, 1, 1, 1];
- STORE([2, 2], 2) , после этой операции содержимое памяти [1, 2, 2, 1, 1, 1, 1, 1],
как и требуется.
Заметим, что операцию STORE([1, 2], 2) выполнить нельзя, потому что [1, 2] не
является корректным отрезком памяти.
Требуется написать программу, которая по заданному содержимому памяти
определяет минимальное количество операций STORE, которое необходимо выполнить для
инициализации памяти заданным образом.

Формат входных данных
Первая строка входных данных содержит три целых числа: k, n и m (0 ≤ k ≤ 30,1 ≤ n ≤ 10
5, 1 ≤ m ≤ 109).
Следующие n строк содержат по два целых числа, i-я из этих строк содержит числа ci
и vi (1 ≤ ci ≤ 2k, 1 ≤ vi ≤ m, c1 + c2 + … + cn = 2k).
Формат выходных данных
Требуется вывести одно целое число – минимальное количество операций STORE,
которое необходимо выполнить для инициализации памяти заданным образом.
 
Ввод Вывод
3 3 2
1 1
2 2
5 1
 3

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

Маша, Даша, Миша и Саша играют с числами. Каждый из них написал некоторое множество целых чисел. Затем они выполнили следующие операции. 
1) Ребята нашли разницу между Машиным и Дашиным множествами.
2) Затем, они объединили множества чисел Миши и Саши.
3) В конце, они нашли общие элементы двух множеств, полученных в результате первой и второй операции. 

Выведите на экран в порядке возрастания числа, которые получились у Маши, Даши, Миши и Саши в результате выполнения третьей операции.

Формат входных данных
Программа получает на вход четыре пары строк (всего восемь строк), в каждой паре строк первая строка содержит целое число Ni - количество чисел в i-й строке (1 <= N <= 106, 1 <= i <= 4), вторая строка каждой пары строк содержит множество целых чисел, разделенных одним пробелом. Во второй строке записано множество чисел Маши, во четвертой - Даши, в шестой - Миши, в восьмой - Саши. Каждое число по модулю не превышает 105.

Формат выходных данных
Выведите на экран одну строку, состоящую из целых чисел - результат выполнения третьей операции. Числа должны быть разделены одним пробелом, числа должны следовать в порядке возрастания.
ID 57756. Ленивое призерство
Темы: Множества    Разреженные таблицы (sparse table)    "Два указателя"   

Алексей, возможно, самый умный и при этом самый ленивый человек в мире. Сегодня он участвует в олимпиаде.

На олимпиаде участникам даны \(n\) задач, за правильное решение \(i\)-й задачи, участник получит \(a_i\) баллов, за неправильное решение баллов не дают. Дипломы призера дадут тем участникам, которые наберут хотя бы половину от суммарного числа баллов. Например, если на олимпиаде дано три задачи, стоимости которых в баллах равны \(1\), \(3\) и \(4\), соответственно, для получения диплома призера достаточно набрать четыре балла.

Алексей пришел на олимпиаду с целью получить диплом призера. При этом Алексей очень умен и может правильно решить любую задачу на олимпиаде. Но в то же время Алексей очень ленив и хочет решить как можно меньше задач.

Алексей настолько ленив, что даже задачи, которые он будет решать, выбирает лениво. Он хочет выбрать некоторую задачу с номером \(k\), а затем решать задачи с номерами \(k, k+1, k+2 \ldots\) до тех пор, пока ему не будет хватать баллов на диплом призера. Максимум, на что готов Алексей, это пропустить одну задачу и не решать ее, чтобы решить в итоге еще меньше задач.

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

Формат входных данных
В первой строке дано одно натуральное число \(n\) — количество задач на олимпиаде (\(1 \le n \le 10^5\)).

Во второй строке заданы \(n\) чисел \(a_1, a_2, \dots a_n\) — стоимости каждой задачи в баллах (\(1 \le a_i \le 10^9\)).

Формат выходных данных
Выведите одно число — минимальное количество задач, которые может решить Алексей, придерживаясь своей стратегии, чтобы получить диплом призера.


Примечание

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

Во втором тесте достаточно решить только вторую задачу, набрав три балла.