Time limit: 1 second Memory limit: 256 megabytes ---------- The selection phase of Pardis Code has been entrusted to Romina and Ali. They are going to hold a tug-of-war competition, and each will select a team from the participants. All members of the winning team advance to the final round. Team selection proceeds as follows: First, Romina selects one participant. Then, Ali chooses two people from the remaining participants. From this point onward, the selection turns continue alternately (starting with Romina), and each person selects two participants each time until no one is left to choose. (If, in the end, the number of remaining participants is less than the required number for selection, Romina or Ali will select only one person in their final turn.) The goal of Romina and Ali is to form the strongest possible team; therefore, both make their choices in the most optimal and intelligent way possible. After team selection, Romina decides to bribe a number of members of the opposing team to withdraw in her favor and be passive in the tug-of-war. What is the minimum number of members Romina must bribe so that the total weight of her team is greater than Ali's team? And conversely, if Ali wants to do this, what would the answer be? State the method of bribing for Romina or Ali to win. **The weights of all participants are distinct.** # Input The first line contains a natural number $n$, representing the total number of participants. The second line contains $n$ natural numbers, representing the weights of the participants. The third line contains one of the strings `"romina"` or `"ali"`, which specifies for whom the bribe analysis should be performed. $$2 \leq n , a_i \leq 10^5$$ # Output The first line should print the minimum number of people the targeted individual must bribe. The second line should list the weights of these individuals in order from **heaviest to lightest**. # Examples ## Sample Input 1 ``` 5 1 4 6 9 2 romina ``` ## Sample Output 1 ``` 0 ``` ## Sample Input 2 ``` 4 1 4 6 9 romina ``` ## Sample Output 2 ``` 1 6 ``` ## Sample Input 3 ``` 4 5 7 3 1 ali ``` ## Sample Output 3 ``` 1 1 ```

Time limit: 1 second Memory limit: 256 megabytes ---------- A grid with $n$ rows and $m$ columns consisting of integers between $0$ and $9$ is called **exceptional** if and only if for every cell in the grid containing the number $x$, exactly $x$ of its adjacent to the sides cells(excluding itself) also contain the number $x$. The numbers $n$ and $m$ are given to you. If an exceptional grid with $n$ rows and $m$ columns exists, report it. # Input The first line of input contains the number $t$, the number of test cases. In each of the following $t$ lines, two natural numbers $n$ and $m$ are given. $$ 1 \leq t \leq 10^5 $$ $$ \sum n \cdot m \leq 10^6 $$ # Output For each test case, if at least one exceptional grid exists, print the phrase `Yes`. Then, in the following $n$ lines, print a string of length $m$ consisting of digits $0$ through $9$ in each line (representing the grid). If no exceptional grid exists, print the phrase `No`. When printing `Yes` or `No`, the output is case-insensitive. # Example ## Sample Input ``` 3 1 1 2 2 4 4 ``` ## Sample Output ``` Yes 0 Yes 22 22 Yes 0222 2212 2012 2222 ```

Time limit: 1 second Memory limit: 256 megabytes ---------- In Scotland, significant differences are seen in gasoline prices. For example, the price of gasoline in the city of $\text{Dunfermline}$ is about 135.7 pence per liter, while in $\text{Glasgow}$ and $\text{Kilmarnock}$ it is about 130.9 pence. The people of Scotland want to know how many pence they must spend to travel from any city to any other city. Scotland has $n$ cities and $m$ roads, and there is at most one road between any two cities. Each road is represented by three numbers $v$, $u$, and $w$, indicating a road between cities $v$ and $u$, and traversing this road requires $w$ liters of gasoline in either direction. We also know that each liter of gasoline in city $i$ costs $a_i$ pence. You must calculate the minimum amount of money (in pence) required to travel from city $s$ to city $t$ for every pair of cities $s$ and $t$. Note that when starting in city $s$, we have no fuel, and we can refuel any amount we desire in any city, with no capacity limit on the fuel we carry. The only restriction is that we must have the required fuel when using a road. # Input The first line of input contains two numbers, $n$ and $m$, the number of cities and the number of roads in Scotland. The second line of input contains the sequence $a_1, a_2, \ldots, a_n \ $, where $a_i$ represents the price per liter of gasoline in city $i$. Each of the following $m$ lines contains three numbers $v$, $u$, and $w$, indicating a bidirectional road between cities $v$ and $u$, requiring $w$ liters of gasoline to use. $$1 \le n \le 500$$ $$n-1 \le m \le \frac{n(n-1)}{2}$$ $$1 \le v \neq u \le n$$ $$1 \le w, a_i \le 10^6$$ It is guaranteed that the input graph is connected, and there is at most one road between any two vertices (no duplicate roads). # Output The output is an $n \times m$ matrix where entry $(i, j)$ represents the minimum amount of money required to travel from city $i$ to city $j$. # Example ## Sample Input 1 ``` 3 3 1 10 3 1 2 4 2 3 5 3 1 6 ``` ## Sample Output 1 ``` 0 4 6 40 0 46 18 15 0 ``` ## Sample Input 2 ``` 5 7 600783 171847 191295 353053 995582 1 2 479221 1 3 159037 1 4 917731 4 5 63986 5 1 809126 4 2 64758 4 3 880750 ``` ## Sample Output 2 ``` 0 217642290081 95546725971 228770758107 239766560249 82352691187 0 109682722526 11128468026 22124270168 30422982915 122095564110 0 133224032136 144219834278 105215697361 22863006174 132545728700 0 22590449258 168919007213 86566316026 196249038552 63703309852 0 ```

Time limit: 1 second Memory limit: 256 megabytes ---------- After a long day, Amin has decided to escape the Pardis Code land and take a rest. But Romina has noticed and wants to prevent his escape. However, Amin suggests solving a problem in exchange for being allowed to leave. Initially, a permutation is written on the board. In each step, Romina writes a new sequence on the board and erases the previous one. The new sequence is written by considering every two consecutive numbers: + If the number of elements in the current sequence on the board is odd, she selects the larger number and writes it below them in the new sequence. + If the number of elements in the current sequence on the board is even, she selects the smaller number and writes it below them in the new sequence. Similarly, after Romina's operations, in each step, a new sequence with one fewer element is written on the board, and then the previous sequence is erased. These steps are repeated until only one number remains on the board. Now, Romina wonders: if she starts the game for all different sequences obtained by erasing a portion from the right side and a portion from the left side of the initial sequence (i.e., all contiguous subarrays) and writes the remaining final number in her notebook, what is the sum of all numbers written in her notebook? Help Amin solve the problem so he can rest. Since the total sum might be large, output its remainder modulo $10^9 + 7$. # Input The first line contains an integer $N$, representing the number of elements in the initial permutation. $$ 1 \leq N \leq 2 \times 10^5 $$ The next line contains $N$ integers, which are the elements of the permutation from left to right. $$ 1 \le a_i \le n $$ It is guaranteed that the initial sequence is a permutation and contains no duplicate numbers. # Output Output the remainder of the sum of all answers for all contiguous subarrays of the initial permutation modulo $10^9 + 7$. # Example ## Sample Input 1 ``` 5 1 2 3 4 5 ``` ## Sample Output 1 ``` 42 ``` ## Sample Input 2 ``` 4 1 3 2 4 ``` ## Sample Output 2 ``` 23 ```

Time limit: 2 seconds Memory limit: 256 megabytes ---------- After her adventures in Vietnam, Sana is lost in the jungles of Vietnam, and her GPS is out of order. The map of Vietnam is modeled as a weighted tree with $n$ vertices; every edge has a positive weight, and the distance between two vertices is the sum of the weights of the edges on the unique path between them. Sana knows that she is located at one of the vertices of this tree. Using her knowledge of signals, she has built a device that can connect to the telecommunication towers at different vertices. Each time she receives a signal, based on the signal round-trip time, she concludes that the distance from the vertex she is currently at to a specified vertex is no more than a certain amount. Now Sana wants to write a program to identify her location by analyzing this data. You must process $q$ queries. In each query, either a new signal is received, or Sadra (Sana's impatient younger brother) asks her whether, given the information received so far, it is possible for her to be at vertex $v$. We have two types of queries: + 1 v x : From this moment onward, we know the distance to vertex $v$ is at most $x$. + 2 v : You must answer the question of whether it is possible to be at vertex $v$ or not. It is possible that none of the vertices satisfy the received information. Pay attention to the first example. # Input The first line of the input contains $T$, the number of test cases. The first line of each test case contains the number $n$, the number of vertices in the tree. In the next $n - 1$ lines, the edges of the tree are described. Each line contains three numbers $v_i, u_i, w_i$ in order, meaning there is an edge with weight $w_i$ between vertices $v_i$ and $u_i$. The next line contains $q$, the number of queries. In each of the next $q$ lines, a query of one of the two following formats appears: + 1 v x + 2 v # Output For every type 2 query, print `Yes` on a single line if it is possible for Sana to be at that vertex, and `No` if it is not possible. # Constraints $$ 1 \leq T \leq 10^5 $$$$ 1 \leq n \leq 2 \cdot 10^5 $$$$ 1 \leq w_i \leq 1000 $$ $$ 1 \leq q \leq 4 \cdot 10^5 $$$$ 1 \leq v \leq n $$$$ 1 \leq x \leq 10^9 $$ + It is guaranteed that the input sequence describes a tree. $$ \sum n \leq 2 \cdot 10^5 $$ $$ \sum q \leq 4 \cdot 10^5 $$ # Example ``` 2 3 1 2 2 1 3 2 6 1 1 2 2 2 1 1 1 2 2 1 2 0 2 1 6 1 2 262 1 3 396 2 6 724 3 4 693 4 5 845 9 1 5 2501 2 6 2 5 1 3 1273 2 5 1 1 372 1 6 871 2 3 2 2 ``` ``` Yes No No No Yes No No Yes ```

+ Time limit: 2 seconds + Memory limit: 256 megabytes ---------- We have several individuals (psychopaths) in a row. Each individual has a power and a cost, both represented by a natural number. The power of any two individuals is different. In one operation, we can instruct an individual to kill one of their neighbors, chosen by us, provided that the power of the killer is greater than the victim. To carry out this instruction, we must pay an amount equal to the cost of the killer individual. In this problem, the power and cost of $n$ individuals are given, and for every interval of them, you must calculate the minimum possible amount of money required until only one individual remains. Finally, output the sum of these values over all intervals, modulo $998244353$. \**It is guaranteed that the powers of the individuals form a random permutation of 1 to $n$.** # Input In the first line, the number $n$ is given, representing the count of individuals. In the second line, the array $a_1, a_2, \ldots, a_n$ is given, representing the powers of the individuals. In the third line, the array $b_1, b_2, \ldots, b_n$ is given, representing the costs of the individuals. # Constraints $$ 1 \le n \le 10^6 $$ $$ 0 \le b_i \le 10^6 $$ $$ 1 \le a_i \le n $$ It is guaranteed that the array $a_1, a_2, \ldots, a_n$ is a random permutation of the numbers $1$ to $n$. The problem consists of 36 tests. One test is the sample. $n=100$ holds in 2 tests. $n=10^5$ holds in 2 tests, and $n=10^6$ holds in 32 tests. # Output Calculate the minimum money that can be paid for each interval until only one individual remains, and output the sum of these values modulo $998244353$. # Example ## Sample Input 1 ``` 10 5 9 3 4 1 7 6 8 10 2 54 92 52 56 26 75 64 12 23 94 ``` ## Sample Output 1 ``` 5905 ```

+ Time Limit: 4 seconds + Memory Limit: 256 megabytes ---------- $n$ children in Pardis Park each bought several cards, where each card features a picture of a football player. They bought a total of $m$ cards. Based on the strength and rarity of the cards, they assigned them values such that each card has a unique value between 1 and $m$. A higher number indicates a higher card value. The children can challenge each other. A challenge proceeds as follows: First, a number $k$ is determined such that both participants have at least $k$ cards. Suppose person $a$ challenges person $b$. Then, each person places their $k$ most valuable cards on the table in order of value. Then, a neutral person stacks the cards as follows: First, the most valuable card of person $a$ is placed, and then the most valuable card of person $b$ is placed on top of the previous card. On top of that, the second most valuable card of person $a$ is placed, followed by the second most valuable card of person $b$, until all $2k$ cards are stacked, forming our deck. Then, in turns, starting with person $a$, each person strikes (taps) the deck of cards. Each strike causes a certain number of cards from the top of the deck to flip over and fall onto the table. That person then takes all the flipped cards for themselves. This continues until there is at least one card remaining on the table. Now, you are given the initial list of cards belonging to the children. Then, the challenges and their results are provided, and you must output the final list of cards each person possesses. # Input In the first line, two numbers $n$ and $m$ are given, representing the number of children and the total number of cards, respectively. Then, in the next $n$ lines, the $i$-th line first contains the number $s_i$, which is the count of cards belonging to person $i$, followed by $s_i$ numbers $a_{i, 1}, a_{i,2}, \dots, a_{i, k}$, which are the values of person $i$'s cards. It is guaranteed that the card with value $i$ is held by exactly one person. Then, the number $q$, which is the number of challenges, is given. In the next $2q$ lines, two lines of input are given for each challenge. The first line contains $a$, $b$, $k$, and $r$, indicating that person $a$ challenged person $b$, they both put $k$ of their cards on the table, and they struck the cards $r$ times. It is guaranteed that both participants have at least $k$ cards. Then, the next line contains $r$ numbers $c_i$, which represent the number of cards flipped over after the $i$-th strike. It is guaranteed that the sum of these numbers is exactly equal to $2k$. # Output You must output $n$ lines. In the $i$-th line, output the number of cards held by person $i$, followed by the values of their cards in **ascending** order. # Constraints $$1 \leq q, n, m \leq 3 \times 10^5$$ $$ \sum s_i = m$$ $$1 \leq k_i, c_i$$ $$1 \leq \sum r_i \leq 3 \times 10^5$$ $$1 \leq a, b \leq n$$ $$a \neq b$$ ## Sample Input ``` 3 10 4 7 1 8 3 3 10 2 9 3 4 5 6 2 2 3 3 3 3 1 2 1 2 3 2 5 1 ``` ## Sample Output ``` 6 1 3 5 6 7 10 3 2 4 8 1 9 ```