Sara has a very old printing press. Adding letters to the press is very difficult, so she wants to avoid doing it. At the moment, there is a line with ten letters in the press. She wants to remove some of the letters (without changing their order) so that the word TAP remains.
For example, if she has
she can achieve this by removing the lighter letters, leaving only the underlined ones. The same applies to
However, she cannot achieve her goal with
Your task is to determine if she can achieve her goal.
A line with a string formed by ten uppercase letters.
A line with the uppercase letter "S" if she can achieve her goal, or the uppercase letter "N" otherwise.
CONTRAPELO
S
XATPTKABPB
S
XATPTPKABB
N
Given an array $$$A$$$ of length $$$N$$$, whose elements are $$${A_1}, {A_2}, \ldots, {A_N}$$$, its array of $$$K$$$-sums blocks is defined as the array of length $$$N-K+1$$$ that satisfies $$$$$$B_i = A_i + A_{i+1} + \cdots + A_{i+K-1}$$$$$$
For example, for $$$A = [0,1,1,0,1]$$$, its array of $$$4$$$-sums blocks is $$$B = [2, 3]$$$, since $$$B_1 = 0 + 1 + 1 + 0 = 2$$$ and $$$B_2 = 1 + 1 + 0 + 1 = 3$$$.
Given an array $$$B$$$ of length $$$N-K+1$$$, count how many arrays $$$A$$$ of length $$$N$$$ exist such that their array of $$$K$$$-sums blocks is $$$B$$$. Both $$$B$$$ and the possible arrays $$$A$$$ consist of non-negative integers. Since the number of arrays $$$A$$$ can be very large, the answer must be given modulo $$$998244353$$$.
Note that the sums of the $$$K$$$-sums blocks array are exact and not modular, meaning the modulo should only be applied to the answer.
The first line contains two integers $$$N$$$ and $$$K$$$ ($$$1 \leq K \leq N \leq 2 \cdot 10^5$$$).
The second line contains $$$N-K+1$$$ integers $$${B_1}, {B_2}, \ldots, {B_{N-K+1}}$$$ ($$$0 \leq B_i \leq 10^9$$$), the elements of the array $$$B$$$.
A line with an integer indicating the number (modulo $$$998244353$$$) of possible arrays $$$A$$$ formed by non-negative integers such that $$$B$$$ is their array of $$$K$$$-sums blocks.
5 4 2 3
10
6 1 2 3 0 8 2 5
1
2 2 1000000000
1755648
In the first example, there are $$$10$$$ possible arrays $$$A$$$. These are $$$[0,1,1,0,1]$$$, $$$[1,0,1,0,2]$$$, $$$[0,0,1,1,1]$$$, and $$$7$$$ other arrays.
In the second example, the only possible array is $$$[2, 3, 0, 8, 2, 5]$$$.
In the third example, remember that the answer must be given modulo $$$998244353$$$.
Luis likes to play with permutations. A permutation is an arrangement of integers such that if its length is $$$N$$$, then each of its elements is between $$$1$$$ and $$$N$$$, and no element appears more than once. For example, $$$[1,3,4,2]$$$ and $$$[1,2]$$$ are permutations, while $$$[1,3,4]$$$ and $$$[1,2,4,2]$$$ are not. In a permutation $$$P$$$ of length $$$N$$$, we denote $$${P[1]}, {P[2]}, \ldots, {P[N]}$$$ as its elements in the order they appear in $$$P$$$. For example, for $$$P=[1,3,4,2]$$$, we have $$$P[3]=4$$$.
Luis is interested in the semi-fixed points of permutations. An integer $$$x$$$ is a semi-fixed point of a permutation $$$P$$$ if $$$P[P[x]]=x$$$. We denote $$$s(P)$$$ as the number of semi-fixed points of the permutation $$$P$$$. For example, for $$$P=[3,6,1,4,2,5]$$$, we have $$$s(P)=3$$$ since $$$1$$$, $$$3$$$, and $$$4$$$ are the semi-fixed points of $$$P$$$.
Luis is also interested in the rotations of permutations. Given a permutation $$$P$$$, $$$\mathop{\mathrm{rot}}\nolimits(P)$$$ is the permutation obtained by rotating $$$P$$$ one position to the left. More generally, $$$\mathop{\mathrm{rot}}\nolimits^k(P)$$$ is the result of rotating the permutation $$$P$$$ exactly $$$k$$$ positions to the left. For example, for $$$P=[1,3,4,2]$$$, we have $$$\mathop{\mathrm{rot}}\nolimits(P)=[3,4,2,1]$$$, $$$\mathop{\mathrm{rot}}\nolimits^2(P)=[4,2,1,3]$$$, and $$$\mathop{\mathrm{rot}}\nolimits^3(P)=[2,1,3,4]$$$.
Luis came up with a brilliant idea: to combine semi-fixed points with rotations. Given a permutation $$$P$$$ of length $$$N$$$, Luis wants to calculate $$$$$$ s(P) + s(\mathop{\mathrm{rot}}\nolimits(P)) + s(\mathop{\mathrm{rot}}\nolimits^2(P)) + \cdots + s(\mathop{\mathrm{rot}}\nolimits^{N-1}(P))$$$$$$ but he does not know how to do it. Would you help him calculate it?
The first line contains an integer $$$N$$$ ($$$1 \leq N \leq 2 \cdot 10^5$$$) indicating the length of the permutation.
The second line contains $$$N$$$ distinct integers $$${P[1]}, {P[2]}, \ldots, {P[N]}$$$ ($$$1 \leq P[i] \leq N$$$), the elements of the permutation $$$P$$$.
A line with an integer, the result of the calculation that Luis wants to compute.
4 1 3 4 2
6
2 1 2
4
In the first example, $$$P=[1,3,4,2]$$$ and its rotations are:
- $$$P = [1, 3, 4, 2]$$$, with $$$1$$$ semi-fixed point, which is $$$1$$$.
- $$$\mathop{\mathrm{rot}}\nolimits(P) = [3, 4, 2, 1]$$$, with no semi-fixed points.
- $$$\mathop{\mathrm{rot}}\nolimits^2(P) = [4, 2, 1, 3]$$$, with $$$1$$$ semi-fixed point, which is $$$2$$$.
- $$$\mathop{\mathrm{rot}}\nolimits^3(P) = [2, 1, 3, 4]$$$, with $$$4$$$ semi-fixed points, which are $$$1, 2, 3$$$, and $$$4$$$.
Then, $$$s(P) + s(\mathop{\mathrm{rot}}\nolimits(P)) + s(\mathop{\mathrm{rot}}\nolimits^2(P)) + s(\mathop{\mathrm{rot}}\nolimits^{3}(P)) = 1 + 0 + 1 + 4 = 6$$$.
On a gray and rainy day, Lautaro and Fiorella decided to take shelter under the eaves of the gallery and spend the afternoon playing brisca, a traditional card game. But since their deck of cards was wet, they replaced it with a very strange one they found among their grandfather's old books. This deck has some peculiarities:
- Each card has a suit and a value.
- There are no two distinct cards with the same suit and value.
- The deck contains an arbitrary number of distinct suits, not necessarily the four usual suits.
The game of brisca is played in rounds. In each round, both players take a card from the deck, then the two cards are compared to decide who wins the round, and finally, the two cards are discarded. In the first round, Lautaro plays first, and then, the winner of a round plays first in the following round. The game ends when there are no more cards left in the deck.
At the beginning of the game, a trump suit is chosen, which beats any other suit in the deck. The rules for deciding the winner of each round take this trump suit into account and are as follows:
- If both cards are of the same suit, the one who played the card of higher value wins (remember that all cards are distinct, so there can be no ties).
- If the cards are of different suits, but one is the trump suit, the one who played the trump wins.
- If the cards are of different suits and neither is the trump suit, the one who played first in the round wins.
Lautaro, always meticulous, noted in his notebook which card each player played in each round and how many rounds each one won. However, he forgot to note which was the trump suit. Luckily, you can help him. Your task is to determine which suit in the deck could have been the trump, such that the number of rounds won by each player matches what Lautaro recorded.
The first line contains two integers $$$M$$$ and $$$N$$$ ($$$0 \leq M, N \leq 10^5$$$ and $$$M + N \ge 1$$$), indicating the number of rounds won by Lautaro and Fiorella respectively.
Each of the following $$$M + N$$$ lines describes the cards played in a round with four values: $$$V$$$, $$$P$$$, $$$W$$$, and $$$Q$$$. The values $$$V$$$ and $$$P$$$ describe the card played by Lautaro in the round, while $$$W$$$ and $$$Q$$$ describe Fiorella's card. The values $$$V$$$ and $$$W$$$ are integers ($$$1 \leq V, W \leq 10^9$$$) representing the value of the cards, while $$$P$$$ and $$$Q$$$ are non-empty strings of at most ten characters formed by uppercase letters, indicating the suits. The rounds are described in the order they were played.
A string reporting the suit that was chosen as trump, which must be one of the suits that appear in the input.
If there is more than one possible suit, any of them will be considered valid.
If no suit from the input could have been chosen as trump, the character "*" (asterisk) should be printed.
1 1 2 ROJO 3 NARANJA 1 AZUL 4 BLANCO
BLANCO
0 2 3 PLATA 2 PLATA 8 BRONCE 1 ORO
*
4 3 1 COCO 2 FRUTILLA 8 FRUTILLA 4 PERA 4 MANZANA 3 PERA 100 ANANA 10 ANANA 5 PERA 5 FRUTILLA 2 COCO 9 FRUTILLA 3 FRUTILLA 99 PERA
FRUTILLA
In the first example, if "BLANCO" is the trump suit, Lautaro wins the first round (because he plays first), while Fiorella wins the second (because she plays trump). If another suit were trump, one of the two players would win both rounds.
In the second example, Lautaro wins the first round regardless of which suit is trump, so it is impossible for Fiorella to win both rounds. None of the suits could have been chosen as trump.
In the third example, "PERA" could also have been a valid response.
Juan is playing a strategy war game called "Execution". The game is played in a tree having $$$N$$$ nodes, numbered with integers from $$$1$$$ to $$$N$$$.
Node $$$1$$$ is an indestructible bunker. When the game starts, each node other than the bunker contains a certain number of soldiers.
The game proceeds in turns. At the beginning of each turn, Juan must choose whether to attack a node or not. The bunker cannot be attacked. If Juan attacks a node, then he defeats every soldier in that node, and the game ends immediately on that turn. On the contrary, if Juan chooses not to attack, soldiers in each node other than the bunker move to a neighboring node, in the direction towards the bunker. The game then proceeds to the following turn.
Juan wants to defeat as many soldiers as possible. Moreover, he wants to defeat that maximum number of soldiers as soon as possible, that is, by playing the minimum number of turns.
The first line contains an integer $$$N$$$ ($$$2 \leq N \leq 2 \cdot 10^5$$$) indicating the number of nodes in the tree. Each node is identified with a distinct integer between $$$1$$$ and $$$N$$$.
The second line contains $$$N-1$$$ integers $$$T_2$$$,$$$T_3$$$,$$$\dots$$$,$$$T_N$$$ ($$$0 \leq T_i \leq 10^9$$$), indicating that when the game begins, node $$$i$$$ contains $$$T_i$$$ soldiers. It is guaranteed that when the game begins, there is at least one soldier outside of the indestructible bunker (node $$$1$$$), that is, $$$T_2 + T_3 + \cdots + T_N \geq 1$$$.
Each of the next $$$N-1$$$ lines contains two integers $$$U$$$ and $$$V$$$ ($$$1 \leq U, V \leq N$$$ and $$$U \neq V$$$), indicating that $$$U$$$ and $$$V$$$ are neighboring nodes in the game. It is guaranteed that these pairs of neighboring nodes define a tree.
A single line with two integers, indicating the maximum number of soldiers that Juan can defeat, and the minimum number of turns required to achieve it.
4 3 2 1 1 2 2 3 2 4
3 1
4 6 7 8 1 2 2 3 2 4
15 2
7 0 0 1 0 0 2 7 2 6 3 3 5 6 1 3 4 6 2
3 3
In the first sample, Juan could attack node $$$2$$$ on the first turn, defeating $$$3$$$ soldiers. If he didn't, on the second turn there would be $$$3$$$ soldiers in node $$$1$$$, $$$3$$$ in node $$$2$$$, and $$$0$$$ in the remaining nodes. At that moment, Juan could attack node $$$2$$$ and also defeat $$$3$$$ soldiers, but he would not achieve it in the minimum number of turns. Remember that attacking node $$$1$$$ is never allowed.
In the second sample, it is best for Juan to wait for a turn, and to attack node $$$2$$$ on the second turn.
Mechi was gifted a goat. To prevent the goat from damaging her garden, she decided to protect the crops with a wooden fence in the shape of a convex polygon. The fence has a post at each vertex of the polygon, and Mechi's idea is to tie the goat with a rope to one of these posts, so that it can eat the grass outside the fence. The grazing region will be determined by the portion of the land that the goat can access without either it or the rope crossing the fence at any time.
In the following figure, a rectangular fence is shown with the goat tied to the upper left post. The grazing region appears in gray.
Mechi has not yet decided which rope to buy. She has been offered several ropes of certain lengths and wants to know, for each of them, the area of the goat's grazing region.
Note: sometimes using acos to calculate angles can cause a large precision error. The recommended function for that is atan2.
The first line contains two integers $$$N$$$ ($$$3 \leq N \leq 10^5$$$) and $$$Q$$$ ($$$1 \leq Q \leq 10^5$$$), which indicate respectively the number of vertices of the polygonal fence protecting the garden, and the number of ropes offered to Mechi.
Each of the following $$$N$$$ lines contains two integers $$$X$$$ and $$$Y$$$ ($$$-10^8 \leq X, Y \leq 10^8$$$), indicating that the fence has a vertex with coordinates $$$(X,Y)$$$. The vertices describe a simple convex polygon that does not have three collinear vertices, and they appear in the input in counterclockwise order, starting from the vertex where Mechi will tie the goat.
The next line contains $$$Q$$$ integers $$${L_1}, {L_2}, \ldots, {L_Q}$$$ ($$$1 \leq L_i \leq 10^8$$$), indicating the lengths of the ropes offered.
Write $$$Q$$$ lines. The $$$i$$$-th line must contain a number $$$R_i$$$ equal to the area that the goat could reach if it were tied with a rope of length $$$L_i$$$.
Each value $$$R_i$$$ will be considered correct if it has a relative or absolute error less than or equal to $$$10^{-6}$$$. Formally, if $$$J_i$$$ is the jury's answer for a rope of length $$$L_i$$$, then the answer $$$R_i$$$ will be accepted if and only if $$$\frac{|R_i - J_i|}{\max{(1, |J_i|)}} \le 10^{-6}$$$.
4 1 0 2 0 0 3 0 3 2 4
41.626102660065
3 5 0 0 2 0 0 1 1 2 1 3 4
2.356194490192 10.441999928667 2.356194490192 26.132741228718 48.020700514225
The first example appears in the figure of the statement. The only rope offered has a length of $$$4$$$, and the corresponding grazing area is shown in gray. We can see that for the goat to access certain portions of the land, the rope must go around the fence, as neither it nor the goat can cross it.
Darío wants to buy an alfajor at the kiosk, which costs $$$A$$$ pesos (the Argentinian currency). He only has a $$$B$$$ peso bill, which is enough to buy it. However, the kiosk owner does not like to give change in pesos and prefers to give it in candies. Each candy costs $$$C$$$ pesos.
In the following figure, we can see alfajores and candies similar to those available at the kiosk.
Can the kiosk owner give Darío the exact change with candies?
A line with three integers $$$A$$$, $$$B$$$, and $$$C$$$ ($$$1 \leq A,B,C \leq 1000$$$ and $$$A \lt B$$$), which indicate respectively the price of the alfajor, the value of Darío's bill, and the price of each candy.
A line with the uppercase letter "S" if the kiosk owner can give Darío the exact change with candies, or the uppercase letter "N" otherwise.
10 20 5
S
6 10 3
N
In the first example, the kiosk owner can give Darío two candies as change.
In the second example, the kiosk owner cannot give the full change with candies. If he gives one candy to Darío, he falls short, while if he gives two candies, he goes over.
A mysterious positive integer $$$X$$$ has exactly $$$N+1$$$ positive divisors. $$$N$$$ of them are known and given to you in a list.
Your task is to find the mysterious number $$$X$$$ and the missing divisor, or indicate that the provided information is not enough to exactly determine those two values.
The first line consists of an integer $$$N$$$ ($$$1 \leq N \leq 2\cdot 10^5$$$) which indicates the number of divisors in the list.
The second line consists of $$$N$$$ positive integers $$$A_1,A_2,\dots,A_N$$$ ($$$1\leq A_i\leq 10^{18}$$$). These are all but one of the divisors of the mysterious number $$$X$$$ ($$$1\leq X \leq 10^{18}$$$).
A single line containing two integers: the mysterious number and the missing divisor. If it is not possible to determine them, print the character $$$\textbf{*}$$$ (asterisk).
5 3 18 1 9 2
18 6
1 1
*
3 5 1 2
10 10
In the first example, the mysterious number is $$$18$$$, whose divisors are $$$1$$$, $$$2$$$, $$$3$$$, $$$6$$$, $$$9$$$, and $$$18$$$. The missing divisor is $$$6$$$.
In the second example, more than one number could be the mysterious number.
Inés regularly plays her favorite game: "Don't compete, make compitas". This game is played in rounds, and in each round, players must choose between two options:
- Option $$$1$$$: Share $$$X$$$ units of gold among the players who choose this option (rounding down). That is, if $$$k$$$ players choose this option, each receives $$$\left\lfloor {\frac{X}{k}} \right\rfloor$$$ units of gold.
- Option $$$2$$$: Receive $$$Y$$$ units of gold directly, without sharing.
Inés will play with $$$N$$$ other players in a game of $$$M$$$ rounds. She knows in advance which option each of the other players will choose in each round. With this information, she wants to decide her strategy to maximize the gold she receives in each round.
Your task is to help Inés make the best decision in each round to achieve her goal, and also, determine the total gold that each player will receive. In case both options in a round are equally convenient for Inés, she will choose option $$$1$$$ (sharing), as she finds it the more fun option.
Note: $$$\left\lfloor {x} \right\rfloor$$$ is the largest integer that is less than or equal to $$$x$$$. For example, $$$\left\lfloor {2.5} \right\rfloor = 2$$$, $$$\left\lfloor {\pi} \right\rfloor = 3$$$, and $$$\left\lfloor {5} \right\rfloor = 5$$$.
A line with two integers $$$N$$$ and $$$M$$$ ($$$1 \leq N, M \leq 100$$$), which indicate respectively the number of players playing with Inés and the number of rounds. Each player playing with Inés is identified by a distinct integer between $$$1$$$ and $$$N$$$.
The following $$$2M$$$ lines describe the rounds, using two consecutive lines per round.
The first line of each round contains two integers $$$X$$$ and $$$Y$$$ ($$$1 \leq X, Y \leq 10^5$$$), which indicate respectively the amount of gold for options $$$1$$$ and $$$2$$$ in that round.
The second line of each round contains $$$N$$$ integers $$${A_1}, {A_2}, \ldots, {A_N}$$$ ($$$A_i=1$$$ or $$$A_i=2$$$), indicating that player $$$i$$$ chooses option $$$A_i$$$ in that round.
A single line with $$$N+1$$$ integers, representing the total gold received by each of the players (including Inés) if Inés decides her strategy as explained. The first $$$N$$$ integers represent the gold of each of the $$$N$$$ players (excluding Inés), ordered by player, while the last integer represents Inés's gold.
3 3 15 10 1 2 1 13 8 2 2 2 16 4 1 1 1
19 22 19 27
Let's see what Inés can do in the example:
- Round 1:
- If Inés chose option $$$1$$$, there would be $$$k=3$$$ players choosing that option (players $$$1$$$ and $$$3$$$, along with Inés herself). Each of them would receive $$$\left\lfloor {\frac{X}{k}} \right\rfloor=\left\lfloor {\frac{15}{3}} \right\rfloor=5$$$ units of gold.
- If Inés chose option $$$2$$$, she would receive $$$Y=10$$$ units of gold.
- Therefore, Inés chooses option $$$2$$$.
- Round 2:
- If Inés chose option $$$1$$$, she would receive $$$\left\lfloor {\frac{13}{1}} \right\rfloor=13$$$ units of gold.
- If Inés chose option $$$2$$$, she would receive $$$8$$$ units of gold.
- Therefore, Inés chooses option $$$1$$$.
- Round 3:
- If Inés chose option $$$1$$$, she would receive $$$\left\lfloor {\frac{16}{4}} \right\rfloor=4$$$ units of gold.
- If Inés chose option $$$2$$$, she would receive $$$4$$$ units of gold.
- Both options yield the same benefit for her, but she finds sharing more fun. Therefore, Inés chooses option $$$1$$$.
Now let's see how much gold player $$$1$$$ receives:
- Round 1: Chooses option $$$1$$$. Since Inés chooses option $$$2$$$, there are $$$k=2$$$ players choosing option $$$1$$$ (players $$$1$$$ and $$$3$$$). Each of them receives $$$\left\lfloor {\frac{X}{k}} \right\rfloor=\left\lfloor {\frac{15}{2}} \right\rfloor=7$$$ units of gold.
- Round 2: Chooses option $$$2$$$. Therefore, he receives $$$Y=8$$$ units of gold.
- Round 3: Chooses option $$$1$$$. Since Inés also chooses option $$$1$$$, ultimately all four players choose this same option. Each of them receives $$$\left\lfloor {\frac{16}{4}} \right\rfloor=4$$$ units of gold.
In total, player $$$1$$$ receives $$$7 + 8 + 4 = 19$$$ units of gold.
Jaimito is a manufacturer of educational children's games. His latest game contains a certain number of wooden blocks that can be placed on a board forming $$$T$$$ towers of blocks. Each tower is in a specific position on the board, designated by a different integer between $$$1$$$ and $$$T$$$ inclusive. These positions can be empty, meaning that some of the towers may not contain blocks.
The blocks in a tower are stacked one on top of the other, so that each block in that tower has exactly one block underneath and exactly one block on top, except for the bottom block which has the board underneath, and the top block which has nothing on top.
Each block has a certain weight that is a positive integer. As part of the game rules, the stability rule must always be respected: it is not allowed for a block to be placed on top of another block with strictly smaller weight. In other words, the blocks of each tower, when viewed from the board upwards, are ordered in a non-increasing manner by weight. A configuration of blocks that respects the stability rule is called stable. The following figure shows two stable configurations for a game with $$$T=3$$$ towers.
A permitted move in the game consists of taking the top block from a non-empty tower and placing it on top of another (possibly empty) tower, always respecting the stability rule.
Jaimito needs your help to determine, given two stable configurations, an initial and a final one, whether it is possible to reach the final configuration from the initial configuration through zero or more permitted moves.
The first line contains an integer $$$T$$$ ($$$1 \leq T \leq 2 \cdot 10^5$$$) indicating the number of towers.
Each of the following $$$2T$$$ lines describes a tower. The first $$$T$$$ lines describe the towers of the initial configuration, in order from tower $$$1$$$ to tower $$$T$$$, while the remaining $$$T$$$ lines describe the towers of the final configuration, in the same order.
The line describing each tower contains an integer $$$K \ge 0$$$ followed by $$$K$$$ integers $$${X_1}, {X_2}, \ldots, {X_K}$$$ ($$$1 \leq X_i \leq 10^9$$$), indicating that the tower contains $$$K$$$ blocks and that $$$X_i$$$ is the weight of the $$$i$$$-th block of the tower, counting from the board upwards.
It is guaranteed that the initial and final configurations are stable, and that neither has more than $$$2 \cdot 10^5$$$ blocks.
A line with the uppercase letter "S" if it is possible to reach the final configuration from the initial configuration through zero or more permitted moves, or the uppercase letter "N" otherwise.
4 2 3 2 1 4 2 3 1 1 4 0 2 2 1 2 3 3 2 4 4
S
3 2 6 5 2 6 3 1 8 1 6 0 3 8 6 5
N
1 0 0
S
In the first example, we can make the following sequence of permitted moves to reach from the initial configuration to the final configuration:
The moves are:
- Move the block with weight $$$4$$$ from the second tower to the fourth.
- Move the block with weight $$$2$$$ from the first tower to the second.
- Move the block with weight $$$1$$$ from the third tower to the second.
- Move the block with weight $$$3$$$ from the first tower to the third.
In the statement, there is an image that shows the initial configuration and the final configuration corresponding to the second example.
Marty returned to the future and found Dr. Brown working on the innovative Kuantum resonance networks, a cutting-edge technology for communications based on the latest advances in quantum physics.
These networks are made up of $$$N$$$ Kuantum Processing Units (KPU), numbered from $$$1$$$ to $$$N$$$. The KPUs are connected in a tree structure, using bidirectional quantum cables. The KPU number $$$i$$$ operates at a specific frequency $$$F_i$$$.
According to the Kuantum protocol, the transmission of a message from a source KPU $$$X$$$ to a destination KPU $$$Y$$$ is divided into exactly three phases, which occur in the following order:
- Preparation: the message is transmitted instantaneously from $$$X$$$ to any KPU $$$w$$$ that operates at the same frequency as $$$X$$$, that is, with $$$F_X = F_w$$$.
- Transit: the message is transmitted from $$$w$$$ to any KPU $$$z$$$ such that $$$F_z = F_Y$$$, taking one unit of time for each cable used.
- Delivery: the message is transmitted instantaneously from $$$z$$$ to $$$Y$$$.
The following figure shows an example of transmission, in which a message from $$$X$$$ to $$$Y$$$ requires $$$4$$$ units of time. Remember that $$$F_X = F_w$$$ and $$$F_z = F_Y$$$.
Dr. Brown has finished building his first Kuantum network, and he needs to verify the efficiency of communication between different KPUs. As members of his team, you must write a program that can answer a series of queries. In each query, a source KPU $$$X$$$ and a destination KPU $$$Y$$$ are indicated, and you must calculate the minimum time required to transmit a message from $$$X$$$ to $$$Y$$$.
The first line contains an integer $$$N$$$ ($$$1 \leq N \leq 10^5$$$), indicating the number of KPUs in the network. Each KPU is identified by a distinct integer between $$$1$$$ and $$$N$$$.
The second line contains $$$N$$$ integers $$${F_1}, {F_2}, \ldots, {F_N}$$$ ($$$1 \leq F_i \leq N$$$), indicating that the frequency of KPU $$$i$$$ is $$$F_i$$$.
Each of the following $$$N-1$$$ lines contains two integers $$$U$$$ and $$$V$$$ ($$$1 \leq U, V \leq N$$$ and $$$U \neq V$$$), indicating that there is a bidirectional cable connecting the KPUs $$$U$$$ and $$$V$$$. It is guaranteed that the network has a tree structure.
The next line contains an integer $$$C$$$ ($$$1 \leq C \leq 10^5$$$) representing the number of queries that need to be answered.
Each of the following $$$C$$$ lines describes a query with two integers $$$X$$$ and $$$Y$$$ ($$$1 \leq X, Y \leq N$$$), indicating respectively the source and destination KPUs for each query.
One line for each of the $$$C$$$ queries, with the corresponding answer, in the order in which the queries appear in the input.
9 1 2 2 3 3 4 4 4 4 1 7 1 3 4 8 7 2 5 6 9 2 8 9 6 2 7 1 1 2 1 1 3 1 4 4 5 4 3 5 3
0 1 1 4 0 2 2
In the second query of the example, the source KPU is $$$X=2$$$. During the preparation phase, the message is transmitted instantaneously to KPU $$$w=3$$$ since $$$F_2=F_3=2$$$. In the transit phase, it is transmitted to KPU $$$z=1$$$ in one unit of time (traversing the cable connecting KPUs $$$w=3$$$ and $$$z=1$$$). In the delivery phase, the message is transmitted instantaneously to the destination KPU $$$Y=1$$$, which in this case coincides with $$$z$$$. The total time is $$$1$$$ for this query.
In the fourth query, the optimal transmission is
which uses KPUs $$$w=1$$$ and $$$z=5$$$, taking $$$4$$$ units of time. A dashed arrow indicates instantaneous transmission in the preparation or delivery phases, while a solid arrow indicates the use of a cable in the transit phase. Note that it is not possible to transmit the message with
in $$$2$$$ units of time, since according to the three-phase protocol, the instantaneous transmission from KPU $$$7$$$ to KPU $$$8$$$ is not applicable in the transit phase.
Marcos has a piece of land that can contain several lakes, and he wants to take advantage of these bodies of water to place some boats. The land can be represented as a grid of dimensions $$$1 \times N$$$ where each of its $$$N$$$ cells is entirely made of either land or water. Each boat that can be obtained in the boat market has a length $$$k$$$ for some positive integer $$$k$$$, and can be placed on the land occupying $$$k$$$ consecutive water cells. It is not possible to place more than one boat in the same water cell.
Marcos can obtain as many boats as he wants, of any length he wants. However, for the landscape to look aesthetic and diverse, Marcos decided that all the boats he places on the land must have different lengths and be arranged in strictly increasing order from left to right.
For each boat that Marcos manages to place, he earns a profit $$$G$$$. However, Marcos is not satisfied with the distribution of his land, so he is willing to excavate some land cells so that they become water and thus be able to place more boats. Excavating the $$$i$$$-th cell of the grid has a variable cost $$$T_i$$$, since not all cells have the same amount of ground to excavate.
If Marcos wisely chooses which cells to excavate and where to place the boats, what is the maximum net profit he can achieve?
The first line contains two integers $$$N$$$ ($$$1 \leq N \leq 10^5$$$) and $$$G$$$ ($$$1 \leq G \leq 10^9$$$), which indicate respectively the number of cells of the land and the profit for placing a boat.
The second line contains $$$N$$$ integers $$${T_1}, {T_2}, \ldots, {T_N}$$$ ($$$0 \leq T_i \leq 10^9$$$), such that $$$T_i=0$$$ if the $$$i$$$-th cell is water, or $$$T_i \ge 1$$$ if the cell is land and its excavation cost is $$$T_i$$$.
A line with an integer, the maximum net profit that Marcos can achieve.
6 5 0 8 0 4 0 6
6
4 1 2 2 2 2
0
10 2 0 0 0 0 8 0 0 7 0 0
4
1 314159265 0
314159265
In the first example, Marcos can excavate the fourth cell with cost $$$T_4=4$$$. In this case, he can place a boat of length $$$1$$$ in the first water cell, and another of length $$$3$$$ in the remaining water cells. His total profit for placing $$$2$$$ boats is $$$2 \cdot G = 2 \cdot 5 = 10$$$. Considering the excavation cost, his net profit is $$$10 - 4 = 6$$$.
In the second example, it is better for Marcos not to place any boats.
Marco Molo is a famous walking traveler in the distant kingdom of Mlogomia. The kingdom has $$$N$$$ cities and $$$M$$$ bidirectional paths. Each path connects two different cities, allowing direct walking from one to the other. The geometry in Mlogomia is extremely peculiar, and all paths have exactly the same length.
Marco intends to travel from Factorial to Primorial, the two most important cities in Mlogomia. Each day he is willing to walk between $$$1$$$ and $$$K$$$ paths, having to rest at night to continue his journey the next day.
Marco does not care about the total number of paths he has to walk to go from Factorial to Primorial, but he does want to ensure that he uses the least number of days possible. How many different ways can Marco make his journey? Since this value can be very large, it must be calculated modulo $$$998244353$$$.
A daily walk of Marco can be described with a sequence of $$$t+1$$$ cities, such that $$$1 \le t \leq K$$$ and there is a path between each city and the next. Two daily walks are different if they differ in the number of cities, or if the $$$i$$$-th city is not the same in both walks.
A journey of Marco can be described with a sequence of $$$d$$$ daily walks, such that the first walk starts in Factorial, the last walk ends in Primorial, and each walk ends in the same city where the next one begins. Moreover, $$$d$$$ is minimal, meaning it is impossible to travel from Factorial to Primorial with fewer walks. Two journeys are different if the $$$i$$$-th daily walk of one differs from the corresponding walk in the other.
The first line contains three integers $$$N$$$, $$$M$$$, and $$$K$$$ ($$$2 \leq N \leq 2000$$$ and $$$1 \leq M,K \leq 2000$$$), which indicate respectively the number of cities in Mlogomia, the number of paths, and the maximum number of paths Marco can walk in a day. Each city is identified by a distinct integer between $$$1$$$ and $$$N$$$, with Factorial being city $$$1$$$ and Primorial being city $$$2$$$.
Each of the following $$$M$$$ lines describes a path by two integers $$$U$$$ and $$$V$$$ ($$$1 \leq U,V \leq N$$$ and $$$U \neq V$$$), which indicate the two cities that this path connects. It is guaranteed that there are no two different paths connecting the same pair of cities.
A single line with one integer, indicating the number of different journeys Marco can make, modulo $$$998244353$$$.
4 3 2 1 3 3 4 4 2
2
4 3 5 1 3 3 4 4 2
4
10 1 100 1 5
0
In the first example, the two possible journeys are as follows:
- The first day's walk is $$$1, 3$$$ and the second is $$$3, 4, 2$$$.
- The first day's walk is $$$1, 3, 4$$$ and the second is $$$4, 2$$$.
For the second example, one of the $$$4$$$ possible journeys uses a single daily walk $$$1, 3, 4, 3, 4, 2$$$. Notice that it is valid to repeat cities in a walk.
In the Patagonian Andean forest, there are numerous species of trees. One of them is Nothofagus antarctica, colloquially known as ñire.
To prevent the logging of the native forest, the local government wants to enclose $$$N$$$ specimens of this species. To this end, the government created a plan that shows the position of each tree they want to protect.
The fence that is to be built must divide the plan into two regions, an interior and an exterior. The interior must contain all the ñires, and to prevent parts of the tree from being outside the fence, each ñire must be at least $$$1$$$ unit away from the fence. Furthermore, to make it more attractive for tourists, it has been decided that the sides of the fence must be parallel to the Cartesian axes represented in the plan.
What is the minimum length that the fence must have to meet all these conditions?
The first line contains an integer $$$N$$$ ($$$1 \leq N \leq 10^5$$$) indicating the number of ñires that the local government wishes to protect.
Each of the following $$$N$$$ lines describes a ñire with two integers $$$X$$$ and $$$Y$$$ ($$$1 \leq X, Y \leq 10^8$$$), which indicate the coordinates of the tree's location on the plan. All these locations are different.
A single line with an integer indicating the minimum length of the fence to be constructed.
5 2 2 4 3 5 3 3 4 4 5
20
1 2 5
8
The following figure illustrates a possible fence of length $$$20$$$ for the first example. The triangles represent the locations of the ñires.
