In the middle of the year we held the Selective IME-USP, a contest to selects which teams will represent USP Butantã in official competitions. In this test, it is clear that the people at MaratonUSP are very competitive, after all, we are a competitive programming group.
In this edition, the tests are being carried out individually, and no longer in teams of 3 people. After the end of the competition, with the general score already available, Kobus realized that she drew first in the tryouts with $$$N$$$ other participants, who are from POLI. As we accept nothing less than the best ─ even more so against polytechnics ─ she wants to come first. But, unfortunately, the tiebreaker criterion is a draw.
To carry out the draw, Nathan will take the string $$$ A = abcdefghijklmnopqrstuvwxyz $$$, which represents the alphabet, and change some letters of place, obtaining a new string $$$ A'$$$. In other words, $$$A'$$$ is a permutation of $$$A$$$. Using this new string as alphabetical order, Nathan will then sort the names, and the name that comes first is the winner.
Kobus has access to the secret laboratory where Nathan studies and, with that, she can change $$$ A '$$$. Help Kobus to come first or say if that is impossible.
The first line contains an integer $$$N$$$ $$$(1 \leq N \leq 1000)$$$ ─ the number of participants who tied with Kobus in the first place.
Each of the next $$$ N $$$ lines contains a lower character string $$$ s_i $$$ $$$ (1 \leq | s_i | \leq 100) $$$ ─ the name of the $$$ i $$$-th participant tied with Kobus. It is guaranteed that everyone participating in the competition has different names.
Print a string $$$ A '$$$ $$$ (| A' | = 26) $$$ which is a permutation of $$$ A $$$ that makes Kobus come first. If multiple answers exist, print any one.
If it is not possible for Kobus to come first, print "sem chance" (without quotes).
3 lamarca kob grabriel
sem chance
5 fabiana marcos roberto julia maquiesperto
abcdekghijflmnopqrstuvwxyz
Sorting a word list uses the relative order between two words. We can call this relative order a lexicographic order. A word $$$ x_1, x_2, \dots, x_a $$$ is lexicographically smaller than the word $$$ y_1, y_2, \dots, y_b $$$ if one of the two conditions below is valid:
- $$$ a \lt b $$$ e $$$ x_1 = y_1, x_2 = y_2, \dots, x_a = y_a $$$, that is, the first word is a prefix to the second; or if
- there is a position $$$j$$$ $$$(1 \leq j \leq min(a, b))$$$, such that $$$x_1=y_1,x_2=y_2,\dots, x_{j-1}=y_{j- 1}$$$ and $$$x_j \lt y_j$$$, that is, in the first position where the words differ, the letter of the first word in that position is smaller than the letter of the second word in that same position (the letter of the first word comes before in the alphabet than the letter of the second word).
For example, let the list of words be given by $$$ \{aaa, aa, ba \} $$$. If the alphabet is $$$ abcd ... z $$$, then the ordered list is $$$ \{aa, aaa, ba \} $$$. However, if the alphabet is $$$ bacd ... z $$$ then the ordered list becomes $$$ \{ba, aa, aaa \} $$$.
Sedentary lifestyle and loss of body mass is an evil that affects college students, including us, in the Maratona. To stay in shape and avoid health problems, Guidi bought a kit of bars and washers along with a reclining bench to become stronger (monstro).
As a good Maratonista, Guidi asked the great wizard Eterom to create a diet based on the simplex algorithm and an exercise routine optimized with combinatorial techniques. The exercise routine is a sequence of movements, where each movement is represented by a character. It is worth mentioning that the order in which each movement is performed is essential for the exercise's effectiveness.
Guidi, a shrewd and cunning competitor, does not want to let his competitors discover the training of the great magician. To hide his training, he opened a bodybuilding guide at the USP Sports Practice Center (CEPE-USP) and had a great idea: to camouflage his optimized training within some sequence of CEPE movements!
For example, let $$$s o a d s$$$ be the sequence of movements of the great magician's training and $$$t s a s d a s$$$ the sequence of movements of the CEPE's training. The best sequence of exercises that Guidi can do in order to hide his training within a sequence of CEPE training movements is $$$s a d s$$$ (bench press, squat, deadlift and bench press).
Given the movement sequences of the great wizard Eterom and CEPE, help Guidi to discover the size of the largest sequence of movements he can make in order to hide his sacred training.
Two lines with one string each, $$$A$$$ and $$$B$$$ $$$(1 \leq |A|, |B| \leq 1000)$$$ ─ the sequence of movements suggested by the great magician Eterom and the sequence of movements of CEPE, respectively. Strings are made up of lowercase letters.
An integer $$$N$$$ ─ the size of the largest sequence of moves Guidi can make in order to hide his optimized training.
soads tsasdas
4
babanad lalaxadnad
5
People who participate in the world of competitive programming share the same passion, numbers. However, some individuals have preferences, such as natural numbers, integer numbers, transcendental numbers, among others.
Harada is no different, having a certain preference for some numbers, which he considers lucky numbers. In particular, Harada has a list of $$$ Q $$$ lucky numbers.
On his birthday, Harada got a nice little graph and a deck of $$$ N $$$ cards, where each of these cards contains a integer number between $$$ 0 $$$ and $$$ 9 $$$. Now that the birthday party is over, Harada was eager to discover the largest subset of his lucky number list he could form using the cards in his new deck.
For example, suppose the list of lucky numbers is $$$ [23, 111, 112] $$$ and that the deck has $$$ 6 $$$ cards, four cards with the number $$$ 1 $$$, a card with the number $$$ 2 $$$ and a card with the number number $$$ 3 $$$. Then, it would be able to form the following subsets: $$$ \{23 \} $$$, $$$ \{111 \} $$$, $$$ \{112 \} $$$, $$$ \{23, 111 \} $$$, with $$$ \{23, 111 \}$$$ being the biggest one.
However, wanting to avoid bad luck ─ after all, he doesn't play with his own lucky numbers! ─ Harada asked for your help in carrying out this task.
The first line contains two integers $$$Q$$$ and $$$N$$$ $$$(1 \leq Q \leq 7)$$$, $$$(1 \leq N \leq 100)$$$ ─ the number of lucky numbers in the Harada list and the number of cards in the deck he got on birthday, respectively.
The second line contains $$$ Q $$$ distinct integers ─ where $$$ q_i $$$ $$$ (0 \leq q_i \leq 10^9) $$$ is the $$$i$$$-th lucky number on Harada's list. It is guaranteed that no number in the list have leading zeros.
The third and last line contains $$$ N $$$ integers ─ where $$$ n_i $$$ $$$ (0 \leq n_i \leq 9) $$$ is the number of the $$$ i $$$-th card in the deck that Harada got on birthday.
On the first line, print an integer $$$R$$$ ─ the size of the largest subset of the lucky numbers that Harada can form.
On the second line, print $$$ R $$$ distinct numbers ─ where $$$ r_i $$$ is the $$$ i $$$-th luck number of the largest subset.
The order in which the numbers are printed on the second line does not matter, and if there is more than one subset, print any.
3 6 23 111 112 1 2 3 1 1 1
2 23 111
6 10 400 289 22 0 20 24 9 5 0 0 1 2 4 2 0 8
3 400 289 0
Like any very organized group, MaratonUSP likes to prepare well in advance. Thus, Lamarca was in charge of organizing a mashup for the next $$$ 10 ^ {18} $$$ days. As it is a team contest, and no team wants to be harmed by having few competitors, the number of people who will participate in the contest must be a multiple of $$$ 3 $$$.
Lamarca created a poll on Telegram for the next $$$ 10 ^ {18} $$$ days, but he forgot to allow participants to vote on multiple options. However, when talking to each other, people realized that everyone who could participate in a $$$ x $$$ day could also participate in every day after $$$ x $$$.
When choosing a date, ALL people who can participate on that day will show up, but if the number of people is not a multiple of $$$ 3 $$$, a team will be sad and there will be total chaos. Clearly, Lamarca does not want chaos and would also like to choose the best day for Mashup.
Help Lamarca discover this day! The best day is the day when the greatest number of people go and the contest still happens, that is, the day when the greatest number of people goes and that no team is sad. Or say if there is no date with these characteristics.
The first line contains a single integer $$$ N $$$ $$$ (3 \leq N \leq 10 ^ 6) $$$ ─ representing the number of contest participants.
The second contains $$$ N $$$ integers $$$ a_i $$$ $$$ (1 \leq a_i \leq 10 ^ {18}) $$$ ─ $$$ a_i $$$ represents the date from which the $$$ i $$$-th member of MaratonUSP can participate in the mashup.
Print a single integer $$$ D $$$, the best day for the contest. If you do not have a valid date, print $$$ -1 $$$.
8 1 9 4 7 8 4 9 9
4
4 1 2 3 3
-1
Baledoc recently joined college and is preparing to become the best programmer in the world. At one of the college's events, he made a website using #React, #GraphQL, #Typescript, #Jest, #Golang, #Postgres, #Kafka, #Blockchain, #Machine #Learning, #Docker and #Kubernetes. At the end of the project, he didn't really know what the site was doing, but he was amazed by all the new things he learned and needs to learn #more.
He noticed that the path to being the best programmer in the world starts with learning all languages, so he decided to go to the bookstore and buy all the dictionaries he could find.
Upon arriving home, he noticed that dictionaries are not the best way to learn a new language, but he will not #give #up. Conveniently, given his perseverance, he already understands a few words from each of the languages in the dictionaries he bought.
Every word in the dictionary is defined in terms of other words. Baledoc can understand a new word when it can be defined in terms of words that he already understands, for that, he needs to understand all the words that define it. Help Baledoc find out how many words he can understand in total.
#Submit2Learn #Learn1000000007Submit
The first line of the entry contains an integer $$$ n $$$ ($$$ 1 \leq n \leq 1000 $$$) ─ the number of words that Baledoc already knows. The second line contains the $$$ n $$$ words $$$ k_i $$$ $$$ (1 \leq | k_i | \leq 10) $$$ known by Baledoc, separated by space.
The third line of the entry contains an integer $$$ m $$$ ($$$ 0 \leq m \leq 100 $$$) ─ the number of words in the dictionary. The next $$$ 2m $$$ lines contains information about the dictionary, $$$ 2 $$$ lines for each word.
For each word, the first line contains a string $$$ s $$$ ($$$ 1 \leq | s | \leq 10 $$$) and an integer $$$ k $$$ ($$$ 1 \leq k \leq 10 $$$) ─ the word that is defined in the dictionary and the number of words used in its definition, respectively. The second line contains the $$$ k $$$ words $$$ s_i $$$ ($$$ 1 \leq | s_i | \leq 10 $$$) used to define $$$ s $$$, separated by space.
All words in the entry have only lower case letters from $$$ a $$$ to $$$ z $$$.
A single integer, the amount of words Baledoc can understand in total.
9 you one more of a or cat have than 3 two 4 one more than one cats 6 two or more of a cat i 1 you
12
3 a b d 3 abacaba 3 aba c aba abadaba 3 aba d aba aba 3 a b a
5
For the first case, Baledoc initially understands 9 words ("you", "one", "more", "of", "a", "or", "cat", "have", "than") and succeeds understand all the words in the dictionary. He understands "two" and "i" because he understands all the necessary words, and now that he understands "two", he can understand "cats", which uses "two" in his definition.
Morete is a student of Molecular Sciences who has dedicated himself a lot to the Maratona, participating in many Codeforces contests. These contests are tests with an approximate duration of 2 hours in which the participant has to solve a certain amount of problems, winning or losing rating (score on the platform) depending on his performance.
At the end of each contest, Morete writes on a card how much he gained or lost in rating, and then he places this card on top of a pile, forming a stack with his cards. Morete does this to control his performance.
Thiago, his archenemy, jealous of Morete's dedication, decides to hinder him and for that, inserts a single card with any number, somewhere in the stack of rating cards. At the end of the month, when Morete decides to analyze his performance, he notes that, at some point, he had a negative rating balance, which left him confused, because from what he remembers, he always had a non-negative rating balance.
Your task is to help Morete to find out which cards are suspected to have been inserted in the pile by Thiago, or to say if Morete got stoned and made a mistake.
For example, let $$$ [500, -100, -400, 100, -500, 200] $$$ be the numbers written on the cards in the stack with Morete's ratings after Thiago has inserted his card, where the number at the beginning of the list is in the bottom of the stack, and the one at the bottom on top. So, the suspect cards would be the ones with values $$$-400$$$ and $$$-500$$$ (indices $$$3$$$ and $$$5$$$, respectively), since either of them, if ignored, makes Morete always have a non-negative rating.
The first line contains an integer $$$N$$$ $$$(2 \leq N \leq 10^5)$$$ ─ the number of cards in the stack, after Thiago has inserted his.
The second line contains $$$ N $$$ integers ─ where $$$ r_i $$$ $$$ (-10^9 \leq r_i \leq 10^9)$$$ is the value of the $$$ i $$$-th card in the stack.
If at any time Morete has a negative balance, print "morete chapou: errou conta" (without quotes).
If there is not at least one card, which if ignored, Morete will always have a non-negative balance, print "morete chapou: ficou com saldo negativo" (without quotes).
Otherwise, on the first line, print $$$ k $$$ ─ the number of suspicious cards. On the second line, print $$$ k $$$ integers ─ the positions of these cards in the stack, indexed from 1 and in any order.
6 500 -100 -400 100 -500 200
2 3 5
4 200 -180 20 80
morete chapou: errou conta!
7 1100 -700 60 -700 200 -700 2000
morete chapou: ficou com saldo negativo!
The students from IME-USP are obsessed with games, a very popular game among the students is the blue dot game. In this game, $$$n$$$ students form a circle such that each student can see the other $$$n - 1$$$ students, and each student has a blue or brown dot painted on their forehead. The objective of the game is to find out which students have a blue dot on the forehead, but, initially, nobody knows the color painted on its own forehead. The game works with turns, when a student discovers the answer he leaves the circle at the end of the turn, the game ends when all students leave the circle.
In this version of the game, it is always guaranteed that at least one student has a blue dot on his forehead.
This time the students started the game just before class! The professors do not want to interrupt the game because it is an important tradition, however, they want to know how many turns the game is going to last. Keep in mind that the students from IME-USP are very smart and always finish the game as fast as possible.
The first line contains one integer $$$n\ (1 \leq n \leq 2*10^5)$$$, the number of students.
The second line contains $$$n$$$ integers $$$a_1, \dots, a_n\ (a_i \in \{0, 1\})$$$ such that if $$$a_i = 0$$$ then the student has a brown dot and $$$a_i = 1$$$ if the student has a blue dot. It is guaranteed that at least one student has a blue dot.
A single integer, the number of turns the game is going to last.
1 1
1
2 0 1
2
The Cidade Universitária is an amazing place, with lots of trees, an Olympic streak, and, most importantly, capybaras. In addition, the campus has an extensive area, with more than $$$ 3700000m^2 $$$. To facilitate students' mobility, USP has a fleet of Circular buses, which are responsible for taking students across the campus.
Today, Nathan woke up very happy and decided to bring joy to his fellow students. Naturally, he decided to tell jokes in the Circular. Nathan understands that, in order for the person to get out of the circular happily, it cannot hear a joke more than once. In addition, there must be an interval of 5 minutes between one joke and another.
As Nathan is very friendly with the driver, he got a list with $$$N$$$ pairs $$$(e_i, s_i)$$$, the arrival and departure time of the $$$i$$$-th passenger. Note that multiple passengers can enter or leave at any given time. Furthermore, as students are almost always late, if Nathan tells a joke at the same time a passenger is leaving, that passenger will not hear the joke, however, if Nathan tells a joke at the same time someone is entering the bus, that person will hear the joke.
Due to the inherently gossipy character of college students, people who are in the Circular at the same time can share the jokes they have heard, and Nathan also wants to take that into account. Similarly, a person who is leaving cannot share a joke with a person who is entering the Circular at the same time.
To simplify things, let's assume that Nathan told his first joke at the instant $$$ t = 0 $$$, the second at $$$ t = 5 $$$, the third at $$$ t = 10 $$$, and so on. In addition, as the university does not make a point of respecting traffic laws, an unlimited number of passengers may be on the Circular at any given time. Since the Circular takes exactly 100 minutes to complete its journey, it is guaranteed that no passenger will stay in it for more than 100 minutes, except Nathan, as he is determined in his task.
With the list of the arrival and departure times of the passengers in hand, Nathan wants to prepare his repertoire of jokes. However, preparing the jokes takes time, and he doesn't want to spend more time than necessary, so he asked for your help in finding the minimum number of jokes he needs to prepare for his goal to be achieved.
The first line contains an integer $$$ N $$$ $$$ (1 \leq N \leq 10 ^ 5) $$$ ─ the number of passengers in the Circular.
Following are $$$ N $$$ lines with two integers, $$$ e_i $$$ and $$$ s_i $$$ $$$ (0 \leq e_i \lt s_i \leq 10^9), (1 \leq s_i - e_i \leq 100) $$$ ─ the entry time and departure time of the $$$ i $$$-th passenger.
Print a single integer - the minimum amount of jokes Nathan needs to prepare for his repertoire.
4 2 7 8 13 6 9 21 25
2
After much insistence on the part of his friends, Raphael "Raphael with 'ph'" Ribeiro finally bought the Mintendo Troca-Troca version of the iconic Mario Kart, an unconventional racing game. In it, competitors go through tracks in different scenarios in the Mintendo world, accumulating points depending on their placement. The first place would receive $$$ 15 $$$ points, the second $$$ 12 $$$, the third $$$ 10 $$$, the fourth $$$ 9 $$$, and so on until the twelfth place, which receives $$$ 1 $$$ point.
After a lot of training, Raphael realized that not only did he manage to win all the races, but he was also able to stay in whatever position he wanted. Upon discovering Raphael's abilities, Noronha, a Mario Kart expert, soon became interested in launching a challenge for him. Given a $$$ N $$$ score, if Raphael managed to hit it in as few races as possible on Mario Kart, then Noronha would award $$$ N $$$ moneys to Raphael. If that didn't happen, then it would be Raphael who would be in a $$$ N $$$ moneys debt with Noronha.
Even though he is confident of his abilities, Raphael does not want to stand a chance of losing his money, so he asked for your help! Write a program that discovers a sequence of placements that he must reach in Mario Kart to get exactly $$$ N $$$ points so that it is as small as possible!
A single integer $$$ N $$$ $$$ (1 \leq N \leq 10^6) $$$ ─ the sum of points that Raphael wants to achieve.
The first line must contain a single integer $$$ S $$$ ─ the size of the smallest sequence of placements in order for Raphael to get exactly $$$ N $$$ points.
The second must contain $$$ S $$$ integers $$$ p_i $$$ $$$ (1 \leq p_i \leq 12) $$$ ─ the position Raphael must reach in the $$$ i $$$-th race, in any order.
28
3 1 2 12
11
2 3 12
100
7 1 1 1 1 1 1 3
In addition to participating in the Maratona and playing Softball, Raphael also has another hobby: singing. As he is very eclectic and his style is always changing, he releases new albums almost every year, with genres ranging from Indie, Rock, Electronic, Rap, and others.
However, Raphael is not very creative in naming his albums. As he has a birthday on the 1st of January, he decided that every album released would be titled his age that year.
Some fans, unhappy that Raphael was so young on an album cover, decided to investigate whether Raphael had lied his age in any of the titles. In other words, given the year of release for each album and its respective title, fans decided to investigate whether age was consistent across all of them.
As this task is very difficult, the fans decided to ask for his help. Please help them in this essential task.
The first line contains an integer $$$N$$$ $$$(1 \leq N \leq 100)$$$ ─ the number of albums released by Raphael.
Each of the next $$$ N $$$ lines contains a pair of integers $$$ a_i $$$ and $$$ t_i $$$ $$$ (1900 \leq a_i \leq 2021) $$$ $$$ (0 \leq t_i \leq 200) $$$ ─ the year and title of the $$$ i$$$-th album released.
If Raphael has lied his age on an album, print "mentiu a idade" (without quotes). Otherwise, print "idades corretas" (without quotes).
5 2020 28 2000 8 2003 11 2001 9 2015 23
idades corretas
3 2000 15 1998 11 2010 25
mentiu a idade