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

Задачи из рубрикатора

Тег: Множества

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

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

Ввод Вывод
3
1 3
4 5
2 4
1 2 1
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 

(с) Курбатов Е., 2018
 

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

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

Ввод Вывод
7
ADD 5
ADD 7
COUNT
PRESENT 3
PRESENT 5
ADD 3
COUNT
2
NO
YES
3
https://informatics.msk.ru/moodle/mod/statements/view.php?chapterid=3453#

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 Xx Yy Zz


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

 

ID 37686: Работа с множествами. Методы - 2
Работа с множествами. Методы - 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
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).