Trojack is mapping the genetic diversity of Araucaria trees along an ecological hike that symbolically stretches from Foz do Iguaçu to Curitiba. He collected samples from $$$N$$$ trees in sequence and assigned each one a genetic identifier.
His research seeks to find sections of the trail that are genetically rich. A section is considered "viable for study" if, within it, all of the trees with a genetic marker are unique.
Your task is to help Trojack find the length of the longest continuous section of trees that is "viable for study".
The first line contains an integer $$$N$$$ ($$$1 \leq N \leq 2 \times 10^{5}$$$), the number of trees.
The second line contains $$$N$$$ integers $$$a_1, a_2,\ldots,a_N$$$, where each $$$a_i$$$ ($$$1 \le a_i \le 10^{9}$$$) is the genetic identifier of each tree in the hike.
Output a single integer, the length of the longest viable section.
51 1 3 4 5
4
81 2 1 3 2 7 4 2
5
The Binarical Garden is a famous tourist attraction in Curitibyte, known mainly for its greenhouse containing countless specimens of plants from Brazil and even other countries.
However, few tourists know that behind the greenhouse there is a gigantic garden of binary flowers positioned side by side. A binary flower located in the $$$i$$$-th position is so called because its number of petals is equal to the number of ones in the binary representation of $$$i$$$.
Dona Francisca is a curious tourist who is currently at position $$$L$$$ in the garden and wants to walk to position $$$R$$$ in order to find the largest number of petals on a binary flower in that part of the garden, including $$$L$$$ and $$$R$$$. Help Dona Francisca find this value.
The input consists of a single line containing two integers $$$L$$$ and $$$R$$$ ($$$1 \leq L \le R \leq 10^{18}$$$), the range of the garden that Dona Francisca will walk.
The output should contain only a single integer, the largest number of petals in the given range.
7 15
4
1 1000000000
29
Yuri Alberto, the people's favorite and Corinthians' star number 9, will be in Curitiba on August 27 to face Athletico Paranaense in the quarterfinals of the Copa do Brasil. Obviously, his victory is already a sure thing because there's no way a small team like CAP can beat the biggest team in the world!
Therefore, Yuri and his adventurous spirit have already planned to take a tour of the state of Paraná after his victory. He is truly worthy of the title of protagonist, as in addition to playing very well, he also dominates a great deal of knowledge about archaeology and rock runes. Because of this, the tour he chose to take was to enter a cave filled with enigmatic runes dating back more than 4000 years, with a legend of a cursed treasure waiting for some star of knowledge to rescue it.
Upon entering the cave, Yuri discovered that the runes are organized into $$$N$$$ panels, each containing a sequence of ancient numbers. A legend carved on the wall reveals:
To unlock the secret of the cursed treasure, the seeker must first purify each panel, maximizing the common essence of each sequence. The seeker may remove one of the runes from the sequence if desired to maximize the common essence of a sequence. Once the panels are purified, gather all the essences obtained. The destination of the treasure will be the smallest possible harmonious multiple of the gathered essences, and it is possible to remove one of the essences (if more than one exists) to minimize the harmonious multiple.
The common essence of a set is defined as the largest number that is a factor of all numbers, better known as the greatest common divisor (GCD). The harmonious multiple of a set is defined as the smallest integer that is a multiple of all elements of the set, better known as the least common multiple (LCM).
Yuri Alberto, with his expertise, knows that the solution to this puzzle requires precision and efficiency, as the runes can be numerous and the treasure will not wait. He has asked for your help in developing a program that will find the value of the cave's puzzle.
The first line contains an integer $$$N$$$ ($$$1 \leq N \leq 10^{5}$$$), the number of panels. This is followed by $$$N$$$ lines, each representing a panel. For each panel, an integer $$$A$$$ ($$$2 \leq A \leq 10^{5}$$$) is first given, representing the number of runes on that panel, followed by $$$A$$$ positive integers $$$v_j$$$ ($$$1 \leq v_j \leq 42$$$), representing the values of the runes. The sum of all $$$A$$$ does not exceed $$$2 \times 10^{5}$$$.
A single integer, the value of the cave riddle after following the ritual described. It is guaranteed that this value does not exceed $$$10^{18}$$$.
33 12 24 302 8 63 4 6 8
8
44 32 35 42 152 35 402 24 123 24 11 7
24
Explanation for example 1
Collecting the essences: $$$[12,8,4]$$$. Removing $$$12$$$, we have $$$\mathrm{LCM}(8,4) = 8$$$, which is the smallest possible value. Therefore, the final result is $$$8$$$.
Amós, Carlos, and Eduarda like to have movie nights at Carlos's house. On these movie nights, Carlos invites his $$$M$$$ friends (including Amós and Eduarda, since Carlos is the owner of the house). For the session, they need to choose which movies to watch from a collection of $$$N$$$ available titles. The selection can contain any number of movies, including none.
Each of the $$$N$$$ friends has two opinions about the available movies. The opinions are of the type "movie $$$i$$$ is good" or "movie $$$i$$$ is bad." Your task is to choose a set of movies to watch so that at least one of each friend's two opinions is satisfied.
An opinion is satisfied if a movie that the friend considers "good" is included in the selection, or if a movie that the friend considers "bad" is left out.
The first line of input contains the integers $$$N$$$ ($$$2 \leq N \leq 10^{5}$$$) and $$$M$$$ ($$$2 \leq M \leq 10^{5}$$$), the number of friends and the number of movies, respectively.
The following $$$N$$$ lines of input contain the friends' suggestions. Each line contains two opinions, where each opinion has the form "S $$$i$$$" (movie $$$i$$$ is good) or "N $$$i$$$" (movie $$$i$$$ is bad), where $$$i$$$ is an integer with $$$1 \le i \le M$$$.
Print a line with $$$M$$$ letters, for each movie "S" if it is included and "N" if it is not. If there are multiple solutions, print any one of them.
If there is no solution, print "IMPOSSIVEL".
3 5S 1 S 2N 1 S 3S 4 N 2
N S S S N
2 6N 3 S 6N 6 S 3
N N N N N N
4 2N 1 S 2N 2 S 1N 1 N 1S 2 S 2
IMPOSSIVEL
Ebert is the best student in Linear Algebra VII in his class, so his mathematical knowledge is quite extensive. As a result, after a mind-boggling test on the subject, several students asked him how he had answered a certain question on the test. This question involved planes in a 4-dimensional space, and Ebert, with all his wisdom, explained that the intersection of two planes in $$$\mathbb{R}^4$$$ can be a single point. "It's too trivial to notice that!" exclaimed Ebert, demonstrating the planes with his own hands.
Now, several students started asking Ebert for help, but they were so annoying that he decided he didn't want to waste any more time on it. But, since he's a nice guy, he decided to ask you to write a program that would solve the problem for him, so he could just run the program. Help Ebert find the coordinates of the intersections!
The first line of input consists of an integer $$$T$$$ ($$$1 \leq T \leq 10^{4}$$$), the number of test cases. Each test case has six lines, each containing four integers $$$X_i, Y_i, Z_i$$$ and $$$W_i$$$ ($$$-10000 \leq X_i, Y_i, Z_i, W_i \leq 10000$$$).
The first line of each test case represents the displacement vector $$$A = (X_1, Y_1, Z_1, W_1)$$$. The second and third lines represent the direction vectors $$$B = (X_2, Y_2, Z_2, W_2)$$$ and $$$C = (X_3, Y_3, Z_3, W_3)$$$, respectively.
The fourth line represents the displacement vector $$$D = (X_4, Y_4, Z_4, W_4)$$$. The fifth and sixth lines represent the direction vectors $$$E = (X_5, Y_5, Z_5, W_5)$$$ and $$$F = (X_6, Y_6, Z_6, W_6)$$$, respectively.
The first plane is defined by $$$A + u_1B + v_1C$$$, where $$$u_1$$$ and $$$v_1$$$ are real numbers. The second plane is defined by $$$D + u_2E + v_2F$$$, where $$$u_2$$$ and $$$v_2$$$ are real numbers.
It is guaranteed that the planes are not degenerate, i.e., the pairs $$$B$$$ and $$$C$$$ and $$$E$$$ and $$$F$$$ are linearly independent.
For each test case, if there is a unique intersection between the two planes, print a line containing four real numbers representing the values $$$u_1, v_1, u_2, v_2$$$. Otherwise, print only the value $$$-1$$$.
Your answer will be considered correct if the absolute or relative error is less than $$$10^{-6}$$$. That is, if your answer is $$$a$$$ and the correct answer is $$$b$$$, then the judge will accept your answer if $$$|a - b| \leq 10^{-6} \cdot \max(1, |b|)$$$.
10 0 0 01 0 0 00 1 0 00 0 0 00 0 1 00 0 0 1
0.000000000000000 0.000000000000000 0.000000000000000 0.000000000000000
24 9 2 00 9 4 22 8 1 28 7 4 91 0 0 05 8 2 15 5 5 51 4 2 73 7 6 24 8 3 07 4 14 72 4 4 9
4.476190476190476 5.333333333333333 46.428571428571429 -10.619047619047619 -1
At the end of the big Unioeste Programming Marathon, euphoria took over the room. To capture the iconic moment, all the competitors threw their badges in the air in celebration. João, the event's Social Media Wizard, captured a spectacular photo of that moment.
Now, João needs to post this photo on Instagram, but the original image is too wide, full of empty spaces that diminish the visual impact. He wants to make a rectangular cut aligned with the axes that perfectly frames all the badges. To create a visually powerful and minimalist composition, he needs this frame to be the smallest rectangle possible that still contains all the badges.
Being a perfectionist, but also... "computationally efficient" (not to say lazy), João decided to turn his task into one last challenge. He used software to identify the coordinates of the center of each badge in the photo. Now, he asks for your help, as one of the brilliant coders, to create a program that determines the exact coordinates of the four corners of the "perfect frame."
The first line of input will contain an integer $$$N$$$ ($$$1 \le N \le 10^{6}$$$), the number of badges in the photo. The next $$$N$$$ lines will contain two integers each, $$$x_i$$$ $$$y_i$$$ ($$$-10000 \le x_i, y_i \le 10000$$$), the coordinates of each badge in the photo.
Your program should print four lines. Each line should contain the $$$x$$$ and $$$y$$$ coordinates of one of the vertices of the smallest rectangle, separated by a space. The vertices can be printed in any order.
54 5-1 28 -32 9-4 0
-4 -3 8 -3 8 9 -4 9
4-3 510 50 510 5
-3 5 10 5 10 5 -3 5
Ana, a great tourist, decided to take advantage of the border between Foz do Iguaçu and Ciudad Del Este and go shopping in Paraguay. She has a list of $$$N$$$ products she would like to bring back. However, when crossing the Friendship Bridge, there is a risk of being stopped by the Federal Revenue Service. To minimize this risk, Ana imposes two restrictions on what she will bring with her:
The first line of the input contains three integers: $$$N$$$ ($$$2 \leq N \leq 20$$$), $$$M$$$ ($$$0 \leq M \leq N(N-1)/2$$$), and $$$K$$$ ($$$1 \leq K \leq 10^{18}$$$), the number of products, the number of forbidden pairs, and the maximum limit.
The second line of input contains $$$N$$$ numbers $$$a_1, a_2, ..., a_N$$$, the price of the $$$i$$$-th product ($$$1 \leq a_i \leq 10^{18}$$$).
The next $$$M$$$ lines are distinct and each contain a pair of numbers $$$i$$$ and $$$j$$$ ($$$1 \leq i \lt j \leq N)$$$, representing the indices of the products that have a higher risk of being stopped if taken together.
Output the number of product subsets that Ana can choose from that meet the constraints.
4 1 1001 2 3 41 2
12
4 1 81 2 3 41 2
11
Nikolas was intrigued by the name of Unioeste: State University of Western Paraná. According to his reasoning, why specify that the university is in the "West" (oeste in Portuguese) of Paraná, if there is no State University of "Eastern" (leste in Portuguese) Paraná? To correct this geographical injustice, he decided to found Unilestep (State University of Eastern Paraná).
However, the master plan for cities in the east includes some rules that must be followed:
For example, for $$$L = 2$$$ and $$$R = 5$$$:
To help Nikolas choose the ideal plot of land to build Unilestep, write a program that, given the values of $$$L$$$ and $$$R$$$, reports how many distinct plots of land he can use. A plot of land is considered distinct from another only if its area is different.
The first line of the input contains the integer $$$T$$$ $$$(1 \leq T \leq 10^{3})$$$, the number of test cases. This is followed by $$$T$$$ lines, each line being a test case containing two integers $$$L$$$ and $$$R$$$ ($$$1 \leq L \leq R \leq 17$$$).
For each test case, your program should output a line containing an integer: the number of different plots of land that Nikolas can use, given the values of $$$L$$$ and $$$R$$$ provided.
12 3
28
29 1210 17
990000 316196144
Thiago is a tourist exploring the wonderful city of Curitiba, in Paraná, famous for its beauty (and cold weather). The map of the region can be represented by $$$N$$$ locations and $$$M$$$ roads connecting them. Each road has an associated travel time, in minutes.
Thiago wants to visit $$$P$$$ tourist attractions, which are the first $$$P$$$ locations on his map, such as the Botanical Garden, the Oscar Niemeyer Museum, and the huge UFPR. For each of these attractions, he has assigned a value of "happiness" that he would feel when visiting them for the first time.
Unfortunately, his time is short. He has only one day for his tour, which starts at 8:00 a.m. at his hotel (located at location $$$N$$$) and must end before midnight (12:00 a.m.). The time to visit each location depends on the tourist attraction to be visited. He can visit the tourist attractions in any order he wants and does not need to return to the hotel.
As a close friend of Thiago's and a skilled programmer, you have decided to assist him. Your task is to develop a program that determines the optimal route for Thiago, that is, the maximum sum of happiness from the locations visited without exceeding the time limit.
The first line of the input contains four integers: the number of locations $$$N$$$ ($$$2 \le N \le 2 \times 10^{5}$$$), the number of roads $$$M$$$ ($$$N-1 \le M \le 2 \times 10^{5}$$$), and the number of tourist attractions $$$P$$$ ($$$1 \le P \le 20$$$). It is guaranteed that the graph is connected and that $$$P \lt N$$$.
The next $$$M$$$ lines describe the roads in the city. Each line contains three integers $$$u$$$, $$$v$$$, and $$$w$$$, where $$$u$$$ and $$$v$$$ ($$$1 \le u,v \le N$$$) represent the locations connected by the road, and $$$w$$$ ($$$1 \le w \le 180$$$) represents the travel time in minutes. The roads are two-way, and there are no repeated roads or roads with $$$u = v$$$ in the input.
The next line contains $$$P$$$ distinct integers $$$f_1, f_2,\ldots,f_P$$$ where each $$$f_i$$$ ($$$1 \le f_i \le 10^5$$$) represents the happiness Thiago gets from visiting tourist spot $$$i$$$ for the first time.
The last line of the input contains $$$P$$$ integers $$$t_1, t_2,\ldots,t_p$$$ where $$$t_i$$$ ($$$1 \le t_i \le 120$$$) represents the time spent, in minutes, at tourist attraction $$$i$$$.
Output a single integer, the maximum amount of happiness that Thiago can achieve.
4 3 24 1 1001 3 1503 2 5050 8030 40
130
8 10 48 6 1206 1 1501 2 1002 3 1703 4 1804 7 907 5 1106 4 1601 7 1708 5 130100 60 70 80120 60 80 40
250
5 4 35 4 1705 1 1704 2 1702 3 100160 120 110120 120 120
280
Andrade, Cosenza, and Ebert are in the middle of a lecture, and they are obviously bored. To pass the time, they decide to play a game on a tree. Andrade generates a tree with $$$N$$$ nodes, with node 1 being the root, and each edge has a weight $$$w$$$. Then, Cosenza and Ebert choose two nodes $$$u$$$ and $$$v$$$ from the tree, and the game consists of calculating the sum of the weights of the edges on the path from the root to $$$u$$$ and the sum of the weights of the edges on the path from the root to $$$v$$$. The sum of the weights is calculated modulo $$$10^{5}$$$. Then, the exclusive OR (xor) between the two sums is calculated bit by bit, and the result is the value of the game for that pair of nodes.
They repeat this process several times, choosing different pairs of nodes, and want to know the different results they can obtain.
The first line of the input contains an integer $$$N$$$ $$$(2 \leq N \leq 10^{5})$$$, the number of nodes in the tree. The next $$$N - 1$$$ lines contain three integers $$$u$$$, $$$v$$$, and $$$w$$$ $$$(1 \leq u, v \leq N; 0 \leq w \leq 10^{9})$$$, indicating that there is an edge between nodes $$$u$$$ and $$$v$$$ with weight $$$w$$$.
The first line of the output contains an integer $$$M$$$, the number of distinct possible outcomes of the game. The second line contains $$$M$$$ distinct integers, representing the possible outcomes, in ascending order.
61 2 41 3 22 4 33 6 103 5 94
16 0 2 3 4 5 6 7 8 11 12 14 96 98 100 103 108
21 2 998244353
2 0 44353
Pinhão is a new social network that is becoming a craze on the internet. On it, users can interact, send messages, and share posts. The great thing about Pinhão is the formation of "pinhas": automatic groups of people who share common interests. A user can only view and share posts from the pinhas they participate in. In addition to this, when a user posts or shares something, that post becomes visible in all the pinhas they are part of.
Currently, the social network has $$$N$$$ active users. Each person's interest is represented by a string of $$$L$$$ characters. Two users belong to the same pinha if their level of common interest is greater than or equal to a value $$$K$$$. This level of interest is defined as the size of the largest common substring between the strings of interest of the two users.
For example: If user A has the string of interest "acabaa" and user B has "abcccc," the largest common substring between them is "ab." Therefore, the level of common interest is 2. If $$$K\leq2$$$, they will belong to the same cluster.
The administrators of Pinhão have hired you for a study. You will receive the values of $$$L$$$ and $$$K$$$, in addition to the strings of interest of all $$$N$$$ users. Your goal is to find out how many shares, at a minimum, are necessary for a publication by user 1 to be seen by user $$$N$$$.
The first line of the input contains three integers, $$$N$$$ ($$$1 \le N \le 5 \times 10^{4}$$$), the number of users on the social network, $$$L$$$, the size of the strings of interest, and $$$K$$$ ($$$1 \le K \le L \le 20$$$), the minimum level of common interest for two users to participate in the same cluster. This is followed by $$$N$$$ lines, each containing a string consisting only of lowercase letters of size $$$L$$$, where line $$$i$$$ represents the interests of the $$$i$$$-th user.
The output should be a single integer: the minimum number of shares required for a post by user 1 to be visible to user $$$N$$$, or -1 if this is not possible.
3 4 2abcdabebzzeb
1
3 4 4zzzzaaaaaaaa
-1
Explanation for example 1
Users 1 and 2 are part of one cluster, and users 2 and 3 are part of another cluster. Thus, a post by user 1 must be shared by user 2 to be visible to user 3.
Explanation for example 2
User 1 is isolated in their own cluster, so it is impossible for them to reach user $$$N$$$.
Paulinha is training for the SBC Programming Marathon and has a clear goal: to advance to the national stage, which will be held in the Liberdade neighborhood of São Paulo. She knows that to do so, she needs to solve at least $$$K$$$ problems.
Paulinha is extremely intelligent and can solve any problem, regardless of the topic, but there is one small problem: Paulinha simply hates graph questions.
Your task is to help Paulinha figure out the minimum number of graph problems she needs to solve to reach her goal.
The first line consists of integers $$$N$$$ ($$$1 \le N \le 10^5$$$), representing the total number of topics, the minimum number of problems $$$K$$$ ($$$1 \le K \le \sum_{i=1}^{N} a_i$$$) that Paulinha needs to solve to pass the stage, and an integer $$$G$$$ ($$$1 \le G \le N$$$), the index corresponding to the graph problems.
The second line contains $$$N$$$ integers, $$$a_1, a_2, \dots, a_{N}$$$, where $$$a_i$$$ ($$$1 \le a_i \le 1000$$$) represents the number of questions available for topic $$$i$$$.
Output a single integer, the minimum number of graph questions that Paulinha needs to solve to pass the level.
3 5 33 1 2
1
5 7 21 2 2 3 1
0
An ancient legend from Foz do Iguaçu tells of a rare mirage that forms in the Devil's Throat: for a single, fleeting moment, a horizontal trail of barrels appears in the middle of the water curtain. Maria, a fearless acrobat, is determined to become the first to cross this trail before it disappears.
For the crossing, the waterfall is modeled as a line of $$$N$$$ positions for barrels, numbered from $$$0$$$ to $$$N-1$$$. Maria starts from the shore at position $$$-1$$$ and her goal is to reach the opposite shore at position $$$N$$$. Her jumping ability is $$$K$$$, which means she can jump from a foothold $$$i$$$ to a barrel $$$j$$$ if $$$(j-i) \le K$$$. Naturally, she can only land on barrels that are available in the mirage.
The biggest challenge is the chaotic nature of the waterfall, which changes the configuration of the barrels. Your task is to analyze $$$Q$$$ of these events and determine, for the initial configuration and after each change, whether Maria can cross the waterfall.
The first line of the input contains three integers separated by spaces: $$$N$$$, $$$Q$$$, and $$$K$$$ ($$$1 \le N, Q \le 2 \times 10^{5}$$$, $$$1 \le K \le 10^{9}$$$), representing the number of barrels, the number of events, and Maria's jumping ability, respectively. The second line contains $$$N$$$ integers, $$$a_1, a_2, \ldots, a_{N}$$$, where $$$a_i = 1$$$ if the $$$i$$$-th barrel is initially usable, and $$$a_i = 0$$$ if it is broken.
The next $$$Q$$$ lines describe the events. Each line contains three integers $$$T$$$ ($$$1 \le T \le 2$$$), $$$L$$$ and $$$R$$$ ($$$1 \le L \le R \le N$$$).
The output should contain $$$Q+1$$$ lines, representing the answer for the initial state and all subsequent states. For each answer, print "SIM" if the traversal is possible, and "NAO" otherwise.
10 3 4 1 1 0 0 0 0 0 0 1 1 1 5 6 2 5 6 1 1 10
NAO SIM NAO SIM
8 2 3 0 0 1 0 0 1 0 0 2 6 6 1 6 7
SIM NAO SIM
Everyone knows that the hardest part of organizing a programming marathon is choosing a name. You and your MarathonFriends are organizing a mini programming marathon and are discussing which name to choose!
After much thought, you are torn between two names: Cataratas do Pinhão and Pinhão das Cataratas. Obviously, a vote will be held to decide the winning name. Each MarathonFriend will write 1 (Cataratas do Pinhão) or 2 (Pinhão das Cataratas) on a piece of paper.
There will be many votes, so many votes that you will need many hands to count them! Unfortunately, you only have two hands =c. That is why you decide to write a program that counts all the votes and decides the winning name.
The first line of input contains an integer $$$N$$$ ($$$11 \leq N \leq 10^{5}$$$), the number of votes received.
The second line of input contains $$$N$$$ numbers $$$a_1, a_2, \ldots, a_N$$$, the vote of the $$$i$$$-th MaratonAmigo.
Output the winning name. In case of a tie, print "Cascatiba?"
121 1 1 1 1 1 2 2 2 2 2 2
Cascatiba?
121 1 1 1 1 1 1 2 2 2 2 2
Cataratas do Pinhao
121 1 1 1 1 2 2 2 2 2 2 2
Pinhao das Cataratas