Множества

ID 57756. Ленивое призерство

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

На олимпиаде участникам даны \(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\)).

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

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

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

ID 50937. Игра с числами

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

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

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

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

ID 49316. Угадай число

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

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

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

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

ID 47637. Паровозики на числовой прямой

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

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

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

Ограничения

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

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

Примеры

3
3 6
1 5
4 7

7

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

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

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

Ограничения

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

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

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

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

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

Ограничения

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

Примеры

3
4 9 5 
5
9 4 9 8 4

5 8

ID 47198. Удаление элементов, которые есть во втором массиве

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

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

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

Ограничения

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

Примеры

3
4 9 5 
5
9 4 9 8 4

5

ID 47197. Объединение массивов

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

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

Ограничения

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

ID 47196. Пересечение массивов

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

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

Ограничения

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

Примеры

3
4 9 5 
5
9 4 9 8 4

4 9

ID 43786. Нет такой оценки!

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

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

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

Примеры

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 43377. Только различные слова

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


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

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

Примеры

ID 43376. Не больше двух

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

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

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

Примеры

4
0 8 9 5 
6 7 3 7 
4 3 5 5

0 3 4 5 6 7 8 9

3
1 2 3
1 2 3
4 5 6

1 2 3 4 5 6

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!» (без кавычек) и с новой строки задачи, которые девочки решить не могут (номера задач следует выводить в порядке возрастания через один пробел).

Примеры

4
3 1 2 3
2 2 4

5
3 1 2 3
2 2 3

ID 42269. Космическая дорожная карта

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

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

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

Примеры

5 3
andoria kanda badjor betazed ueno
andoria badjor ueno

Yes
No
Yes
No
Yes

7 7
a b c d e f g
a b c d e f g

Yes
Yes
Yes
Yes
Yes
Yes
Yes

ID 38364. Черепахи

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

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

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

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

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

Примеры

ID 38122. Acowdemia III

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

• C если в ячейке корова
• G если в ячейке трава
• . если в ячейке нет ни коровы, ни травы

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

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

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

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

 

Примеры

Abc123

YES

Abc[a!

NO

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» в том порядке, в котором они произошли, выведите строку и номер столбца места, на которое должен сесть учащийся

Примеры

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. 

Примеры

ID 37707. Игра для Маши

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

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

Примеры