Plus
Pin


Problem description Progress
ID 30685. Segments
Темы: Sets   

There is a straight line, painted white. n black segments are added to it one by one.
Determine the number of connected black segments (that is, the number of black segments in the union) after each segment addition.
In particular, consider that if one segment ends at point x and another segment begins at point x, then these two segments lie in the same connected component.
 
Input
The first line is an integer n (1 ≤ n ≤ 200 000) — number of segments.
i-th of the next n lines contains two integers li and ri (1 ≤ li < ri ≤ 109) — coordinates of the left and right ends of segment number i. The segments are listed in the order they were added to the white line.
 
Output
Print n integers — the number of connected components from black segments after each addition of a segment.

 
Examples
# Input Output
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. Using SET
Темы: Sets   

Write a program that will execute a sequence of queries like ADD num, PRESENT num, and COUNT (without a parameter). The program must be written using the set template type.
 
Each query like ADD num should add element num to the set (if such an element already exists, adding another copy does not change the set), and nothing is displayed.
 
Each query like PRESENT num should return a "YES" message; or "NO" (in capital letters, on a separate line), according to whether there is such an element in the set; the value of the set does not change.
 
When executing each query of the COUNT type, the current number of different elements in the set should be displayed on a separate line; the value of the set does not change.
 
Input
The first line of the standard input contains N requests (1 < N < 100000), followed by N lines, each containing one request according to the described format.
 
Number values ​​do not exceed 100000000 modulo.
 
Output
Print to standard output (screen) on separate lines the results of PRESENT and COUNT queries; no output is required for ADD queries.

 
Examples
# Input Output
1
7
ADD 5
ADD 7
COUNT
PRESENT 3
PRESENT 5
ADD 3
COUNT
2
NO
YES
3

ID 37688. Memory training
Темы: Sets   

Deniska decided to train Mishka's memory. To do this, he decided to name some numbers. And Mishka for each number must say the word YES, if this number was previously called Deniska or NO, if it was not called. Help Deniska train Mishka, write a program that would show what answer Mishka should pronounce.

Input
Enter a list of numbers. All numbers in the list are on the same line.

Imprint 
For each number, print the word YES (in a separate line) if this number has previously occurred in the sequence or NO if it has not.
 

Examples
# Input Output
1 1 2 3 2 3 4 NO
NO
NO
YES
YES
NO

ID 37687. Set sorting
Темы: Sets   

Help Deniska from two lists of numbers to display in ascending order those that are included in both the first and second lists.

Try writing a Python program in one line.


Input  
Two lists of numbers are entered. All numbers of each list are on a separate line.

Imprint 
Print the answer to the problem.

 
Examples
# Input Output
1 1 3 2
5 1 2
1 2

ID 37689. Number game
Темы: Sets   

Games with numbers for Deniska and Mishka have become the most favorite. Now they play like this. 
Deniska gives Mishka the following commands:
1) remember a - after this command Mishka must remember the next number a
2) forget a - after this command, Mishka forgets that the number a was (Deniska always says the number a, which was exactly before)
The game continues for a certain number of steps, which is agreed in advance. After all the steps, the Bear must name in ascending order all the unique numbers that he remembered.

Input
The input is the number N (\(1 <= N <= 100000\)) - the number of steps in the game . The following N lines contain  commands in the following format:
character ‘+’ (remember number) or ‘-’ (forget the number) followed by a space separated number a (\(1 <= a <= 1000000000\)).
It is guaranteed that if the number a needs to be forgotten, then it has already been encountered with the command '+' and not forgotten. 

Imprint
It is required to display all unique numbers (in ascending order) that Mishka eventually remembered after executing all requests or -1 if there were no such numbers in the end.
 

Examples
# Input Output
1
3
+1
+2
-1
2
2
3
+1
+1
-1
-1
3
3
+1
+1
+1
1

 

ID 37690. closeness of thoughts
Темы: Sets   

Deniska and Mishka write down their sets of numbers. Moreover, each boy has different numbers. Then the guys determine how closely their thoughts converge, that is, how many numbers are present in both sets, and how many are different in each set. 

Input
The first line of the input file contains the numbers N and M — the number of numbers for Deniska and Mishka, respectively. The following N lines contain Deniska numbers. In the last M lines - Mishka's numbers.

Imprint 
Print first the quantity, and then the numbers sorted in ascending order, those that are in both sets, then the quantity and the remaining numbers sorted in ascending order from Deniska's set, then the quantity and numbers sorted in ascending order from Mishka's set.
 
Examples
# Input Output
1 4 3
0
1
10
9
1
3
0
2
0 1
2
9 10
1
3

ID 37685. Set Methods
Темы: Sets   

Deniska thinks that he can say how many unique numbers in the sequence that Mishka came up with. Help Denis. Write a program for him that will do all the calculations for him.

(You can write a program in Python in one line. Try it!)

Input
The input is a sequence of numbers.

Imprint 
Print on the screen how many distinct numbers occur in the sequence. 

 

Examples
# Input Output
1 4 5 7 2 3 3 2  5

ID 37699. birthday balloons
Темы: Sets   

Mishka had n children at his birthday party. Each child received m balloons as a gift. The color of the ball is conditionally given by some natural number. 
Determine if all children have balls of the same color. If so, print the numbers of these colors in ascending order, otherwise print -1.

Input
The first line contains numbers n (\(0 < n <= 100\)) and m  (\(1 <= m <= 50\)). Then there are n lines with m numbers in each - numbers of colors of balloons of the i-th child. Color is encoded by a natural number not exceeding 20.

Imprint
Print on the screen, in ascending order, the numbers of colors that match all the guys, if there are none, print -1.

 

Examples
# Input Output
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. Vowels or consonants
Темы: Sets   

Misha, while chatting with friends on whatsapp, decided to determine which characters in his last message are more - Latin vowels or Latin consonants? When counting, it takes into account both uppercase and lowercase letters (the same lowercase and uppercase letters are considered different), the same letters are counted once.

Input: string containing letters and spaces. There are no other characters in it.
Output: print the word vowels if there are more vowels, consonants if there are more consonants, and sign = in case of equality

Alphabet:
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


Examples
# Input Output
1 it's sunny today vowels
2 Hello how are you =

 

ID 37686. Working with sets. Methods - 2
Темы: Sets   

Mishka decided to test Deniska's abilities on other tasks. For example, I decided to check whether Deniska from two lists of numbers can quickly calculate the number of numbers that occur simultaneously in both. As we know, Deniska likes to show off and said that he would easily do it. He asks you to write a program for him. 
In Python, this can be done in one line.

Input
Two lists of numbers are entered. All numbers of each list are on a separate line.

Imprint
Print the answer to the problem.

 

Examples
# Input Output
1 1 3 2
5 1 2
2

ID 37700. Two lines
Темы: Sets   

Masha and Dasha write messages to each other via whatsapp. Then they decided to determine the characters (case sensitive) that are in Masha's message but not in Dasha's message. Write a program that will do it for the girls 

Input data: Masha's message is given in the first line, Dasha's message in the second line
Output: print the answer to the problem. Display characters in alphabetical order.

 

Examples
# Input Output
1 Hallo
Hi
al o

 

ID 33107. Number of different numbers
Темы: Sets   

Dasha writes down different numbers, but sometimes she forgets and writes the same ones. Masha wants to determine how many different numbers Dasha wrote down. Automate Masha's calculations.
 
Input: A list of integers is entered. All numbers in the list are on the same line. There are no more than 100000 numbers in total.
Output: Print the answer to the problem.

 

Examples
# Input Output
1 1 2 3 2 1 3

 

ID 33293. Has the number been seen before?
Темы: Sets   

Dasha writes down a certain number of numbers, and Masha keeps track of whether the already written number is repeated or not. If repeated Masha says YES, if not - NO. Masha is tired and wants you to automate her work. Help her. 

Input: The first line contains the number of numbers N (1<=N<=100 000), the second line contains a list of numbers separated by a space. 
Output: For each number, print the word YES (in a separate line) if this number has previously occurred in the sequence, or NO if it has not.
 

 

Examples
# Input Output
1 6
1 2 3 2 3 4
NO
NO
NO
YES
YES
NO

ID 37703. Computer science grades
Темы: Sets   

Masha, Dasha and Misha received a number of marks in computer science. Masha and Dasha want to see which of the ratings they met, but did not meet with Misha. Write a program to solve this problem.

Input: The first line contains the number N (\(0 < N <= 100\)) - the number of ratings for each child. 
Then there are 3 lines of N numbers in each - Masha's, Dasha's and Misha's scores respectively. Children's grades at school are given on a 100-point scale.
Output: Display the scores that Masha and Dasha encountered but Misha did not. List your scores in ascending order. If there are no such estimates, output -1

 

Examples
# Input Output
1 5
5 4 6 4 5
5 2 3 6 6
5 5 2 1 2
3 4 6

 

ID 37704. Mishina scores
Темы: Sets   

Masha, Dasha and Misha received a number of marks in computer science. Masha and Dasha want to see which of the ratings met with Misha, but did not meet with them. Write a program to solve this problem.

Input: The first line contains the number N (\(0 < N <= 100\)) - the number of ratings for each child. 
Then there are 3 lines of N numbers in each - Masha's, Dasha's and Misha's scores respectively. Children's grades at school are given on a 100-point scale.
Output: Display the scores that Misha had but Masha and Dasha did not. List your scores in ascending order. If there are no such estimates, output -1

 

Examples
# Input Output
1 5
5 4 6 4 5
5 2 3 6 6
5 5 2 1 2
1

 

ID 37705. Cards for Dasha
Темы: Sets   

Masha invites Dasha to play the next game. Masha writes a number on a piece of paper, and Dasha has cards with numbers from 0 to 9 in front of Dasha. Dasha's task is to choose cards that contain numbers that are not used in Masha's number.

Input: the input is a natural number not exceeding 109
Output: Display in ascending order the cards Dasha should take. If Masha's number contains all digits from 0 to 9, then print -1

 

Examples
# Input Output
1 2007 1 3 4 5 6 8 9

 

ID 37706. Cards for Misha
Темы: Sets   

Masha invites Misha to play the next game. Masha writes two numbers on a piece of paper, and in front of Misha are cards with numbers from 0 to 9. Misha's task is to choose such cards for himself, on which numbers are written, which are used to write both the first number and the second.

Input: The input is two natural numbers not exceeding 109. Each number on a separate line
Output: Display in ascending order the cards that Misha should take. If Misha cannot take any cards, then print -1

 

Examples
# Input Output
1 514
233
-1
2 1248
3472
2 4

 

ID 37707. Game for Masha
Темы: Sets   

Dasha invites Masha to play the next game. Dasha writes one number on a piece of paper, and Masha's task is to write another number using only the numbers that are in Dasha's number. Write a program that prints the numbers used by Masha to write down her number if Masha fulfilled Dasha's condition, otherwise display the word losing

Input: The input is two natural numbers (first Dasha's number, then Masha's number) not exceeding 109. Each number on a separate line
Output: print in ascending order the required numbers, or the word losing

 

Examples
# Input Output
1 5112648
1246
1 2 4 6
2 64141
1246
losing

 

ID 37708. Workout
Темы: Sets   

The extracurricular life of Masha, Dasha and Misha is very eventful. Together, the children attend \(K\) circles. The days when a circle is working, parents have to take the children to training after work. If the days of classes are not weekends (Saturday or Sunday), then such days are considered busy.
All circles work through a certain number of days. The i-th circle runs every \(b_i\) day, starting from the day numbered \(a_i\). That is, the i-th circle works on the days \(a_i\), \(a_i+b_i\)\( a_i+2b_i\) etc. 
In the extra class calendar, \(N\) days are numbered from 1 to \(N\). The first day is always Monday, the sixth and seventh days are holidays, the week consists of seven days.

Input: The program receives as input the number of days in the calendar \(N\) (\(1<=N<=10^6\)) and number of circles \(K\) (\(1<=K<=100\)). Next comes \( K\) lines describing training schedules. \(i\)th line contains numbers \(a_i\) and \(b_i\)  (\(1<=a_i,b_i<=N\)).

Output: print a single number: the number of busy days parents have during the entire class calendar.

Note: The first circle runs on days 2, 5, 8, 11, 14, 17. The second circle runs on days 3, 8, 13, 18. The third circle - on days 9 and 17. Days 6, 7, 13, 14 are days off. So days 2, 3, 5, 8, 9, 11, 17, 18 will be loaded. 

 

Examples
# Input Output
1 19 3
23
3 5
98
8

 

ID 37877. First impressions can be deceiving
Темы: Sets   

Nani from the first minutes disliked Stitch and was even afraid to stay with him in the same house. But after a while, she saw a kind soul in the baby and accepted him into her family. Together with Stitch, his creator Jumbo, who had to stay on Earth, had to be sheltered. 
To remember the names of new aliens he knows, Jumbo enters them into the computer. Alien names can contain a wide variety of characters, but always satisfy specific rules. The rules are as follows: all names contain only Latin letters (uppercase and lowercase), numbers and underscores. The name always starts with either a letter or an underscore. There are no other characters in the names. 
Write a program for Jumbo that would check if he entered the name of the next acquaintance into the computer correctly.

Input
The input of the program is a character string - the name that Jumbo entered into the computer.

Imprint
The program should output the answer 'YES' if the string is a problem-formed name, and 'NO' otherwise.  

 

Examples
# Input Output
1
Abc123
YES
2
Abc[a!
NO

 

ID 38122. Acowdemia III
Темы: Sets    Greedy Algorithm   

Farmer John opened a pasture to help Besie and her friends.
The PD pasture can be viewed as a large 2D grid of square cells. Each cell is labeled like this:

  • C if the cell contains a cow
  • G if the cell contains grass
  • . if there is no cow or grass in the cell
In order for two different cows to become friends, the cows must meet in a cell with grass that is horizontally or vertically adjacent to each of them. During this process, they eat the grass in that cell, so another pair of cows can no longer use that cell as a meeting place. Any cow can befriend more than one other cow, but no pair of cows can meet and become friends more than once.

The FD hopes that many pairs of cows will become friends. Determine the maximum number of pairs of cows that can become friends.

INPUT FORMAT:
The first line contains N and M.
Each of the next N lines contains M characters describing a pasture.

OUTPUT FORMAT:
Determine the maximum number of pairs of cows that can become friends.
 
# Input Output
1 4 5
.CGGC
.CGCG
CGCG.
.CC.C
4

If we label the cow in row i and column j with coordinates (i,j), then in this example there are cows in (1,2), (1,5), (2,2), (2,4), (3 ,1), (3,3), (4,2), (4,3), and (4,5). One way for 4 cows to become friends is this:

Cows from (2,2) and (3,3) eat grass in (3,2).
Cows from (2,2) and (2,4) eat grass in (2,3).
Cows from (2,4) and (3,3) eat grass in (3,4).
Cows in (2,4) and (1,5) eat grass in (2,5).

ID 42269. space roadmap
Темы: Sets   

Deniska wants to go on a space journey on ships with warp engines. To do this, he bought a space roadmap. There are N stations on the first open intergalactic warp line operated by the ITC (Interstellar Transportation Company). The ith station (1<=i<=N) from the start station is called Si.
Regular spaceships stop at all stations, while warp ships (spaceships with warp drives) only stop at M (M <= N) stations, and jth station (1 <= j <= M) is the station named Tj.
Here it is guaranteed that T1 = S1 and T= SN , i.e. warp ships stop both at the starting and end stations.
Deniska wants to ride the warpship. For each of the N stations, determine if Deniska can get to that station in the warpship.

Input
The program receives three lines as input. The first line contains two integers N and M (2 <= M <= N <=105). The second line contains N different words Si (1 <= i <= N, ) separated by a space - the title stations where conventional spacecraft stop. The third line contains M various words Tj (1 <= j <= M, ) separated by a space - the name of the stations where warp ships stop. All words in the third line (T1,...,TM) is obtained by removing zero or more lines from (S1,... ,SN) and line up the remaining words without changing the order. 

Imprint
Output N lines. The i-th line (1<= i <=N) should contain Yes if Deniska gets to the i-th station from the starting station by warp ship, otherwise - No< /code>.
 
 

Examples
# Input Output
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. Keep your distance!
Темы: Sets   

During the 2020 pandemic, at Masha, Dasha and Misha's school, the canteen was refurbished to comply with social distancing requirements. For each class, all tables were single and arranged in a grid consisting of \(N\) rows, numbered from \( 1\) to \(N\), and two columns numbered from \(1\)< /span> to \(2\). Distance between tables \((R_a, C_a)\) and \((R_b, C_b)\) equals the Euclidean distance between the centers of the corresponding cells, namely \(\sqrt {(R_a - R_b)^2 + (C_a - C_b)^2}\)
Each student in the class, coming to the dining room, is placed as far as possible from other students. More precisely, the class attendant assigns the student a free place, the distance from which to the nearest occupied place is maximum. If there is more than one such seat, then the attendant always assigns the seat with the number in the smallest row, and if there are several such seats, he chooses the seat with the smallest column. After the duty officer has appointed a place, the student should only sit at this table until the end of lunch, after lunch the student leaves the dining room, informing the duty officer about this. If no one is in the cafeteria, the incoming student is always assigned a seat in row 1 and column 1. 
At the school of Masha, Dasha and Misha, all the students are diligent and always take the places that they were assigned.
But since attendants are sometimes late in class, they ask you to write a program that, given the sequence of events and the type of each event, would automatically assign a seat to the student. Initially, the dining room is empty.
Events are numbered from \(1\) to \(M\) in the order in which they occur . There are two kinds of events: an event of type "E" corresponds to a student who has bought lunch and needs a table, and an event of type "L" corresponds to a student who has finished lunch and freed left the table. For an event of type "L", a number P is also given - this indicates that the outgoing student is the one who bought lunch at the time of the P event .
It is guaranteed that there will always be at least one free seat in the cafeteria when a student buys their own lunch.

Input: The first line contains two integers N and M ( 1 <= N <= 150000, 1 <= M <= 30000), the number of rows per word, and the number of events. The following M lines contain a description of the event, K-th of these lines contains a description of the event K - or the symbol « ;E", or the character "L" followed by an integer Pk (1 <= Pk < K). The Pk event is guaranteed to be of type «E» and no student will try to leave the cafeteria twice .
Output: For each event of type «E» in the order in which they happened, output the row and column number of the seat where the student should sit

 

Examples
# Input Output
1 3 7
E
E
E
L2
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
L6
E
1 1
10 2
5 2
7 1
4 2
2 2
4 1
 

 

ID 43374. Tasks for training
Темы: Sets   

Alisa and Yulia, 6-B students at a Moscow school, are preparing for a programming competition together. In order to perform well at the Olympiad, they must solve all the problems of the training contest.

The girls have n tasks in total. Alice can accurately solve p contest problems. Yulia can only solve q problems of the same contest. You have information about the numbers of problems that Alice can solve and the numbers of problems that Yulia can solve. Will the girls be able to solve all the problems of this contest and perform well at the Olympiad if they unite their efforts and solve the context together?

 

Input

The first line contains a single integer n (1 <=  n <= 100).< /p>

The next line is an integer first (0 <= p <=n) followed by p various integers a1, a2< /code>, ..., ap (1 <= ai <= n). These numbers indicate the numbers of problems that Alice can solve. The next line contains the numbers of problems that Yulia can solve in a similar format. Tasks are assumed to be numbered from 1 to n.


Output

If the girls can solve all the problems together, print "I'm winner!". If this is not possible, print "Oh!" (without quotes) and from a new line of problems that girls cannot solve (problem numbers should be output in ascending order, separated by one space).

 
Examples
# Input Output
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. Just different words
Темы: Sets   

Masha reads books most often in electronic form. Today she wanted to know how many different words are in the book she is currently reading. Help Masha write a program for this.
 A word is a sequence of consecutive non-whitespace characters separated by one or more spaces.
Punctuation .,;:-?! must be ignored.


Input
The program receives a line of text.

Imprint
Print the number of distinct words in this string.
 
 

Examples
# Input Output
1 This is my book! 4
2 The next day, business began to pick up. Not abruptly, but bit by bit. A sack of potatoes here... 18

ID 43376. No more than two
Темы: Sets   

Masha, Dasha and Misha collect cards with numbers. Each of them already has n cards. Each card has a number not exceeding 10. Are you interested in what numbers occur in no more than two of the guys?
Write a program to find the answer to this question.
 

Input data
The first line contains a natural number n - the number of cards each child has. Each of the following three lines contains n positive numbers, not exceeding 10, separated by a space. In the second line - the numbers on Masha's cards, in the third - Dasha, in the fourth - Misha.

Imprint data
Print one line - a set of numbers in ascending order, separated by spaces, which occur in no more than two of the guys.

 
Examples
# Input Output
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. Turtles
Темы: One-Dimensional Arrays    Sets   

The following problem for younger students is widely known. Three turtles crawl along the road. One turtle says, "There are two turtles ahead of me." The other turtle says, "There are two turtles behind me." The third turtle says, "There are two turtles in front of me and two turtles behind me." How can this be? Answer: the third turtle is lying!

N turtles move one after another along the road. Each turtle says a phrase like: “In front of me are ai turtles, and behind me are bi turtles”. Your task is to determine the largest number of turtles that can tell the truth.

Input
The first line contains an integer N (1 ≤ N ≤ 10000) . Then N lines follow, containing integers ai and bi, modulo not exceeding 10000, describing the statement of the i-th turtle.

The data on turtle statements are given in random order, that is, the first statement does not necessarily correspond to the turtle walking at the head of the column, the second - not necessarily following it, and so on

Imprint
Print an integer M – the maximum number of turtles that can tell the truth.
 

Examples
# Input Output
1 3
20
0 2
2 2
2

ID 43786. There is no such score!
Темы: Sets   

Masha, Dasha and Misha have a 10-point grading scale in additional lessons in mathematics. Each of the guys received a certain number of marks. Write a program that prints out many grades that none of them have.

Input
The program receives the marks of three students separated by a space character (the marks of each student are on a separate line, the marks are written on a 10-point scale: from 0 to 10).

Imprint 
The program should display a set of ratings in ascending order on one line, separated by spaces, in accordance with the condition of the problem.

 

Examples
# Input Output
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. Sets in C++
Темы: Standard Template Library    Sets   

Input
Given a number N (1 <= N <= 100000) – number of requests. The following N lines contain the character ‘+’ or ‘-’ and the number a (1 <= a <= 1000000000). If the symbol – ‘+’, then the number a is added to the set, otherwise – removes all a values ​​that were previously added.
It is guaranteed that when a number is removed, it is contained in the set.

Imprint
It is required to display in ascending order all unique elements in the set after all queries are completed, or "-1" if there are no elements in the set.

 

Examples
# Input Output
1
3
+1
+2
-1
2
2
3
+1
+1
-1
-1
3
3
+1
+1
+1
1