The Autonomous Municipal Government of Cochabamba has decided to build a park around the Alalay Lagoon. El Soto, after working for 2 years on a cargo ship, has decided to work for the municipality. He studied physics, but they made him pass as a civil engineer since El Soto can handle everything. El Soto provided a list of points to Samir, the geometry manager of the municipality. El Soto claimed that the supposed list of points is ordered counterclockwise and that it forms the convex hull enclosing the lagoon. El Soto also claims that this convex hull would be a good boundary for the park according to mathematical calculations that El Soto is capable of doing in his head and that you wouldn't understand.
The convex hull is defined as the smallest convex polygon that can enclose a set of points in the plane.
Samir looks at him doubtfully and discovers that El Soto was mistaken, but not entirely; the coordinates are correct, but their order is not. He realizes that by swapping two coordinates, he can fix the plan and obtain a counterclockwise convex hull. Help El Soto and Samir figure out which coordinates to swap.
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) representing the number of test cases.
For each test case, the first line contains an integer $$$n$$$ ($$$4 \leq n \leq 10^5$$$) representing the number of points in the order that El Soto provided to Samir.
The following $$$n$$$ lines each contain two integers $$$x_i$$$ and $$$y_i$$$ ($$$-10^9 \leq x_i, y_i \leq 10^9$$$) representing the coordinates of the points.
It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$10^5$$$, that in each test case there are no three collinear points, and that for each test case there is always a unique solution.
For each test case, print two integers $$$i$$$, $$$j$$$ $$$(i \lt j)$$$, the indices of the coordinates that need to be swapped to obtain a correctly ordered convex hull.
240 01 11 00 151 04 33 02 50 2
2 3 2 3
In the Tunari Park, there is a magical tree with fruits that grow at each node, including the root. Every night, each fruit produces one milliliter of magical juice and the fruit moves one node closer to the root. The fruit is harvested exactly after it has produced magical juice at the root of the tree. The root is node 1. A tree is a connected graph that contains no cycles.
Mr. Pozo, Armando's teacher, is a master of mystical arts. Pozo has such great mastery over magical trees that he can choose which node will be the root.
The goal is to determine the maximum amount of milliliters of magical juice that can be obtained by choosing the optimal node as the root. Mr. Pozo already knows the answer, but if you manage to find the answer, he will reward you with "Api con Pastel" (a delicious bolivian breakfast).
An integer $$$n$$$ representing the number of nodes, $$$2 \leq n \leq 10^5$$$. Then, $$$n-1$$$ pairs of numbers $$$a_i, b_i$$$ ($$$1 \leq a_i, b_i \leq n$$$) representing the connections between the nodes. It is guaranteed that there is a simple path between each pair of nodes. Then, $$$n$$$ numbers $$$f_i$$$ ($$$1 \leq f_i \leq 10^5$$$) representing the number of fruits at each node.
An integer representing the maximum amount of milliliters of magical juice that can be obtained by choosing the optimal node as the root.
21 21 2
5
21 22 1
5
41 21 33 42 3 2 1
23
You have proven that you are a sigma, but you still do not have your sigma badge. You decide to climb the steps of the Christ of Discord. At the top, the supreme sigma shows you a list $$$a$$$, composed of $$$n$$$ numbers. He tells you that if you answer his $$$q$$$ questions correctly, you will earn the sigma badge. Each question provides you with two numbers $$$l$$$ and $$$r$$$, which represent a range of the list of numbers. You have to respond with the sigma function of the product of the numbers that appear in the range.
The sigma function is defined as the sum of all divisors of a number including the number itself:
For example, $$$\sigma(6) = 12$$$ because the divisors of $$$6$$$ are: $$$1, 2, 3, 6$$$.
The list of numbers $$$a$$$ is represented as $$$a_1, a_2, a_3, \ldots, a_n$$$ and the range consists of $$$a_l, a_{l+1}, \ldots, a_r$$$. The answer to a question is $$$\sigma(a_l*a_{l+1}*\ldots*a_r)$$$, which is the sigma function applied to the product of the numbers in the range.
Now, to obtain your sigma badge and be recognized internationally, you must answer the $$$q$$$ questions correctly.
The input consists of two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n, q \leq 10^4$$$), followed by $$$n$$$ integers, the list $$$a$$$ ($$$1 \leq a_i \leq 10^5$$$). Then, there are $$$q$$$ lines representing the questions, each with two integers $$$l$$$ and $$$r$$$ ($$$1 \leq l \leq r \leq n$$$).
You must print $$$q$$$ numbers, the answer to each question. Since the number can be very large, respond with each of the results modulo $$$10^9 + 7$$$.
10 51 2 3 4 5 6 7 8 9 101 110 101 101 37 10
1 18 15334088 12 19344
In the year 2888, thanks to the teleporters invented by the team "Que No Perdió" in the competition "Cocha Somos Innovación" of the year 2882, Bolivia has conquered the world and Cochabamba is its capital.
Now, for this year's competition, programmers from all over the world will come, but we are interested in knowing how many do not represent any of the 9 original departments from the 21st century, which are:
Each team represents a department according to its abbreviation. There may be multiple teams representing the departments. Now, the countries that were annexed to Bolivia count as additional departments. Count how many teams come from what used to be called abroad.
The first line contains an integer $$$n$$$ ($$$3 \leq n \leq 100$$$) representing the number of teams. The following $$$n$$$ lines each contain a character string of minimum length 2 and maximum length 4, representing the abbreviations of the departments, using lowercase letters from the English alphabet.
Print an integer representing the number of teams that represent departments that are not part of the original 9.
6argcbbachllpcbbacol
3
3permexcccp
3
We all know that The Pachorverse has infinite timelines; but this problem takes us to the Mr-137 universe, not C-137. In this competitive programming universe, there are many characters that contribute to the main story, including the legendary teams Spokies and QuePerdio.
Our old friend Steven, from the Mr-137 universe, will give us some advice to navigate this chaotic universe. Remember: it doesn't matter where you start learning, as long as you are consistent, you will eventually find an optimal training strategy in competitive programming.
Steven, being self-taught, reads random tutorials from Codeforces. It takes him between one and two months to learn advanced techniques. Over the years, he understood that there are problems that, no matter how hard you try, will force you to give up and explore other areas. Eventually, you will accumulate enough knowledge to face them again. For Steven, learning without the help of others was difficult; that's why he values his mentors who dedicated their time in those days (*).
Steven invites you to solve difficult problems with a rating of +2500 weekly, because the only way to grow is to step out of your comfort zone; it won't be easy, but it won't be impossible either. Time management is crucial; with these problems, one can lose a lot of time without realizing it, so it is advisable to set limits and keep learning.
Steven Ronaldo Tercero has left us another intriguing gift for the competition. This time, your task is to analyze integers under specific conditions related to divisibility.
Given an integer $$$S$$$, an integer $$$N$$$, and a set of $$$K$$$ numbers $$$\{a_1, a_2, \dots, a_K\}$$$, you must count how many numbers less than or equal to $$$N$$$ are divisible by $$$S$$$, but not divisible by any of the numbers in the given set.
The input consists of the following lines:
Print a single integer: the count of numbers less than or equal to $$$N$$$ that meet the described conditions.
3 10 2 2 5
2
In the given example:
For the third time, Pacha invites you to walk through the mountains. You are very scared to go because the last time you went, you got lost on the way back and almost fell off a cliff. But since you are an adrenaline junkie, you decide to go again. Pacha provides you with a map with $$$n$$$ segments, starting from segment $$$1$$$ and ending at segment $$$n$$$, where the height of each segment is indicated. If there is a difference between segments, then you have to exert effort depending on the difference in heights. This time you decide to take your girlfriend with you, and since you are a simp, you decide to carry her backpack for her. So now the climbs require much more effort than before.
The effort between two consecutive segments $$$i$$$ and $$$i+1$$$ is defined as:
You realize that it is very difficult and you feel like crying, but luckily another time traveler appears in front of you. He tells you that in the future, Cochabamba is the most advanced city in the world thanks to the multiple programming contests held every year.
he programmers who participated in the "Cocha, We Are Innovation" contest in 2881 developed a device that, if you are currently on segment $$$i$$$, lets you teleport to the next segment $$$(i + 1)$$$ or the one after the next $$$(i + 2)$$$ without any effort. Being the 3.0 version, it can be used as many times as you want, but once you teleport, you must proceed to the next segment—meaning if you land on segment $$$i$$$, you must still move on to segment $$$i + 1$$$ and exert the required effort, unless you've teleported onto the very last segment.
Now you must calculate the minimum effort you can make if you use the device wisely.
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 2.5 * 10^4$$$) representing the number of test cases.
For each test case, the first line contains an integer $$$n$$$ ($$$4 \leq n \leq 10^5$$$) representing the number of segments. The second line contains $$$n$$$ integers $$$h_i$$$ ($$$1 \leq h_i \leq 10^4$$$) representing the height of each segment.
It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$10^5$$$.
For each test case, an integer representing the minimum effort you can make if you use the teleportation device wisely.
351 2 3 4 571 3 2 5 1 4 241 10 1 1
3 5 0
Global warming is causing massive ice melting in Antarctica, leading to coastal cities being submerged. In Bolivia, as a landlocked country, we are not as concerned about this, as no city is directly affected. For example, Cochabamba is at 2558 meters above sea level, La Paz at 3625 meters, and even Santa Cruz, at 416 meters, is safe. To the west, we have the Andes mountain range with its high peaks, such as Illimani, which rises to 6462 meters. To the east lies the vast Amazon region and Brazil, where nearly 40
Unfortunately, global warming has reached an irreversible point. It is known that starting next year, the sea level will rise 1 meter each year until it reaches $$$10^9$$$ meters. We are all doomed due to our excessive use of plastic soda bottles, pizza boxes, egg cartons, and for leaving the light on all night thinking that our parents would turn it off. Now we want to know how many years each segment of the map has left before being flooded, imagining that the water comes from both the Pacific Ocean (west) and the Atlantic Ocean (east).
To simplify, we will consider Bolivia and the neighboring countries as one-dimensional. A height map will be provided from one coast to the other. It is well known that a straight line between the Atlantic and the Pacific, passing through Cochabamba, is 2880 km long, so that is the limit. Calculate how many years each segment has left before being flooded, assuming that the ocean water is infinite and that once a segment is flooded, its level does not decrease.
The first line contains an integer $$$n$$$ ($$$3 \leq n \leq 2880$$$) representing the number of segments. The first and last segments will always have a height of 0 meters. The second line contains $$$n$$$ integers $$$h_i$$$ ($$$0 \leq h_i \leq 6542$$$) representing the height of each segment in meters.
Print $$$n$$$ numbers, where each number indicates how many years each segment has left before it gets flooded.
50 1 0 2 0
1 2 2 3 1
160 100 1000 3625 6462 4000 2880 2558 1500 416 200 400 100 900 288 0
1 101 1001 3626 6463 4001 2881 2559 1501 901 901 901 901 901 289 1
30 10 0
1 11 1