Jordan Belfort has been released from prison and has decided to conquer Wall Street once again! UAM, the main organization for the extraction of ancient artifacts, also eagerly awaited his return. They contacted Jordan, the world's foremost financial mind, on the same day with the following task:
All over the world, there are plenty of numismatists with a penchant for rare Incan coins. UAM has accumulated a decent number of these coins over time. Now, the organization wants to send these coins to each of its clients.
As it turns out, each client of UAM has apparently helped them with financial savings as well. For that reason, UAM also needs to send some amount of dollars to each of them. Of course, the organization wants to send as many dollars as possible, but its main goal is to deliver a fixed number of coins to each client, and to ensure that the couriers do not raise suspicion at the airport customs control.
To start with the task, Jordan has decided how the money will be transported: the ancient coins will be placed in separate square containers which, in turn, will then be neatly arranged inside plastic bags, together with stacks of dollar bills. The bags will then be vacuum-sealed, rolled into rolls and transported this way.
To avoid raising suspicion at customs, there should be no correlation between the couriers. With clothing, appearance, and voice, Belfort knows very well how to handle it, he has pulled it off more than once. But when it comes to the money being arranged differently in the bags... the ingenious magnate pondered.
He is curious about how many rolls he can prepare so that the money is arranged differently in each pair. He has hired you, experienced programmers, to write a program that will help him figure this out.
Belfort has an infinite number of plastic bags of the same size. Their dimensions are $$$N$$$ united meters in height and $$$m$$$ united meters in width. He also has an infinite number of containers measuring $$$1 \times 1$$$ united square meters.
UAM has an infinite amount of dollars, and UAM also wants each client to receive exactly $$$K$$$ coins. At the time of Belfort's release from prison, the dollar bills have dimensions of $$$1 \times 2$$$ united square meters.
You need to find out how many different ways there are to arrange the money tightly in a bag so that there are exactly $$$K$$$ containers with coins among them. The stacks of bills can only be arranged horizontally or vertically. Belfort claims that it is impossible to vacuum-seal plastic bags safely (for the money, undoubtedly) if there are empty spaces, therefore, each bag must be packed to the brim, so packings with empty spaces not filled with money are not allowed!
Since the number of people who can be Belfort's accomplices on Earth is limited, the answer must be calculated modulo $$$2^{32}$$$.
The single line of input contains three space-separated integers $$$N$$$, $$$m$$$, and $$$K$$$ ($$$1 \leq N \leq 10^5$$$, $$$1 \leq m \leq 4$$$, $$$0 \leq K \leq 100$$$).
You need to output the number of different ways to arrange the containers with coins of size $$$1 \times 1$$$ and stacks of dollar bills of size $$$1 \times 2$$$ vertically or horizontally in a bag of size $$$N \times m$$$ so that there are exactly $$$K$$$ containers with coins.
Two ways are considered different if there exists a $$$1 \times 1$$$ square that either is filled with a stack of bills horizontally in one way and vertically in the other, or this square contains a coin in one way and a stack of bills in the other.
Since the answer can be quite large, you have to calculate it modulo $$$2^{32}$$$.
2 3 2
11
Let us start by listing all possible ways to arrange the containers:
$$$$$$ \left\lvert \begin{matrix} \hline x & x & . \\ . & . & . \\ \hline \end{matrix} \right\rvert \; \left\lvert \begin{matrix} \hline x & . & x \\ . & . & . \\ \hline \end{matrix} \right\rvert \; \left\lvert \begin{matrix} \hline x & . & . \\ x & . & . \\ \hline \end{matrix} \right\rvert \; \left\lvert \begin{matrix} \hline x & . & . \\ . & x & . \\ \hline \end{matrix} \right\rvert \; \left\lvert \begin{matrix} \hline x & . & . \\ . & . & x \\ \hline \end{matrix} \right\rvert $$$$$$
$$$$$$ \left\lvert \begin{matrix} \hline . & x & x \\ . & . & . \\ \hline \end{matrix} \right\rvert \; \left\lvert \begin{matrix} \hline . & x & . \\ x & . & . \\ \hline \end{matrix} \right\rvert \; \left\lvert \begin{matrix} \hline . & x & . \\ . & x & . \\ \hline \end{matrix} \right\rvert \; \left\lvert \begin{matrix} \hline . & x & . \\ . & . & x \\ \hline \end{matrix} \right\rvert $$$$$$
$$$$$$ \left\lvert \begin{matrix} \hline . & . & x \\ x & . & . \\ \hline \end{matrix} \right\rvert \; \left\lvert \begin{matrix} \hline . & . & x \\ . & x & . \\ \hline \end{matrix} \right\rvert \; \left\lvert \begin{matrix} \hline . & . & x \\ . & . & x \\ \hline \end{matrix} \right\rvert $$$$$$
$$$$$$ \left\lvert \begin{matrix} \hline . & . & . \\ x & x & . \\ \hline \end{matrix} \right\rvert \; \left\lvert \begin{matrix} \hline . & . & . \\ x & . & x \\ \hline \end{matrix} \right\rvert $$$$$$
$$$$$$ \left\lvert \begin{matrix} \hline . & . & . \\ . & x & x \\ \hline \end{matrix} \right\rvert $$$$$$
Now, let us try to place the dollars in each arrangement. In the end, we get the following ways:
$$$$$$ \left\lvert \begin{matrix} \hline x & x & v \\ h & h & v \\ \hline \end{matrix} \right\rvert \; \left\lvert \begin{matrix} \hline x & v & v \\ x & v & v \\ \hline \end{matrix} \right\rvert \; \left\lvert \begin{matrix} \hline x & h & h \\ x & h & h \\ \hline \end{matrix} \right\rvert \; \left\lvert \begin{matrix} \hline x & h & h \\ h & h & x \\ \hline \end{matrix} \right\rvert \; \left\lvert \begin{matrix} \hline v & x & x \\ v & h & h \\ \hline \end{matrix} \right\rvert \; \left\lvert \begin{matrix} \hline v & x & v \\ v & x & v \\ \hline \end{matrix} \right\rvert $$$$$$
$$$$$$ \left\lvert \begin{matrix} \hline h & h & x \\ x & h & h \\ \hline \end{matrix} \right\rvert \; \left\lvert \begin{matrix} \hline v & v & x \\ v & v & x \\ \hline \end{matrix} \right\rvert \; \left\lvert \begin{matrix} \hline h & h & x \\ h & h & x \\ \hline \end{matrix} \right\rvert \; \left\lvert \begin{matrix} \hline h & h & v \\ x & x & v \\ \hline \end{matrix} \right\rvert \; \left\lvert \begin{matrix} \hline v & h & h \\ v & x & x \\ \hline \end{matrix} \right\rvert $$$$$$
You are given an undirected tree with $$$n$$$ vertices. Each vertex $$$v$$$ has a value $$$a_v$$$. The cost of any subtree $$$T$$$ is defined as: $$$$$$\displaystyle \mathrm{cost}(T) = \mathrm{size}(T) \cdot \sum_{v \in T} a_v\text{,}$$$$$$ where $$$\mathrm{size}(T)$$$ is the size of subtree $$$T$$$.
A vertex $$$u$$$ is removed from the original tree along with all its incident edges. Thus the graph transforms into multiple trees.
Your task is to find the maximum possible total cost of the resulting trees, given that you can choose the vertex $$$u$$$ yourself.
The first line of input contains an integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$).
The second line of input contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-2 \cdot 10^5 \le a_i \le 2 \cdot 10^5$$$), where $$$a_i$$$ corresponds to the value for vertex $$$i$$$.
The third line of input contains $$$n - 1$$$ integers $$$p_2, p_3, \ldots, p_n$$$ ($$$1 \le p_i \lt i$$$). They indicate that there is an edge in the tree between $$$2$$$ and $$$p_2$$$, an edge between $$$3$$$ and $$$p_3$$$, ..., an edge between $$$n$$$ and $$$p_n$$$.
It is guaranteed that the given edges form a tree.
Output a single integer: the maximum possible total cost of the resulting trees if you can choose any vertex as the vertex $$$u$$$.
21 21
2
3-1 -1 21 1
2
41 -1 -1 -11 1 1
-3
41 -1 -1 -11 2 3
-1
A space explorer plans to go on an expedition to a remote planet. In his path, there are several space objects given in order of visiting them, each of which has its own unique value for exploration. Each object requires a certain amount of energy (in units) and time (in days) for the study.
However, the explorer has a limitation on the amount of available energy $$$K$$$ and time $$$M$$$ to complete the mission. It is necessary to create an optimal sequence of visiting objects that maximizes the scientific value of the expedition, taking into account the constraints on energy and time.
The first line contains three space-separated integers: the number of space objects $$$1 \le N \le 100$$$ and the limitations on energy $$$1 \le K \le 100$$$ and time $$$1 \le M \le 100$$$.
Each of the next $$$N$$$ lines described an object and contains three integers: its scientific value $$$0 \le V \le 150$$$, the amount of energy $$$1 \le F \le 50$$$ required, and the time in days $$$1 \le T \le 20$$$ needed for exploration.
The first line should contain a number: the maximum scientific value of the exploration. The second line should contain the sequence of visiting objects.
It is assumed that the objects are numbered sequentially, starting from one. The explorer can only visit them in the specified order.
If it is not possible to explore any object, output 0.
If there are several possible solutions, output any one of them.
5 60 10100 20 380 17 250 10 4120 25 460 12 2
280 1 4 5
2 12 1067 15 9120 4 15
0
4 40 3030 7 1050 16 1280 12 2015 5 7
110 1 3
Consider a rectangular field of size $$$m \times n$$$. In the upper left square with coordinates $$$(1, 1)$$$, the starting point, there is a giraffe. It wants to get to the lower right square with coordinates $$$(m, n)$$$: the destination. Each square of the field is characterized by an integer: the number of trees in it.
The giraffe can make two types of moves: down by $$$k$$$ squares and right by $$$1$$$ square; or right by $$$k$$$ squares and down by $$$1$$$ square. The giraffe wants to traverse the field from the starting square to the destination. At the end of each move, the giraffe eats the leaves on the trees at the square where it arrived. The giraffe does not eat anything at the starting square. On every even move, the giraffe feels hungry and eats $$$3t$$$ leaves, and on every odd move, it feels full and eats only $$$t$$$ leaves, where $$$t$$$ is the number of trees on the square. Moves are numbered starting from 1.
Determine the maximum number of leaves the giraffe can eat on its journey.
The first line contains two integers separated by a space: $$$m$$$ and $$$n$$$ ($$$1 \le m, n \le 100$$$).
The second line contains an integer $$$k$$$ ($$$1 \le k \le \min (m, n)$$$).
Each of the next $$$m$$$ lines contains $$$n$$$ numbers; the $$$j$$$-th number in the $$$i$$$-th of these lines is the number of trees in the square $$$(i, j)$$$, and it is an integer in the range from $$$0$$$ to $$$100$$$, inclusive.
Output a single integer: the maximum number of leaves the giraffe can eat on a path from the starting square to the destination. If there are no such paths, output $$$-1$$$.
2 211 11 1
1
3 521 2 0 3 12 4 5 7 83 0 7 1 0
5
3 211 32 41 2
-1
Petya got some unusual dice as a gift: each die has 26 faces containing all 26 small letters of the English alphabet, one letter on each face. Petya wanted to play a game: initially, he arranged $$$n$$$ dice in a row, forming a certain string, and now he wants to turn it into his favorite string. To do this, Petya makes moves: in one move, Petya can flip any die, changing the corresponding letter of the string to any other. Petya also has a big fluffy Cat who can make moves instead of him. Depending on the Cat's mood, it can help Petya by immediately flipping the dice to form Petya's favorite string in one move, or the Cat can do the opposite: flip the dice so that the resulting string differs from Petya's favorite string in every letter. A move by any player is possible only if it somehow changes the string of dice. The players can make moves in any order.
Since Petya needs to give a report on physical education, there is time only for $$$m$$$ moves in the game. Petya now wonders how many different games can occur if after exactly $$$m$$$ moves, the dice should form his favorite string. Since the number of games can be very large, Petya is only interested in the remainder of dividing this number by $$$9! = 362\,880$$$. Help Petya find this value.
Note that two games are different if there is a move number that Petya made in one game, and the Cat made in the other, or if there is a move number after which the strings on the dice were different.
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 10\,000$$$ and $$$0 \leq m \leq 10\,000$$$). The second line contains the initial string that was obtained from the dice before the start of the game, and the third line contains Petya's favorite string. It is guaranteed that both strings have a length of $$$n$$$ and consist only of small letters of the English alphabet.
Output a single integer: the answer to the problem.
4 5starwars
111957
4 1spbuspbu
0
Lolek loves to play the lottery and to cheat. And recently he found a loophole in the lottery ticket submission system! There is a delay between announcement of the winning numbers and the end of ticket submission.
The rules of the lottery are simple as always. The participant buys a lottery ticket on which $$$n$$$ positive integers are written. Then on a certain day, $$$n$$$ positive integers are announced: the winning numbers. All participants will see them as an array of integers $$$b$$$. Also, the prizes are announced in advance: if the $$$i$$$-th element of the participant's ticket matches the $$$i$$$-th element of the winning ticket, the participant receives $$$c_i$$$ coins.
Lolek decided to use the loophole in the system for his enrichment. He has an official template for a lottery ticket, which is an array $$$a$$$ of size $$$n$$$ filled with ones. Lolek also has a device for changing the digits on the ticket.
Unfortunately, the device is homemade, and works as follows. Lolek can choose two integers $$$i$$$ ($$$1 \leq i \leq n$$$) and $$$z$$$ ($$$z \gt 0$$$) and increase $$$a_i$$$ by $$$\left\lfloor \frac{a_i}{z} \right\rfloor$$$ (the quotient of dividing $$$a_i$$$ by $$$z$$$, rounded down). Lolek can choose the same $$$i$$$ for operations as many times as he wants.
But this process is not fast, and the time for the loophole is limited. In total, Lolek will be able to perform no more than $$$k$$$ operations. Therefore, he asked you to maximize his winnings.
Your task is to determine the maximum number of coins that Lolek can receive by performing no more than $$$k$$$ operations.
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^3$$$): the number of integers on the lottery ticket.
The second line contains a single integer $$$k$$$ ($$$0 \leq k \leq 10^6$$$): the maximum number of operations.
The third line contains $$$n$$$ integers $$$b_i$$$ ($$$1 \leq b_i \leq 10^3$$$): the winning lottery ticket.
The fourth line contains $$$n$$$ integers $$$c_i$$$ ($$$0 \leq c_i \leq 10^6$$$): the number of coins received if the numbers match.
A single integer: the maximum number of coins that can be obtained by performing no more than $$$k$$$ operations.
331 2 33 2 1
6
302 3 41 1 1
0
597 5 3 5 32 5 3 2 5
13
At the Institute of Marine Biology, several new species of deep-sea mollusks have been discovered. Now, the researchers are trying to understand their genealogy. To do this, lab assistant Petya extracted a specific segment of the genome from each species of mollusk, and lab assistant Vasya constructed $$$T$$$ hypothetical partial evolutionary trees based on external characteristics.
The partial evolutionary trees constructed by Vasya are rooted trees in which each vertex corresponds to a particular species. The root corresponds to the common ancestor, and the leaves correspond to modern species.
For each species, the researchers observe the same segment of the genome which is represented as a string of characters A, G, C, and T (each character represents a nucleotide). It is known that all species have segments of the same length, but during evolution, some nucleotides may have been replaced by others (deletions and additions of nucleotides without replacement could not occur). Each of the modern species corresponds to one of $$$G$$$ segments of the genome extracted by Petya. The genome segments of the ancestor species are unknown.
From previous empirical observations, Petya and Vasya know that evolution is a slow process, and therefore, for each tree constructed by Vasya, they want to determine its minimum possible weight. The weight of an evolutionary tree is defined as the sum of the weights of its edges, and the weight of an edge is the number of nucleotides that changed between the ancestor and descendant species.
The researchers themselves could not solve such a problem, so they ask for your help!
The first line contains an integer $$$G$$$ ($$$0 \le G \le 500$$$): the number of genome segments extracted by Petya.
The following $$$G$$$ lines contain these segments, one per line. The segments are given as strings of characters A, G, C, and T. It is guaranteed that the lengths of all strings are the same and do not exceed $$$500$$$.
Next, a separate line contains an integer $$$T$$$ ($$$0 \le T \le 100$$$): the number of partial evolutionary trees constructed by Vasya. Then there are $$$T$$$ descriptions of these trees.
The first line of a tree description contains two integers, $$$N$$$ and $$$M$$$ ($$$0 \le M \le N \le 500$$$): the number of vertices and leaves in the tree, respectively.
If $$$N$$$ is positive, the next $$$N - 1$$$ lines contain the parents of the vertices: the $$$i$$$-th of these lines contains the parent of vertex $$$i + 1$$$. The first vertex is the root and has no parent.
Each of the last $$$M$$$ lines of a description contain two integers, $$$v$$$ and $$$g$$$: the number of the vertex of the tree that is a leaf and the number of the corresponding genome from Petya's library. Each leaf of the tree appears in these lines exactly once. The root is considered a leaf when it is the only vertex of the tree.
For each of the partial evolutionary trees constructed by Vasya, you need to output only one integer: the minimum possible weight of this tree.
2ACTC14 21223 14 2
1
3AGGTGC25 311223 14 25 33 2112 23 3
3 1
You are given a sequence of distinct integers and a set of allowed differences. Your task is to find the length of the longest increasing subsequence in which the difference between any two adjacent elements is one of the allowed differences. For example, if the allowed differences are $$$1$$$ and $$$3$$$, then the subsequence $$$1, 4, 5, 8$$$ will satisfy the condition, while the sequence $$$1, 2, 4$$$ will not, as the difference between the second and third element is $$$2$$$.
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 10^6$$$ and $$$1 \le k \le 10$$$): the number of elements in the sequence and the number of allowed differences, respectively. The second line contains $$$n$$$ distinct integers $$$s_i$$$ ($$$1 \le s_i \le 10^9$$$): the elements of the sequence. The third line contains $$$k$$$ distinct integers $$$d_i$$$ ($$$1 \le d_i \le 10^9$$$): the allowed differences.
One positive integer: the length of the longest increasing subsequence with allowed differences.
7 22 5 6 3 8 10 93 1
4
9 22 5 6 3 8 10 9 7 121 3
5
You are given an undirected tree with $$$n$$$ vertices. Find the sum of lengths of all simple paths in it.
The length of a simple path between vertices $$$u$$$ and $$$v$$$ is the minimum number of edges that need to be traversed to go from $$$u$$$ to $$$v$$$.
The first line contains an integer $$$n$$$ ($$$1 \le n \le 300\,000$$$).
The next line contains $$$n - 1$$$ integers $$$p_2, p_3, \ldots, p_n$$$ ($$$1 \le p_i \lt i$$$). They mean that there is an edge in the tree between $$$2$$$ and $$$p_2$$$, an edge between $$$3$$$ and $$$p_3$$$, ..., an edge between $$$n$$$ and $$$p_n$$$. It is guaranteed that the given edges form a tree.
Output a single integer: the sum over all $$$(u, v)$$$, where $$$1 \le u \le v \le n$$$, of the lengths of simple paths between $$$u$$$ and $$$v$$$.
51 1 3 1
18