Scientists have discovered a new species of bacteria and have begun conducting experiments to study it.
In one of the experiments, they placed a colony of bacteria on an infinite grid, and it turned out that it expands every second. In every even second, the colony expands in eight directions, meaning it occupies cells adjacent to the occupied ones both orthogonally and diagonally, if they are not already occupied. In odd seconds, it only expands in four directions, occupying cells adjacent to the occupied ones orthogonally.
Help the scientists determine how many cells are occupied by the colony of bacteria at the $$$k$$$-th second of the experiment, given that it was placed on the grid in the first second.
The first line contains an integer $$$k$$$ — the time in seconds when the scientists want to know how many cells are occupied by the colony of bacteria ($$$1 \le k \le 10^8$$$).
Output a single number – the number of cells occupied by the colony of bacteria at the $$$k$$$-th second of the experiment.
1
1
2
9
3
21
4
45
5
69
The filling of the grid for the first five seconds, with the cell indicating the second when this cell will first be occupied by the colony of bacteria.
| 5 | 5 | 5 | 5 | 5 | ||||
| 5 | 4 | 4 | 4 | 4 | 4 | 5 | ||
| 5 | 4 | 4 | 3 | 3 | 3 | 4 | 4 | 5 |
| 5 | 4 | 3 | 2 | 2 | 2 | 3 | 4 | 5 |
| 5 | 4 | 3 | 2 | 1 | 2 | 3 | 4 | 5 |
| 5 | 4 | 3 | 2 | 2 | 2 | 3 | 4 | 5 |
| 5 | 4 | 4 | 3 | 3 | 3 | 4 | 4 | 5 |
| 5 | 4 | 4 | 4 | 4 | 4 | 5 | ||
| 5 | 5 | 5 | 5 | 5 |
You are probably familiar with the classic problem of finding the longest increasing subsequence in an array. Let $$$a$$$ be an array consisting of $$$n$$$ integers. A subsequence $$$i_1 \lt i_2 \lt \ldots \lt i_k$$$ is called increasing if $$$a_{i_1} \lt a_{i_2} \lt \ldots \lt a_{i_k}$$$. The longest increasing subsequence is the increasing subsequence of maximum length. Of course, we will not ask you to solve the classic problem; you will have to solve its more complicated version...
Initially, there is an empty array $$$a$$$. Then, the numbers $$$1, 2, \ldots, n$$$ are added to the array in this order. The number $$$i$$$ is added to the array at position $$$p_i$$$. Positions in the array are numbered with integers from $$$1$$$ to $$$k$$$, where $$$k$$$ is the current size of the array. When adding an element at position $$$p$$$ in an array of size $$$k$$$, all elements that previously had positions from $$$p$$$ to $$$k$$$ are shifted one position to the right, and the current element is added to the freed space.
Your task is to determine the length of the longest increasing subsequence in the array after each addition of a new element.
The first line contains one integer $$$n$$$ ($$$1 \le n \le 200\,000$$$) — the number of added elements.
The second line contains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le i$$$) — $$$p_i$$$ denotes the position where element $$$i$$$ is added.
Output $$$n$$$ integers — the length of the longest increasing subsequence of the array after each addition of a new element.
51 2 1 3 4
1 2 2 2 3
11
1
The array in the first example changed as follows: $$$[] \to [1] \to [1, 2] \to [3, 1, 2] \to [3, 1, 4, 2] \to [3, 1, 4, 5, 2]$$$.
The new high-speed highway M-11 is an infinite straight line.
On the highway, there are $$$n$$$ stopping points, each of which is a rest area or a gas station. Each stopping point is defined by its coordinate $$$x_i$$$, and no two stopping points are located at the same place. A triplet of stopping points $$$(i, j, k)$$$ is called convenient if $$$x_{i} \lt x_{j} \lt x_{k}$$$, there are gas stations at points $$$x_{i}$$$ and $$$x_{k}$$$, a rest area at point $$$x_{j}$$$, and the distance between the gas stations does not exceed $$$d$$$.
A team from Moscow is planning to travel to the contest along the M-11 highway, and its leader became curious about how many convenient triplets of stopping points exist along the way.
The first line contains two natural numbers $$$n$$$ and $$$d$$$ — the number of stopping points and the maximum distance between gas stations ($$$3 \leq n \leq 5 \cdot 10^{5}$$$, $$$2 \leq d \leq 10^{9}$$$).
In the following $$$n$$$ lines, the stopping points are given. Each stopping point is defined by two integers $$$x_i$$$ and $$$t_i$$$ — the coordinate of the point and its type. Type $$$0$$$ denotes a rest area, and type $$$1$$$ denotes a gas station ($$$-10^{18} \leq x_i \leq 10^{18}$$$; $$$t_{i} \in \{0, 1\}$$$). It is guaranteed that the coordinates of the stopping points are in increasing order.
Output a single number — the number of convenient triplets.
8 51 12 03 16 07 08 115 119 1
3
10 60 11 03 14 05 18 110 011 014 118 1
7
In the first input set, the convenient triplets are $$$(1, 2, 3)$$$, $$$(3, 4, 6)$$$, and $$$(3, 5, 6)$$$.
Katya formed the word $$$s_1$$$ from blocks, but when she returned to the room, she saw her brother Andrey running out. Now the word made from the blocks looked different — $$$s_2$$$. Andrey admitted that he played a little prank. His prank consisted of the following: Andrey would choose a position and then insert two blocks with the same letter next to it. He could place these two blocks at the beginning of the string, at the end of the string, or between two neighboring blocks.
Help Katya determine whether Andrey told the truth, that is, whether the string $$$s_2$$$ could have been obtained from the string $$$s_1$$$ by possibly applying several pranks.
One test contains several sets of input data.
The first line contains one integer $$$t$$$ — the number of sets of input data ($$$1 \le t \le 500\,000$$$).
In the first line of each set description, there is one string $$$s_1$$$ — the word from the blocks that Katya originally had.
In the second line of each set description, there is one string $$$s_2$$$ — the word from the blocks that Andrey obtained.
It is guaranteed that all words consist of lowercase Latin letters. The total length of all words does not exceed $$$1\,000\,000$$$.
For each set of input data, output "YES", if Andrey could be telling the truth, and "NO" otherwise.
2hellohavvaeeellotesttesssst
YES NO
Petya received a failing grade in cryptography, but it was the teachers who did not understand his genius, not him being lazy. To convince the entire world community of his genius, Petya created a new public key encryption system — PSA. Any self-respecting public key cryptosystem has a public key and a private key.
As a private key, Petya chose a tree $$$T$$$, and as a public key — two numbers $$$(n, p)$$$, where $$$n$$$ is the number of vertices in the tree $$$T$$$, and $$$p$$$ is the number of paths of length 2 in $$$T$$$. Recall that a tree is an undirected connected graph that does not contain cycles.
The peculiarity of Petya's cryptosystem is that any private key corresponding to the public key will suffice to break it. But that's not a problem; Petya chose quite a complex task, right? Restore any private key of the cryptosystem $$$PSA$$$ or state that such a public key could not have been produced.
The input consists of a single line containing two numbers $$$n$$$ and $$$p$$$ ($$$1 \leq n \leq 1000$$$, $$$0 \leq p \leq 10^9$$$).
If a solution exists, output "Yes" in the first line. In the next $$$n - 1$$$ lines, output two distinct integers from 1 to $$$n$$$ — the edges of the tree.
If no solution exists, output "No" in a single line.
7 11
Yes 1 2 2 3 3 4 3 5 3 6 3 7
5 5
No
Katya knows that the travel time from home to the metro on a scooter is $$$t$$$ seconds.
The cost of the ride on the scooter from company W is calculated as follows: first, the number of full minutes spent on the trip is determined, then this time is multiplied by 60 and used to calculate the cost at the rate of $$$c_1$$$ cents per second.
The cost of the ride on the scooter from company Y is calculated differently: first, the cost of the trip is calculated at the rate of $$$c_2$$$ cents per second, and then this amount is rounded up to the nearest whole euro.
Help Katya understand what is the minimum cost she can get to the metro on a scooter from one of these companies.
Recall that there are 100 cents in one euro.
The first line contains three integers $$$t$$$, $$$c_1$$$, and $$$c_2$$$ — the travel time in seconds, the fare in cents per second on the scooter from company W, and the fare in cents per second on the scooter from company Y ($$$1 \le t \le 1000$$$, $$$10 \le c_1, c_2 \le 20$$$).
Output the minimum cost of the ride in cents.
473 10 11
4200