+ Time limit: 1 second + Memory limit: 256 megabytes -------------------- Amirhosein has recently invented a new sport called **Shootball**. Shootball is just like football, with the difference that the number of players of each team on the field can be any number, and the two teams do not necessarily have to have the same number of players. We know that if a team has $x$ players in defense, $y$ players in midfield, and $z$ players in attack, then due to the importance of midfield for possession-based play, the team's power is equal to $x + 2y + z$. Since this sport has just been invented, there are currently only three teams participating in the Shootball league. Help Amirhosein determine which of these three teams is stronger than the others and will become the league champion. # Input In the first line of the input, three natural numbers $a_1 \ $, the number of players of the first team in defense, $a_2 \ $, the number of players of the first team in midfield, and $a_3 \ $, the number of players of the first team in attack, are given. In the second line of the input, three natural numbers $b_1 \ $, the number of players of the second team in defense, $b_2 \ $, the number of players of the second team in midfield, and $b_3 \ $, the number of players of the second team in attack, are given. In the third line of the input, three natural numbers $c_1 \ $, the number of players of the third team in defense, $c_2 \ $, the number of players of the third team in midfield, and $c_3 \ $, the number of players of the third team in attack, are given. $$1 \leq a_1, a_2, a_3, b_1, b_2, b_3, c_1, c_2, c_3 \leq 100$$ # Output In the only line of the output, print the number of the team with the highest power. If multiple teams have the same highest power, print the smallest team number. # Examples ## Sample input 1 ``` 2 9 2 3 5 4 4 4 2 ``` ## Sample output 1 ``` 1 ``` ## Sample input 2 ``` 4 3 3 4 7 2 3 5 7 ``` ## Sample output 2 ``` 2 ``` In this case, the power of the second and third teams is equal and greater than that of the first team.

+ Time Limit: 1 second + Memory Limit: 256 MB -------------------- Amirhosein has a piece of land consisting of $n$ consecutive sections. The height of section $i$ is $a_i$, and the array $a$ is a permutation of the numbers from $1$ to $n$. We call a section a **pit** if its height is smaller than the heights of all of its neighboring sections. In other words, if a section has no neighbors, it is always a pit; if it has exactly one neighbor, it is a pit if it is shorter than that neighbor; and if it has two neighbors, it must be shorter than both of them. Now, Amirhosein has a ball on every section of the land. For each ball, he wants to know the minimum amount of time needed for the ball to enter a pit if it is rolled from its initial section in either the **left or right** direction. A ball may fail to reach any pit when started in one of the two directions, but it is guaranteed that every ball can reach a pit in at least one of the two possible directions. If the ball is initially in a pit, the answer is $0$. Once a ball starts rolling in a direction, it never changes direction. While rolling in a particular direction, if the height of the section where the ball currently is is greater than the height of the next section in that direction, the ball rolls into that adjacent section. Each move to an adjacent section takes **1 unit of time**. For every section, find the minimum time required for the ball placed on that section to enter a pit. # Input The first line contains a single integer $n$. $$1 \le n \le 2*10^5$$ The second line contains $n$ integers, where the $i$-th integer denotes the height of the $i$-th section of the land. $$1 \le a_i \le n$$ The array $a$ is a permutation of the numbers from $1$ to $n$, and no two sections have the same height. # Output Print $n$ integers in one line. The $i$-th integer should be the minimum time required for the ball placed on section $i$ to enter a pit. # Example ## Sample Input 1 ``` 7 2 3 6 7 4 1 5 ``` ## Sample Output 1 ``` 0 1 2 2 1 0 1 ```

+ Time limit: 1 second + Memory limit: 256 megabytes ------------- Amirhosein has $n$ seconds available to do his daily activities. He also has $c$ units of money and can tolerate a maximum temperature of $h$ degrees; that is, his body temperature must never exceed $h$. We also know that his body temperature is always a non-negative integer. In each second, Amirhosein chooses one of the following two states: + **Headphones on:** In this state, he can turn the air conditioner on or off. If the air conditioner is off, his over-ear headphones act like a blanket, and his body temperature increases by one degree during that second. If the air conditioner is on, his body temperature does not change. Keeping the air conditioner on for one second costs one unit of money. + **Headphones off:** In this state, his body temperature decreases by one degree during that second, and whether the air conditioner is on or off has no effect on his body temperature; with the exception that the temperature can never become less than zero. More precisely, if the temperature before this second is $t$, then after it, the temperature becomes $max(0, t - 1)$. Amirhosein initially has a body temperature of $0$ degrees, and at no point can his temperature exceed $h$ degrees. Also, the total cost of keeping the air conditioner on during all $n$ seconds must not exceed $c$. Amirhosein's enjoyment from listening to music is calculated as follows: Every **maximal interval** of consecutive seconds during which Amirhosein wears his headphones is considered a music-listening interval. If the length of this interval is $l$ seconds, then $l^2$ is added to his enjoyment. Given the values of $n$, $c$, and $h$, **calculate the maximum amount of enjoyment that Amirhosein can obtain.** # Input The only line of input contains three integers $n$, $h$, and $c$. $$1 \leq n, h, c \leq 10^9$$ # Output Print a single integer equal to the maximum amount of enjoyment that Amirhosein can obtain. # Sample ## Sample input 1 ``` 10 2 2 ``` ## Sample output 1 ``` 21 ``` + $2$ seconds of listening, enjoyment $4$ + $2$ seconds of resting until the temperature reaches zero + $1$ second of listening, enjoyment $1$ + $1$ second of resting + $4$ seconds of listening using $2$ units of money for the air conditioner, enjoyment $16$ In total: $$4 + 1 + 16 = 21$$

+ Time Limit: 1 second + Memory Limit: 256 megabytes ----------- There are some fish standing in a queue. The weight of every fish except the first one is known, and the weight of the $i$-th fish is $a_i$. Fish $i$ can eat fish $j$ if and only if $a_j \leq a_i$. If fish $i$ eats fish $j$, the weight of fish $i$ will eventually become equal to the sum of the weights of the two fish, and fish $j$ will no longer be in the queue. As long as more than one fish remains in the queue, the following two steps are performed in order: + First, the first fish tries to eat the only fish adjacent to it. If the first fish cannot eat the fish in front of it, the game ends and the first fish loses. + Amirhosein, who hates the first fish, can choose some pairs of the remaining fish (including the first fish). He may choose no pairs. Each fish can belong to at most one pair, and two fish that are not adjacent to each other cannot be paired. Then, in each pair, Amirhosein forces the heavier fish to eat the lighter fish. If the two fish have equal weights, he may choose either one to eat the other. Amirhosein, determined to destroy the first fish, wants to find the minimum natural number $x$ such that if the weight of the first fish is $x$ $(a_1=x)$, then no matter how Amirhosein chooses the pairs during the game, the only fish remaining at the end of the game will be the first fish. # Input The first line contains an integer $n$, the number of fish. The second line contains $n-1$ integers representing the weights of the second through the $n$-th fish, respectively. $$ 1 \leq n \leq 3*10^5 $$ $$ 1 \leq a_i \leq 10^9 $$ # Output Print the minimum possible initial weight of the first fish such that the first fish cannot be eaten by any other fish, regardless of how the pairs are chosen. # Sample input 1 ``` 3 3 7 ``` # Sample output 1 ``` 5 ``` # Sample input 2 ``` 6 7 1 10 6 8 ``` # Sample output 2 ``` 16 ```

+ Time Limit: 3 seconds + Memory Limit: 256 megabytes --- Mohammadsam has recently become interested in participating in various lotteries. In the latest lottery he participated in, he was given an \(n\)-digit code consisting of the digits \(1\), \(2\), and \(3\). He defines a luckiness index for himself so that he can use it to guess whether he might win the lottery or not. For an \(x\)-digit code called \(s\), whose digits are \(s_1\) through \(s_x\), he defines the attractiveness of that code as the number of indices \(i\) such that $$ 1 \leq i \leq x-1 $$ and $$ s_i < s_{i+1} $$ and denotes it by \(G(s)\). (The attractiveness of a 0-digit code is defined as \(0\).) In other words, \(G(s)\) represents the number of positions in code \(s\) where the digit is smaller than the next digit. He defines the luckiness of an \(n\)-digit lottery code \(s\) as the sum of \(G(a)^k\) over all \(2^n\) subsequences of code \(s\), where \(k\) is a fixed number given as input for each test case, and \(a\) is a subsequence of \(s\). More precisely, the luckiness of a code is defined by the following expression: $$ \sum_{m=0}^{n} \; \sum_{1\le i_1<i_2<\cdots<i_m\le n} G(s_{i_1}s_{i_2}\cdots s_{i_m})^k $$ Mohammadsam has not received his lottery code yet and does not know how lucky it will be. However, he knows that this code will be an \(n\)-digit code with digits \(1\), \(2\), and \(3\). He knows that his lottery code will be chosen randomly and with equal probability from the \(3^n\) possible \(n\)-digit codes (with digits \(1\), \(2\), and \(3\)). Now he asks you to calculate the expected value of the luckiness of the lottery code Mohammadsam will receive, modulo \(10^9+7\), based on this information. It can be shown that the answer can be represented as an irreducible fraction $$ \frac{p}{q} $$ where \(p\) and \(q\) are integers and \(q \neq 0\), and you should output $$ p \cdot q^{-1} \pmod{10^9+7} $$ where \(q^{-1}\) is the multiplicative inverse of \(q\) modulo \(10^9+7\). \**Notes:** A subsequence of a code \(s\) is a sequence obtained by deleting some elements of \(s\), which may include all elements or none of them. A code of length \(n\) has \(2^n\) subsequences. # Input The input consists of \(T\) different test cases, and each test case should be solved independently. The first line contains an integer \(T\), followed by \(T\) lines. Each of the next \(T\) lines contains two integers \(n\) and \(k\), representing the length of the lottery code and the fixed number \(k\), respectively. $$ 1 \leq T \leq 50 $$ $$ 1 \leq n \leq 10^{18} $$ $$ 1 \leq k \leq 50 $$ It is guaranteed that the sum of the values of \(k\) over all test cases does not exceed \(50\). # Output In one line, calculate the expected value of the luckiness of Mohammadsam's lottery code (while this code is chosen randomly and with equal probability). # Example ## Sample Input 1 ``` 3 1 1 5 2 10 10 ``` ## Sample Output 1 ``` 0 148148169 525754884 ```

+ Time Limit: 2 seconds + Memory Limit: 256 megabytes ------------ Nelly has $n$ crystal jars, each of which has a certain **transparency**. She wants to place all the jars in a row, one after another. The transparency of jar $i$ is $a_i$. However, for some reasons, placing jars next to each other causes some of them to crack! The amount of cracking of each jar depends on the jars placed before and after it. Note that cracking a jar does not change its transparency. Suppose that in a certain ordering, jar $i$ is placed at some position. To determine the amount of cracking of this jar, among all jars that are **before it**, consider the most transparent jar as $j$, and similarly, among all jars that are **after it**, consider the most transparent jar as $k$. Then the amount of cracking of jar $i$ is determined as follows: + If $a_i < min(a_j, a_k) \ $, jar $i$ cracks by an amount of $min(a_j, a_k) - a_i \ $. + If $a_i > min(a_j, a_k) \ $ and $a_i < max(a_j, a_k) \ $, jar $i$ cracks by an amount of $max(a_j, a_k) - a_i \ $. + If $a_i > max(a_j, a_k) \ $, jar $i$ does not crack, and its amount of cracking is equal to zero. For the first jar, we only consider the jars after it, and for the last jar, we only consider the jars before it. Also, if there are no jars on one side, we consider the maximum transparency on that side to be $0$. We define the fragility of an ordering as the sum of the amounts of cracking of all $n$ jars. Nelly gives her jars to Amirhosein and asks him to find the minimum possible fragility among all permutations of these $n$ jars. Amirhosein is a little busy, so he asks you to help him find the answer. # Input The first line contains an integer $n$, the number of crystal jars. $$1 \leq n \leq 3*10^5$$ The second line contains $n$ integers, where the $i$-th integer represents the transparency of jar $i$. $$1 \leq a_i \leq 10^9$$ It is guaranteed that no two jars have the same transparency. # Output Print the minimum possible fragility among all permutations of the $n$ jars in a single line. # Examples ## Sample input 1 ``` 5 3 1 4 2 5 ``` ## Sample output 1 ``` 6 ``` ## Sample input 2 ``` 7 7 1 10 2 6 8 12 ``` ## Sample output 2 ``` 20 ```