In basic engineering subjects, we have the calculation of areas between curves. In this case, we will have to calculate the area between a parabola and the x-axis.
For example, consider the parabola $$$x^2-4$$$ over the range $$$[-3, 3]$$$:
In this case, the areas are: $$$$$$ A_1 = \Bigg | \int_{-3}^{-2} (x^2-4) \cdot dx \Bigg | = \frac{7}{3} $$$$$$ $$$$$$ A_2 = \Bigg | \int_{-2}^{2} (x^2-4) \cdot dx \Bigg | = \frac{32}{3} $$$$$$ $$$$$$ A_3 = \Bigg | \int_{2}^{3} (x^2-4) \cdot dx \Bigg | = \frac{7}{3} $$$$$$ Therefore, the requested area will be $$$A_1 + A_2 + A_3 = \displaystyle\frac{46}{3}$$$
Note that there are cases where the function may not intersect the x-axis in the range, such as $$$x^2+4\cdot x -5$$$ in the range $$$[-3,0]$$$
$$$$$$ A = \Bigg | \int_{-3}^{0} (x^2+4\cdot x- 5) \cdot dx \Bigg | = \frac{24}{1} $$$$$$
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 5000$$$), indicating the number of test cases. This is followed by $$$t$$$ lines, one for each test case.
Each test case contains 5 integers $$$A, B, C, L, R$$$ $$$(-10^4 \leq A, B, C, L, R \leq 10^4)$$$ which are the coefficients of the equation $$$A\cdot x^2+B\cdot x+C = 0$$$ and the range $$$[L,R]$$$ where the function is evaluated. It is guaranteed that $$$L \leq R$$$ and that if there is an intersection with the x-axis, these intersections will occur at integer values. Also, $$$A \neq 0$$$.
For each test case, print a line with the requested area in the form $$$p/q$$$ where it is guaranteed that $$$p$$$ and $$$q$$$ are integers such that $$$GCD(p,q)=1$$$.
3 1 0 -4 -3 3 1 0 -4 0 3 1 4 -5 -3 0
46/3 23/3 24/1
A game is being played where the player (you) must guess the number the other player is thinking of. To do this, there is a set of 60 cards that contain an infinite list of numbers; the player who thinks of a number must choose all the cards where their number appears. And, to make the game fair, the number they are thinking of must be positive and less than or equal to $$$10^{18}$$$.
Below is the content of the first 5 cards:
- $$$1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, ...$$$
- $$$2, 3, 6, 7, 10, 11, 14, 15, 18, 19, 22, 23, 26, 27, 30, 31, 34, 35, 38, 39, ...$$$
- $$$4, 5, 6, 7, 12, 13, 14, 15, 20, 21, 22, 23, 28, 29, 30, 31, 36, 37, 38, 39, ...$$$
- $$$8, 9, 10, 11, 12, 13, 14, 15, 24, 25, 26, 27, 28, 29, 30, 31, 40, 41, 42, 43, ...$$$
- $$$16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 48, 49, 50, 51, ...$$$
And so on until reaching card number 60.
The game is played in $$$q$$$ rounds. In each round, a list of $$$k$$$ numbers is given, indicating all the cards that contain the number the other player is thinking of. You must guess the secret number in each round.
The first line contains an integer $$$q$$$ ($$$1 \leq q \leq 1000$$$), indicating the number of rounds to be played.
The next $$$q$$$ lines start with an integer $$$k$$$ ($$$1 \leq k \leq 60$$$), indicating the number of cards in the round. Then, $$$k$$$ integers $$$a_i$$$ ($$$1 \leq a_i \leq 60$$$) separated by a space are presented, indicating the card number $$$i$$$. It is guaranteed that there will be no repeated cards in the same round.
For each of the $$$q$$$ rounds, print one line with the secret number the other player was thinking of.
It is guaranteed that the answer will always be a number in the range $$$[1, 10^{18}]$$$.
4 4 1 2 3 4 2 1 2 3 1 3 4 7 3 6 9 10 22 29 45
15 3 13 17592456577828
Mateo is extremely bored with his virtual classes. He is looking at the list of attendees in the class; there are a lot of people, a total of 2880. Mateo is thinking of his 3 favorite people in the class and wonders what is the probability that among the group of students there are 3 people who have the same birthday on the same day of the year and at the same time there are no more people who share birthdays, neither among themselves nor with the 3 people.
The next day, in his Probability exam, they ask him the exact same question, only they ask him to generalize the formula for $$$x$$$ people within a group of $$$n$$$. Mateo hates mathematics and that's why he didn't study probability for the ICPC, so he asks you to help him with this annoying exam question (considering that a year has 365 days).
The input consists of multiple test cases. The first line contains an integer $$$t$$$ $$$(1 \le t \le 10^3)$$$, the number of test cases.
Each test case consists of a single line containing two integers $$$n, x$$$ $$$(2 \le x \le n \le 10^{18})-$$$ the number of people in the group and how many people must have the same birthday.
For each test case, print the answer to the problem. It can be shown that the answer can be represented as an irreducible fraction $$$\frac{p}{q}$$$.
Print $$$pq^{-1}$$$ modulo $$$10^9 + 7$$$.
42 23 228 3100 99
882191787 839324457 542713201 259255172
For this problem, you will find the sum of the proper divisors of a number excluding the number itself. For example, the sum of the divisors of $$$n=10$$$ is $$$5+2+1=8$$$. This process can be repeated until there are no more divisors in the sum. See the case for $$$n=10$$$:
- Sum of the divisors of $$$10$$$: $$$5 + 2 + 1 = 8$$$.
- Sum of the divisors of $$$8$$$: $$$4 + 2 + 1 = 7$$$.
- Sum of the divisors of $$$7$$$: $$$1$$$.
- Sum of the divisors of $$$1$$$: $$$0$$$.
Numbers can be classified according to the behavior of the sum of their divisors. For now, the following types of numbers will be considered:
- "perfectos". These are numbers whose sum of divisors equals the number itself. For example, the sum of the divisors of 6 is $$$3+2+1=6$$$.
- "romanticos". If the sum of the divisors of a number gives a different number, and the sum of the divisors of this latter number gives the original number, then the number is said to be romantic. For example, the sum of the divisors of $$$220$$$ is $$$284$$$, and the sum of the divisors of $$$284$$$ is $$$220$$$; both are romantic numbers.
- "abundantes". These are numbers whose sum of divisors is strictly greater than the number itself. For example, the sum of the divisors of $$$12$$$ is $$$6+4+3+2+1=16$$$; $$$12$$$ is an abundant number.
- "complicados". These are numbers that are not "perfectos", "romanticos", nor "abundantes".
You will be given a list of numbers and you must classify them according to the type of number they are.
In the case that a number is both "romantico" and "abundante", you should print its classification as "romantico" first and then as "abundante". See the example cases for clarity.
The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$), indicating the number of numbers to be classified.
The following $$$n$$$ lines each contain an integer $$$a_i$$$ ($$$1 \leq a_i \leq 10^5$$$), indicating the number to be classified.
For each number, you must print a line with the number followed by its classification. The number and each classification should be separated by a space.
5 28 220 276 1 287
28 perfecto 220 romantico abundante 276 abundante 1 complicado 287 complicado
Armando is a very curious child; he always gets obsessed with something different, and now, he is obsessed with numbers. In particular, he is very interested in the fact that many natural numbers can be represented as the product of smaller numbers. For example, $$$2002$$$ can be represented as $$$14 \times 143$$$; $$$2880$$$ can be represented as $$$2 \times 2 \times 16 \times 45$$$.
He also realized that he can add an infinite number of ones to any number and it will still be the same number ($$$2002 = 14 \times 143 \times 1 \times 1 \times ...$$$). This seems absurd to him, so he decided never to use ones in his representations.
Now he wonders: What is the representation of a number $$$n$$$ as a product of smaller or equal numbers that uses the largest number of factors possible without using ones?
You must help him find this product. To make it easier for Armando to understand the answer, you should print the factors in non-decreasing order and separate each one with the letter 'x' (lowercase 'x', without quotes).
The first and only line contains an integer $$$n$$$ ($$$2 \leq n \leq 10^5$$$).
A line with the factors in non-decreasing order, separated by the letter 'x'.
12
2x2x3
5
5
94202
2x19x37x67
In the first example, $$$12$$$ can be represented as $$$4 \times 3$$$, $$$12$$$, $$$2 \times 6$$$ or $$$2 \times 2 \times 3$$$. The answer is $$$2 \times 2 \times 3$$$ because it is the representation with the most factors.
Franklin Richards is a very curious and playful boy who, unlike other children, has extraordinary powers. Franklin has been watching YouTube videos about setting up domino tiles and how they fall one after the other. Inspired, Franklin decided to do something similar and created a bag from which he can draw any number of one-dimensional domino tiles of any height with infinitesimal width. He also created a one-dimensional play table.
Franklin drew $$$n$$$ domino tiles numbered from $$$1$$$ to $$$n$$$ and placed them vertically on the table (it seems impossible for them to balance, but since Franklin has powers beyond your imagination, this is possible). It is known that there is always an integer distance $$$x_i$$$ greater than $$$0$$$ between tile $$$i$$$ and tile $$$i - 1$$$, for each $$$i \gt 1$$$. After setting up all the tiles, Franklin thought that if he pushed one tile, it would trigger all the tiles to fall. Determine if Franklin is right. It is known that a domino tile $$$a$$$ can knock down another tile $$$b$$$ if the height $$$h_a$$$ is greater than the distance between $$$a$$$ and $$$b$$$ and tile $$$a$$$ falls towards $$$b$$$.
The input consists of multiple test cases. The first line contains an integer $$$t$$$ $$$(1 \le t \le 10^4)$$$, the number of test cases. Each test case is described as follows:
First line: An integer $$$n$$$ $$$(2 \le n \le 10^5)$$$, the number of domino tiles.
Second line: $$$n$$$ integers $$$h_1, h_2, \ldots, h_n$$$ $$$(1 \le h_i \le 10^9)$$$, where $$$h_i$$$ represents the height of tile $$$i$$$.
Third line: $$$(n-1)$$$ integers $$$x_2, x_3, \ldots, x_n$$$ $$$(1 \le x_i \le 10^9)$$$, where $$$x_i$$$ is the distance between tile $$$i$$$ and tile $$$i-1$$$.
The sum of $$$n$$$ in all test cases does not exceed $$$10^5$$$.
For each test case, print the word "habibi" if pushing any tile can cause all the others to fall, or "which" if it is not possible.
4210 1010310 20 309 10330 5 1010 10310 5 3010 10
which habibi habibi habibi
You have an array $$$a$$$ of $$$n$$$ positive integers. There are three types of operations performed on this array:
- Given a value $$$i$$$, remove a random prime factor from $$$a_i$$$. If $$$a_i$$$ has no prime factors, do nothing.
- Given two values $$$l$$$ and $$$r$$$, find the minimum possible sum of the prime factors of the numbers $$$a_l, a_{l+1}, \ldots, a_r$$$.
- Given three values $$$l$$$, $$$r$$$, and $$$x$$$, assign the value $$$x$$$ to $$$a_i$$$ for all $$$l \leq i \leq r$$$.
Given the array $$$a$$$ and a sequence of $$$q$$$ operations performed in order, determine the result of each type 2 operation.
The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$), the size of the array $$$a$$$.
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^4$$$), the elements of the array $$$a$$$.
The third line contains an integer $$$q$$$ ($$$1 \leq q \leq 10^5$$$), the number of operations.
The next $$$q$$$ lines describe the operations performed in order. Each operation is described by an integer $$$t$$$ ($$$1 \leq t \leq 3$$$) and the values corresponding to the operation.
- If $$$t=1$$$, a value $$$i$$$ ($$$1 \leq i \leq n$$$) is given.
- If $$$t=2$$$, two values $$$l$$$ and $$$r$$$ ($$$1 \leq l \leq r \leq n$$$) are given.
- If $$$t=3$$$, three values $$$l$$$, $$$r$$$, and $$$x$$$ ($$$1 \leq l \leq r \leq n$$$, $$$1 \leq x \leq 10^4$$$) are given.
For each type 2 operation, print an integer, the minimum possible sum of the prime factors of the numbers $$$a_l, a_{l+1}, \ldots, a_r$$$.
4 10 9 2 4 8 1 4 2 1 4 1 1 2 1 3 3 2 3 12 2 2 4 1 4 2 4 4
17 10 16 0
8 9608 9630 489 5648 5240 8338 9028 5564 10 2 6 6 3 3 7 9838 3 6 7 7525 1 8 2 8 8 2 2 5 2 1 3 1 5 2 6 7 2 5 6
392 17 14883 6248 120 62
For the first case, the first 4 operations are performed as follows:
- Remove a random prime factor from $$$a_4$$$; since $$$a_4 = 4 = 2 \times 2$$$, we get $$$a_4 = 2$$$.
- The sum of the prime factors of 10, 9, 2, and 2 is $$$2 + 5$$$ $$$+$$$ $$$3 + 3$$$ $$$+$$$ $$$2$$$ $$$+$$$ $$$2$$$ $$$= 17$$$.
- Remove a random prime factor from $$$a_1$$$; since $$$a_1 = 10 = 2 \times 5$$$, we can get $$$a_1 = 2$$$ or $$$a_1 = 5$$$.
- There are two possible sums: $$$2$$$ $$$+$$$ $$$3 + 3$$$ $$$+$$$ $$$2$$$ $$$ = 10$$$ or $$$5$$$ $$$+$$$ $$$3 + 3$$$ $$$+$$$ $$$2$$$ $$$ = 13$$$; the minimum is 10.
Pacha loves hiking in the mountains. This time, he decided to go to the highest point of the mountains surrounding his city to take a souvenir photo. It is well known that there is no other point on the mountain with an equal or higher height, so he has the best view.
He always gathers a group for these activities, and this time, you decided to join. The day of the hike arrived; you had everything prepared, but unfortunately, you overslept... You won't be able to accompany the group all the way, but you can meet them at the highest point. You ask Pacha for the map to reach them, and he sends it to you in the form of a riddle.
The mountains are represented as a string consisting of the characters '$$$+$$$' and '$$$-$$$', each indicating whether that point of the mountain is higher or lower than the previous one from left to right, and always having a height difference of 1 meter. He also tells you to assume that the point before the start of the mountain is at height 0.
For example, the string $$$+++--+--$$$ is a map of mountains with heights $$$[1, 2, 3, 2, 1, 2, 1, 0]$$$.
Given the map, you must calculate the position of the mountain (from left to right) that corresponds to the highest point to meet the group.
The first and only line contains a string $$$s$$$ formed by the characters '$$$+$$$' and '$$$-$$$' (without quotes). The size of the string will not exceed $$$10^5$$$ and will contain at least one character.
It is guaranteed that all points of the mountains will be at a non-negative height and that there will only be one highest point.
An integer, indicating the position of the mountain corresponding to the highest point.
+-+-+++--+--
7
+++-++-+--+++-+++--+
17
In the first case, the mountain points have heights $$$[1, 0, 1, 0, 1, 2, 3, 2, 1, 2, 1, 0]$$$. The point at position $$$7$$$ is the highest.
Matías is a renowned chef who has been specializing in pizzas lately.
Having prepared and tasted hundreds of pizzas, Matías noted pairs of ingredients (represented by integers) that have the same flavor.
This relationship of equal flavors is transitive, and sometimes out of laziness, Matías omits pairs that are already represented by the rest of the notes; for example, if he noted that pairs $$$(1, 2)$$$ and $$$(2, 3)$$$ have the same flavor, he may not note the pair $$$(1, 3)$$$ because it can be deduced that if $$$1$$$ tastes the same as $$$2$$$ and $$$2$$$ tastes the same as $$$3$$$, then $$$1$$$ tastes the same as $$$3$$$.
His friends, Javier, Víctor, and Lalo, gathered with Matías to make pizzas, and they came up with the following strategy:
- Put all the ingredients in a randomly sorted list.
- Check the ingredients one by one in the order of the list.
- If the current ingredient would add a new flavor to the pizza according to Matías' notes and the ingredients already used, add it to the pizza. If not, do not add it.
Soon they realized, disappointed, that all the pizzas they made tasted the same. But Víctor, being the computer scientist of the group, became more interested in the total number of different pizzas that could be made with their strategy. Two pizzas are considered different if the sets of ingredients used in both are different.
Víctor quickly calculated the value and wants to confirm the answer with you. Given the number of ingredients and Matías' notes, calculate the number of different pizzas that can be formed modulo $$$10^9+7$$$ using the described strategy.
The first line contains two integers $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ and $$$m$$$ $$$(0 \leq m \leq \min(\frac{n(n-1)}{2}, 10^5))$$$, indicating the total number of ingredients and the number of pairs in Matías' notes.
The following $$$m$$$ lines contain two integers $$$a_i$$$, $$$b_i$$$ $$$(1 \leq a_i, b_i \leq n, a_i \neq b_i)$$$ each, indicating that ingredient $$$a_i$$$ has the same flavor as ingredient $$$b_i$$$ and vice versa. There are no repeated pairs in Matías' notes.
An integer, indicating the number of different pizzas that can be formed modulo $$$10^9+7$$$ using the described strategy.
5 3 1 3 2 4 3 5
6
20 9 1 9 2 6 2 16 6 20 7 13 8 15 10 20 16 18 17 18
56
In the first example case, pizzas can be formed with the following sets of ingredients: $$$\{1, 2\}$$$, $$$\{1, 4\}$$$, $$$\{3, 2\}$$$, $$$\{3, 4\}$$$, $$$\{5, 2\}$$$, $$$\{5, 4\}$$$.
Note that ingredients $$$1$$$ and $$$5$$$ have the same flavor (which is the same as the flavor of $$$3$$$), so they cannot be used together in the same pizza.
One possible way to make a pizza with ingredients $$$\{3, 2\}$$$ is with the following list of ingredients (after randomly sorting it): $$$[3, 5, 2, 1, 4]$$$. In this case, $$$3$$$ adds a new flavor and is added; $$$5$$$ has the same flavor as $$$3$$$, so it is not added; $$$2$$$ adds a new flavor and is added; $$$1$$$ has the same flavor as $$$3$$$, so it is not added; $$$4$$$ has the same flavor as $$$2$$$, so it is not added.
Chess has always been a legendary discipline with a variety of pieces, such as bishops, rooks, king, queen, knights, and pawns. Each of these pieces has defined movements, and this time we will talk about the bishop. We will have a board with $$$n$$$ rows and $$$m$$$ columns where we will launch a bishop from the upper left corner, and in this case, the bishop will always go until it touches the edge of the board (it bounces on the edges). Let's see the following examples:
For $$$n=4$$$ , $$$m=6$$$
And so on
Therefore the number of squares that were not visited is 12.
Now for the case For $$$n=5$$$ , $$$m=5$$$
Therefore the number of squares that were not visited is 20.
The input consists of multiple test cases, each on a separate line.
Each case contains two integers $$$n, m$$$ $$$(2 \leq n,m \leq 10^9)$$$ indicating the dimensions of the chessboard. The total number of test cases is less than $$$5\cdot 10^4$$$.
For each case, print an integer with the number of squares not visited by the super bishop.
4 6 5 5
12 20
Aylin is in a maze with several treasures and wants to know the maximum number of treasures she can gather. Each square of the maze can contain treasures (whose quantity per square is represented by a digit between 1 and 9), a trap 'T', an empty space '.', or a wall '#'.
An interesting detail is that the maze is in complete darkness and she must blindly traverse the entire maze, with movements allowed up, down, left, or right. She can know if there are traps around her position (cell above, below, left, or right), but she does not know in which direction the trap is. She will not take risks, so she will avoid moving forward in her journey if there are traps around her, being able to safely retreat to a position without danger even if it has already been traversed.
The input consists of multiple test cases.
Each case begins with a line with 2 integers $$$N, M$$$ $$$(1 \leq N,M \leq 10^3)$$$ followed by N lines with M characters each, which is the map description. There is a square that contains the letter 'S' representing Aylin's initial position. It is guaranteed that there is only one 'S' square for each test case.
For each case, print a line with an integer indicating the maximum number of treasures that Aylin can gather.
4 9 S......T. #####.### 111.#.111 ..T....T. 4 7 S....T1 ..111.. ..1T1.. ..111.. 2 5 .23.. .3T.S
2 5 3