Cat Miston started downloading the series "Police Cat". The series consists of $$$n$$$ episodes, where the $$$i$$$-th episode is currently being downloaded at a speed of $$$v_i$$$ and the browser indicates that the $$$i$$$-th episode will be downloaded exactly in $$$t_i$$$ minutes, which is not entirely true.
The browser calculates the time based on the assumption that the download speed of the $$$i$$$-th episode will not change. However, when a certain episode is completely downloaded, the download speed of other episodes increases (there are no other reasons for changes in the download speed of any episode). At the same time, the ratios of download speeds of the remaining episodes remain unchanged. In other words, if $$$v_i^t$$$ is the download speed of the $$$i$$$-th episode at time $$$t$$$, then for any $$$i$$$ and $$$j$$$ it holds that for all $$$t$$$ less than the moment of download completion of the $$$i$$$-th or $$$j$$$-th episode the value of $$$\frac{v_i^t}{v_j^t}$$$ is the same.
There is no other network load besides downloading the $$$n$$$ episodes. In other words, the total download speed $$$\sum\limits_{i=1}^n v_i^t$$$ is constant (the same at any moment $$$t$$$).
Determine the actual time at which each episode will be fully downloaded.
The first line of input contains an integer $$$n$$$ — the number of episodes in the series ($$$1 \le n \le 3 \cdot 10^5$$$).
Each of the following $$$n$$$ lines contains two integers $$$v_i$$$ and $$$t_i$$$ — the current download speed and the download time assumed by the browser for the $$$i$$$-th episode ($$$1 \le v_i, t_i \le 10^{18}$$$; $$$\sum\limits_{i=1}^n v_i \le 10^{18}$$$).
For each episode output the actual time it will take to download it.
Your answer will be accepted if its absolute or relative error does not exceed $$$10^{-6}$$$. Formally, let your answer be $$$a$$$ and the jury's answer be $$$b$$$. Your answer will be accepted if $$$\frac {|a - b|}{\max(1, b)} \le 10^{-6}$$$.
Points for each subtask are awarded only if all tests for that subtask and the necessary subtasks are successfully passed.
| Subtask | Points | Constraints | Required subtasks | Feedback policy |
| 0 | – | examples | full | |
| 1 | 5 | $$$n \le 2$$$ | full | |
| 2 | 5 | $$$n \le 3$$$ | 0, 1 | first error |
| 3 | 15 | $$$n, v_i, t_i \le 3000$$$ | 0 | first error |
| 4 | 20 | $$$n \le 3000$$$ | 0 – 3 | first error |
| 5 | 20 | $$$v_i = v_j$$$ for all $$$i$$$, $$$j$$$ | first error | |
| 6 | 15 | $$$n \le 30\,000$$$ | 0 – 4 | first error |
| 7 | 5 | $$$t_i \le 10^{9}$$$ for all $$$i$$$; $$$\sum\limits_{i=1}^n v_i \le 10^{9}$$$ | 0, 3 | first error |
| 8 | 15 | no additional constraints | 0 – 7 | first error |
22 43 5
4 4.6
31 45 22 3
2.5 2 2.375
Students of Innopolis have come up with a new board game. The game is cooperative, meaning that players must work together to achieve a specific goal. One of the phases of the game involves distributing resources.
The game is designed for exactly $$$n$$$ players, and during the resource distribution phase $$$n$$$ cards with integers, ordered in non-decreasing order, are distributed among the players in order. Let $$$a_i$$$ be the number received by the $$$i$$$-th player (then $$$a_i \le a_{i+1}$$$ for all $$$i \le n - 1$$$). We call the set of three numbers $$$\{a_{i-1}, a_i, a_{i+1}\}$$$, i.e., the number written on his card and the two numbers of his neighbors, the options of the $$$i$$$-th player. The players sit in a circle, so for the first player instead of $$$a_{i-1}$$$ the first option will be $$$a_n$$$, and for the $$$n$$$-th player instead of $$$a_{i+1}$$$ the third option will be $$$a_1$$$.
Each player must choose exactly one of the available options and receive exactly that many resources from the bank. Then, the bitwise "AND" operation (the '&' operation) is performed on the two remaining options and the resulting number of points is added to the players' score for this round. For example, if a player has the options $$$\{2, 5, 11\}$$$ and chooses to take $$$5$$$ resources, he gets $$$2\ \&\ 11 = 0010_2\ \&\ 1011_2 = 2$$$ points. To successfully move on to the next phase of the game:
- the total amount of resources taken by the players must not exceed $$$\left(\sum\limits_{i=1}^n a_i\right) + X$$$, i.e., it must not exceed the amount of resources in the case where each player chooses his own $$$a_i$$$ by more than $$$X$$$;
- the total number of points earned must be maximized.
Help the players make their choices and successfully move on to the next phase. Note that it is not necessary to maximize the amount of resources taken within this upper limit; only the number of points needs to be maximized.
The first line of input contains two space-separated integers $$$n$$$ and $$$X$$$ — the number of players and the limit on the "extra" number of resources ($$$3 \le n \le 300$$$; $$$0 \le X \le 10^5$$$).
The second line contains $$$n$$$ space-separated integers $$$a_i$$$ — the values written on the cards given to the players ($$$0 \le a_i \le 10^5$$$; $$$a_i \le a_{i+1}$$$).
Output a single integer — the maximum number of points that the players can earn in this phase.
Points for each subtask are awarded only if all tests for that subtask and any necessary subtasks are successfully passed.
| Subtask | Points | Constraints | Necessary subtasks | Feedback policy |
| 0 | – | examples | full | |
| 1 | 13 | $$$n \le 14$$$ | 0 | full |
| 2 | 8 | $$$1 \le a_i \le 2$$$ for all $$$i$$$ | first error | |
| 3 | 10 | $$$a_i \le 3$$$ for all $$$i$$$ | 2 | first error |
| 4 | 12 | $$$a_n - a_1 \le 1$$$ | 2 | first error |
| 5 | 17 | $$$a_i\ \&\ a_{i+1} = a_i$$$ for all $$$i$$$ | first error | |
| 6 | 16 | $$$a_i \le 200$$$ for all $$$i$$$ | 0, 2, 3 | first error |
| 7 | 24 | no additional constraints | 0 – 6 | first error |
4 01 2 4 8
0
4 03 6 12 24
22
7 31 2 3 4 5 6 7
26
In the first example $$$a_i\ \&\ a_j = 0$$$ for $$$i \ne j$$$, so it is not possible to score any points.
In the second example the players should take resources in quantities of $$$24$$$, $$$3$$$, $$$6$$$, and $$$3$$$ respectively. Then the number of points is equal to $$$(3\ \&\ 6) + (6\ \&\ 12) + (12\ \&\ 24) + (12\ \&\ 24) = 2 + 4 + 8 + 8 = 22$$$.
The VK company urgently needed to move servers from one data center to another. This is a very important and urgent task, because not all services will function properly during their movement, but there is traffic on the roads today, so the servers will be moved by helicopter.
The map of the area over which the helicopter can move is a field consisting of $$$n$$$ rows and $$$m$$$ columns. The numbering of the rows goes from $$$1$$$ to $$$n$$$ from top to bottom, the numbering of the columns goes from $$$1$$$ to $$$m$$$ from left to right. Each cell represents a section of the same height. We will characterize the cell in row $$$i$$$ and column $$$j$$$ as $$$(i, j)$$$, and the minimum height at which the helicopter can safely fly in the corresponding section as $$$a_{i, j}$$$.
The servers need to be moved from cell $$$(1, 1)$$$ to cell $$$(n, m)$$$. The helicopter has already taken off and is at a height of $$$a_{1, 1}$$$. When the helicopter reaches cell $$$(n, m)$$$ at any allowed height, the route is considered completed.
At any given time the height at which the helicopter is located must be at least the minimum flight height for the current cell, that is, if we denote the height at which the helicopter is currently located in cell $$$(i, j)$$$ as $$$h$$$, it must satisfy $$$a_{i, j} \le h$$$. At the same time, from position $$$(i, j)$$$ at height $$$h$$$ the helicopter can:
- Fly to an adjacent cell, spending $$$h$$$ fuel for such a flight. The height will not change, and such a movement can only be made if the value of $$$a$$$ of the cell to which the flight is made is not greater than $$$h$$$.
- Increase its height by any $$$x \ge 0$$$. This action will consume $$$x$$$ fuel.
- Descend to any height not less than $$$a_{i,j}$$$. This will not consume fuel.
Due to weather conditions the helicopter may not be able to fly in all directions. The available directions are specified by the string $$$\mathtt{s}$$$. Each possible flight direction is represented by the following letters:
- 'R' — movement to the right from cell $$$(i, j)$$$ to cell $$$(i, j + 1)$$$ is allowed.
- 'L' — movement to the left from cell $$$(i, j)$$$ to cell $$$(i, j - 1)$$$ is allowed.
- 'U' — movement upwards from cell $$$(i, j)$$$ to cell $$$(i - 1, j)$$$ is allowed.
- 'D' — movement downwards from cell $$$(i, j)$$$ to cell $$$(i + 1, j)$$$ is allowed.
The height can always be increased or decreased. The movement directions 'R' and 'D' are always allowed. It is not possible to move beyond the field boundaries.
Programmers from VK quickly managed to determine the optimal fuel costs for the helicopter's route, even with such a large number of conditions on its movement. Can you do it too?
The first line contains two integers $$$n$$$ and $$$m$$$ — the dimensions of the field over which the helicopter moves ($$$1 \le n, m \le 1000$$$).
The second line contains a string $$$\mathtt{s}$$$, consisting of different characters 'L', 'R', 'U', and 'D' — the allowed flight directions ($$$2 \le |s| \le 4$$$). It is guaranteed that $$$\text{'\t{R}'}, \text{'\t{D}'} \in \mathtt{s}$$$.
Then there are $$$n$$$ lines with $$$m$$$ numbers each — the description of the field; the $$$i$$$-th line contains the numbers $$$a_{i,j}$$$ (the values of the minimum flight height) describing the $$$i$$$-th row of the field ($$$0 \le a_{i, j} \le 10^9$$$).
Output a single number — the minimum amount of fuel needed to travel from the position at height $$$a_{1,1}$$$ in cell $$$(1, 1)$$$ to cell $$$(n, m)$$$.
Points for each subtask are awarded only if all the tests of this subtask and the necessary subtasks are successfully passed. Here, $$$A$$$ denotes $$$\max\limits_{i,j} a_{i,j}$$$.
| Subtask | Points | Constraints | Necessary subtasks | Feedback policy |
| 0 | – | examples | full | |
| 1 | 5 | $$$n, m, A \le 10$$$ | 0 | full |
| 2 | 5 | $$$n, m \le 10^3$$$, $$$A \le 1$$$ | first error | |
| 3 | 5 | $$$n = 1$$$, $$$m \le 10^3$$$ | first error | |
| 4 | 7 | $$$n, m, A \le 500$$$, $$$\mathtt{s} = \text{"\t{RD}"}$$$ | first error | |
| 5 | 15 | $$$n, m \le 10^3$$$, $$$\mathtt{s} = \text{"\t{RD}"}$$$ | 4 | first error |
| 6 | 5 | $$$n, m \le 10^3$$$, and $$$a_{i - 1, j}, a_{i, j - 1} \le a_{i, j}$$$ | first error | |
| 7 | 15 | $$$n, m \le 10^3$$$, $$$\mathtt{s} = \text{"\t{LRD}"}$$$ | 5 | first error |
| 8 | 5 | $$$n, m, A \le 100$$$ | 0, 1 | first error |
| 9 | 13 | $$$n, m, A \le 500$$$ | 0, 1, 4, 8 | first error |
| 10 | 25 | no additional constraints | 0 – 9 | first error |
3 3LRDU1 2 44 4 41 1 1
13
5 5LRD0 10 0 0 00 0 0 10 010 10 10 10 09 5 3 2 03 3 2 5 0
30
In the first example the best path is to fly down to the limit, then right to the limit. The first two flights will have to be made at a height of $$$4$$$, the last two can be made at a height of $$$1$$$.
In the second example, the optimal path passes through cells with $$$a_{i,j} = 0$$$ and costs $$$0$$$ fuel, but for this it is necessary to move upwards, and upward movements are prohibited. In this case it is possible to fly over the "zero" cells through cell $$$(1, 2)$$$ or $$$(2, 4)$$$ with $$$a_{1,2} = a_{2,4} = 10$$$. To fly over either of them it will be necessary to ascend to a height of $$$10$$$ then perform two movements at this height.
In the data center of the University of Innopolis there are $$$n$$$ servers numbered with consecutive integers from $$$1$$$ to $$$n$$$. The servers are connected by $$$n - 1$$$ optical fiber cables in such a way that data transmission is possible between any two servers through one or multiple cables. In other words, the connections between servers form a tree.
Each optical fiber cable transmits data with a delay of $$$1$$$ unit of time, and the delay between two servers is equal to the distance in the tree between these servers.
It is required to select several servers for a distributed data storage system in such a way that the delay between any two servers in the system does not exceed $$$d$$$. Let the selected servers be $$$s_1, s_2, \ldots, s_k$$$, then the total delay of the system is the sum of delays between all $$$\frac{k (k - 1)}{2}$$$ pairs of servers $$$s_i$$$. Formally:
- $$$\mathtt{dist}(s_i, s_j) \le d$$$ must hold for any $$$i$$$ and $$$j$$$ (where $$$\mathtt{dist}$$$ is their distance in the tree);
- then the total delay of the system is $$$\sum\limits_{i \lt j} \mathtt{dist}(s_i, s_j)$$$.
Your task is to answer $$$q$$$ queries. Each query is defined by a number of a server $$$u$$$ and represents the following question: if a specific server $$$u$$$ is included in the data storage system, what is the maximum possible total delay of the system?
The first line of the input contains two integers $$$n$$$ and $$$d$$$ — the number of servers in the data center and the maximum allowed delay between two servers ($$$2 \le n \le 5 \cdot 10^5$$$; $$$0 \le d \le n - 1$$$).
Each of the next $$$n - 1$$$ lines contains two integers $$$a_i$$$ and $$$b_i$$$ — the numbers of two servers directly connected by the $$$i$$$-th optical cable ($$$1 \le a_i, b_i \le n$$$). It is guaranteed that it's possible to transmit data between any two servers through one or multiple consecutive cables.
The next line contains a single integer $$$q$$$ — the number of queries ($$$1 \le q \le 10$$$). In the $$$i$$$-th of the next $$$q$$$ lines, a single integer $$$u_i$$$ is given — the number of the server from the $$$i$$$-th query ($$$1 \le u_i \le n$$$).
For each query, output a single integer on a separate line — the maximum total delay of the system when the corresponding server is included in the data storage system.
Points for each subtask from 1 to 4 are awarded only if all tests for this subtask and the necessary subtasks are successfully passed.
Each test in subtasks 5 and 6 is scored independently and costs 3 points in subtask 5 or 2 points in subtask 6.
| Subtask | Points | Constraints | Necessary subtasks | Feedback policy |
| 0 | – | examples | full | |
| 1 | 12 | $$$n \le 15$$$ | 0 | first error |
| 2 | 11 | $$$d = n - 1$$$ | first error | |
| 3 | 13 | $$$n \le 300$$$ | 0, 1 | first error |
| 4 | 16 | $$$n \le 5000$$$ | 0, 1, 3 | first error |
| 5 | $$$8 \times 3$$$ | $$$n \le 10^5$$$ | 0, 1, 3, 4 | full |
| 6 | $$$12 \times 2$$$ | no additional constraints | 0 – 6 | full |
7 22 11 32 45 44 76 577654321
9 4 9 9 4 9 4
2 01 211
0
In the first example the responses to the queries correspond to the following sets of selected servers:
- for server $$$1$$$ — set $$$\{1, 2, 3\}$$$ or set $$$\{1, 2, 4\}$$$;
- for servers $$$2$$$, $$$4$$$, $$$5$$$, and $$$7$$$ — the set $$$\{2, 4, 5, 7\}$$$;
- for server $$$3$$$ — $$$\{1, 2, 3\}$$$;
- for server $$$6$$$ — $$$\{4, 5, 6\}$$$.