Monocarp plays a new computer game. Each level of this game can be represented as the coordinate axis $$$oX$$$.
To beat the current level, Monocarp's character has to travel from the point $$$0$$$ to the point $$$n$$$. There are two ways to move in the game:
Note that it's possible that Monocarp's character will travel through some points that are to the left of point $$$0$$$ or to the right of point $$$n$$$; it's not against the rules, since the level is infinite.
You have to calculate the minimum time required to reach the point $$$n$$$ from the point $$$0$$$.
The first line contains four integers $$$n$$$, $$$a$$$, $$$b$$$ and $$$d$$$ ($$$1 \le n \le 1\,000$$$, $$$1 \le a \le 1\,000$$$, $$$1 \le b \le 1\,000$$$, $$$1 \le d \le n$$$) — the point Monocarp's character has to reach, the time required to walk to an adjacent point, the time required to leap, and the length of the leap.
Print one integer — the minimum time required to reach the point $$$n$$$ from the point $$$0$$$.
9 7 6 5
19
20 5 10 15
35
4 3 5 2
10
In the first example, it's possible to walk to the left for $$$7$$$ seconds. Then Monocarp's character ends up in the point $$$-1$$$. Then he can leap to the right twice, the first leap ends in the point $$$4$$$, and the second leap ends in the point $$$9$$$. Two leaps take $$$12$$$ seconds. So, Monocarp reaches the goal in $$$7 + 12 = 19$$$ seconds.
In the second example, it's possible to start by leaping to the right. Then the character ends up in the point $$$15$$$, spending $$$10$$$ seconds. Then he has to walk to the right $$$5$$$ times, so he reaches the point $$$20$$$. The total time spent by Monocarp will be equal to $$$10 + 5 \cdot 5 = 35$$$ seconds.
In the third example, it's possible to leap to the right twice. Then the character ends up in the point $$$4$$$, spending $$$10$$$ seconds.
You are given an integer $$$n$$$. You have to construct a permutation of size $$$n$$$.
A permutation is an array where each integer from $$$1$$$ to $$$s$$$ (where $$$s$$$ is the size of permutation) occurs exactly once. For example, $$$[2, 1, 4, 3]$$$ is a permutation of size $$$4$$$; $$$[1, 2, 4, 5, 3]$$$ is a permutation of size $$$5$$$; $$$[1, 4, 3]$$$ is not a permutation (the integer $$$2$$$ is absent), $$$[2, 1, 3, 1]$$$ is not a permutation (the integer $$$1$$$ appears twice).
A subsegment of a permutation is a contiguous subsequence of that permutation. For example, the permutation $$$[2, 1, 4, 3]$$$ has $$$10$$$ subsegments: $$$[2]$$$, $$$[2, 1]$$$, $$$[2, 1, 4]$$$, $$$[2, 1, 4, 3]$$$, $$$[1]$$$, $$$[1, 4]$$$, $$$[1, 4, 3]$$$, $$$[4]$$$, $$$[4, 3]$$$ and $$$[3]$$$.
The value of the permutation is the number of its subsegments which are also permutations. For example, the value of $$$[2, 1, 4, 3]$$$ is $$$3$$$ since the subsegments $$$[2, 1]$$$, $$$[1]$$$ and $$$[2, 1, 4, 3]$$$ are permutations.
You have to construct a permutation of size $$$n$$$ with minimum possible value among all permutations of size $$$n$$$.
The first line contains one integer $$$t$$$ ($$$1 \le t \le 48$$$) — the number of test cases.
Then, $$$t$$$ lines follow. The $$$i$$$-th of them contains one integer $$$n$$$ ($$$3 \le n \le 50$$$) representing the $$$i$$$-th test case.
For each test case, print $$$n$$$ integers — the permutation of size $$$n$$$ with minimum possible value. If there are multiple such permutations, print any of them.
256
1 4 3 5 2 4 1 6 2 5 3
In the first example, the permutation $$$[1, 4, 3, 5, 2]$$$ is one of the possible answers; its value is $$$2$$$.
In the second example, the permutation $$$[4, 1, 6, 2, 5, 3]$$$ is one of the possible answers; its value is $$$2$$$.
Monocarp has a string $$$s$$$ of length $$$n$$$. The string consists of characters a and/or b.
Monocarp will apply the following operation to this string $$$k$$$ times ($$$2k \lt n$$$):
You have to print the resulting string after these $$$k$$$ operations. Note that the constraints on $$$k$$$ guarantee that at least one character will remain in the string.
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$3 \le n \le 200\,000$$$, $$$1 \le k$$$, $$$2k \lt n$$$) — the length of the string and the number of operations Monocarp performes, respectively.
The second line contains the string $$$s$$$ consisting of $$$n$$$ characters a and/or b.
Print the resulting string after $$$k$$$ operations are performed.
6 2 ababbb
ba
13 4 bababbaaababb
aaabb
8 2 abaaabab
aaab
7 1 ababbab
abbab
3 1 bba
b
6 1 aababa
abab
In the first example, during the first operation, the string is reversed, so it becomes bbbaba. Then the first character and the last character are removed, so it becomes bbab. The string won't be reversed during the second operation, and after removing the first and the last character, it becomes ba.
Monocarp has forgotten the password to his mobile phone. The password consists of $$$6$$$ digits from $$$0$$$ to $$$9$$$ (note that it can start with the digit $$$0$$$).
Monocarp remembers that his password had exactly two different digits, and each of these digits appeared exactly three times in the password. Monocarp also remembers some digits which were definitely not used in the password.
You have to calculate the number of different sequences of $$$6$$$ digits that could be the password for Monocarp's mobile phone (i. e. these sequences should meet all of the constraints on Monocarp's password).
The first line contains one integer $$$n$$$ ($$$1 \le n \le 8$$$) — the number of digits for which Monocarp remembers that they were not used in the password.
The second line contains $$$n$$$ different integers $$$a_1, a_2, \dots a_n$$$ ($$$0 \le a_i \le 9$$$) representing the digits that were not used in the password. Note that the digits $$$a_1, a_2, \dots, a_n$$$ are given in ascending order.
Print one integer — the number of different $$$6$$$-digit sequences that meet the constraints.
8 0 1 2 4 5 6 8 9
20
1 8
720
Monocarp has got a sequence of integers $$$a_1, a_2, \dots, a_n$$$. He can perform the following operation any number of times:
You have to determine if it is possible to sort the sequence in non-descending order (i. e. reorder the elements so that for each $$$i$$$ from $$$1$$$ to $$$n - 1$$$, the condition $$$a_i \le a_{i + 1}$$$ is met) using the described operation any number of times (possibly zero).
The first line contains two integers $$$n$$$ and $$$d$$$ ($$$2 \le n \le 200\,000$$$, $$$1 \le d \le n - 1$$$) — the number of elements in the sequence and the distance for the swap operation, respectively.
The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{9}$$$) — the elements of the sequence.
If it's possible to sort the sequence in non-descending order using the described operation any number of times, print YES. Otherwise, print NO.
4 2 6 7 1 4
YES
5 3 5 6 6 10 10
YES
8 3 4 5 3 1 3 4 2 4
NO
In the first example, it's possible to swap the first element and the third element (the sequence becomes $$$[1, 7, 6, 4]$$$), and then swap the second element and the fourth element (so the sequence becomes $$$[1, 4, 6, 7]$$$). After that, the sequence is sorted in non-descending order.
In the second example, the sequence is already sorted in non-descending order.
Monocarp has been collecting rare magazines for quite a while, and now he has decided to cell them. He distributed the magazines between $$$n$$$ boxes, arranged in a row. The $$$i$$$-th box contains $$$a_i$$$ magazines. Some of the boxes are covered with lids, others are not.
Suddenly it started to rain, and now Monocarp has to save as many magazines from the rain as possible. To do this, he can move the lids between boxes as follows: if the $$$i$$$-th box was covered with a lid initially, he can either move the lid from the $$$i$$$-th box to the box $$$(i-1)$$$ (if it exists), or keep the lid on the $$$i$$$-th box. You may assume that Monocarp can move the lids instantly at the same moment, and no lid can be moved more than once. If a box will be covered with a lid after Monocarp moves the lids, the magazines in it will be safe from the rain; otherwise they will soak.
You have to calculate the maximum number of magazines Monocarp can save from the rain.
The first line contains one integer $$$n$$$ ($$$1 \le n \le 200\,000$$$) — the number of boxes.
The second line contains a string of $$$n$$$ characters 0 and/or 1. If the $$$i$$$-th character is 1, the $$$i$$$-th box is initially covered with a lid. If the $$$i$$$-th character is 0, the $$$i$$$-th box is initially not covered.
The third line contains a sequence of integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^4$$$), where $$$a_i$$$ is the number of magazines in the $$$i$$$-th box.
Print one integer — the maximum number of magazines Monocarp can save from the rain.
5 01110 10 5 8 9 6
27
6 011011 20 10 9 30 20 19
80
4 0000 100 100 100 100
0
4 0111 5 4 5 1
14
In the first example, Monocarp can move the lid from the second box to the first box, so the boxes $$$1$$$, $$$3$$$ and $$$4$$$ are covered, and $$$10 + 8 + 9 = 27$$$ magazines are saved.
In the second example, Monocarp can move the lid from the second box to the first box, then from the third box to the second box, then from the fifth box to the fourth box, and then from the sixth box to the fifth box. The boxes $$$1$$$, $$$2$$$, $$$4$$$ and $$$5$$$ will be covered, so $$$20 + 10 + 30 + 20 = 80$$$ magazines can be saved.
There are no lids in the third example, so it's impossible to save even a single magazine.
Monocarp is participating in a competition. There are $$$n$$$ judges evaluating the participants; the score given by each of them is an integer between $$$1$$$ and $$$10^{9}$$$, inclusive (the bigger it is, the better for the participant).
According to the rules of the competition, the final score of the participant is an integer, which is calculated based on the list of $$$n$$$ integers given by the judges, as follows:
This operation is performed $$$n - 1$$$ times, after which, the list contains only one number. The remaining integer is the final score of the participant.
You have to calculate Monocarp's final score according to these rules, based on the score he received from each judge.
The first line contains one integer $$$n$$$ ($$$2 \le n \le 200\,000$$$) — the number of judges.
The second line contains the sequence of integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{9}$$$) — the scores given by the judges.
Print one integer — the final score calculated according to the rules of the competition.
5 3 6 1 9 1
3
8 12 12 40 30 20 24 21 13
20
3 100 100 100
100
The sorted list of the scores in the first example is $$$[1, 1, 3, 6, 9]$$$.
During the first operation, $$$x = 1$$$, $$$y = 9$$$. These integers are removed, and $$$\frac{1 + 9}{2} = 5$$$ is added. So, the current list is $$$[1, 3, 5, 6]$$$.
During the second operation, $$$x = 1$$$, $$$y = 6$$$. These integers are removed, and $$$\frac{1 + 6}{2} = 3$$$ (rounded down) is added. So, the current list is $$$[3, 3, 5]$$$.
During the third operation, $$$x = 3$$$, $$$y = 5$$$. These integers are removed, and $$$\frac{3 + 5}{2} = 4$$$ is added. So, the current list is $$$[3, 4]$$$.
During the fourth operation, $$$x = 3$$$, $$$y = 4$$$. These integers are removed, and $$$\frac{3 + 4}{2} = 3$$$ (rounded down) is added. So, the current list is $$$[3]$$$.
The final score is $$$3$$$, since it is the only element of the resulting list.
Monocarp is a student. There are $$$n$$$ other students in his group at the university.
The Linguistics lecturer told the students to prepare a report based on a book which consists of $$$m$$$ pages. Pages of the book are numbered from $$$1$$$. The group of students will be prepared for the report if every page of the book is read by at least one student.
The $$$i$$$-th student from $$$n$$$ of Monocarp's groupmates (excluding Monocarp himself) has read several pages of the book, from the page $$$a_i$$$ to the page $$$b_i$$$ inclusive ($$$a_i \le b_i$$$).
Monocarp will read several consecutive (without skips) pages of the book — he thinks that it will allow him to prepare better. You have to calculate the minimum number of pages he has to read so that the group is prepared for the report (i. e. so that every page is read by at least one student).
Note that if every page of the book is already read by at least one student, Monocarp won't read anything.
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 200\,000$$$, $$$1 \le m \le 10^{9}$$$) — the number of students (excluding Monocarp) and the number of pages in the book, respectively.
The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i \le b_i \le m$$$) — the first and the last page in the part of the book which was read by the $$$i$$$-th student. So, the $$$i$$$-th student has read all pages from the $$$a_i$$$-th one to the $$$b_i$$$-th one inclusive.
Print one integer — the minimum number of pages Monocarp has to read so that every page is read by at least one student. If Monocarp doesn't have to read anything, print $$$0$$$.
2 6 1 2 5 6
2
3 10 2 7 5 8 9 9
10
2 15 1 13 4 15
0
In the first example, Monocarp has to read the third page and the fourth page, and the group will be prepared for the report.
In the second example, neither the first page nor the last page has been read. Since Monocarp cannot skip pages while reading, he has to read all $$$10$$$ pages of the book.
In the third example, Monocarp doesn't have to read anything, since each page is already read by some other student.
Monocarp lives on a street which can be represented as a segment of the $$$oX$$$ axis. The street begins in point $$$0$$$ and ends in point $$$f$$$. There are $$$n$$$ pillars on the street, they are located in points $$$a_1, a_2, \dots, a_n$$$.
It is possible to install a lantern on each pillar. Each lantern illuminates a segment of the axis. If a lantern is installed on a pillar in point $$$x$$$, and the power of the lantern is $$$y$$$, then the segment from $$$x - y$$$ to $$$x + y$$$ (including both endpoints) will be illuminated.
Monocarp can install up to $$$k$$$ lanterns. Each lantern's power should be a positive integer.
Monocarp wants to illuminate the whole street, i. e. each point from $$$0$$$ to $$$f$$$. Note that all points from $$$0$$$ to $$$f$$$, including non-integer ones, should be illuminated.
To achieve this, Monocarp will choose $$$k$$$ pillars, install lanterns on them (one lantern on each of the chosen pillars), and tune all lanterns, so they have the same power, equal to $$$d$$$.
Monocarp doesn't want to spend too much money on electricity (the more power the lantern has, the more it consumes). Help him calculate the minimum possible power for his $$$k$$$ lanterns, so they can be installed in such a way that the whole street (from $$$0$$$ to $$$f$$$) is illuminated.
The first line contains three integers $$$n$$$, $$$k$$$ and $$$f$$$ ($$$1 \le k \le n \le 200\,000$$$, $$$1 \le f \le 10^{9}$$$) — the number of pillars, the number of lanterns and the rightmost point of the street, respectively.
The second line contains the sequence of integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le f$$$) — the locations of the lanterns. The elements of the sequence are pairwise distinct.
Print one integer — the minimum possible power of lanterns (all $$$k$$$ lanterns should have the same power) such that $$$k$$$ lanterns are enough to illuminate the whole street from the point $$$0$$$ to the point $$$f$$$ (including non-integer points).
2 1 12 6 4
6
4 2 20 3 6 13 19
7
2 2 1 0 1
1
2 1 1 0 1
1
10 4 100 34 52 12 35 89 60 77 43 23 11
15
In the first example, it is possible to install a lantern with power $$$6$$$ on a pillar in point $$$6$$$. Then all points from $$$0$$$ to $$$12$$$ will be illuminated.
In the second example, it is possible to install the lanterns in points $$$3$$$ and $$$13$$$ with power $$$7$$$. Then all points from $$$0$$$ to $$$20$$$ will be illuminated. Note that the lantern in point $$$3$$$ will illuminate the segment $$$[-4, 10]$$$, which is partially outside the street, but it doesn't make the placement incorrect.
In the third example, Monocarp has to install the lanterns on both pillars with power $$$1$$$, since all points (including non-integer ones) should be illuminated, and the power of the lanterns should be integer.
In the fourth example, the lantern with power $$$1$$$ can be installed on any pillar. All points from $$$0$$$ to $$$1$$$ will be illuminated.
You are given a string $$$s$$$ consisting of $$$n$$$ characters. Each character of $$$s$$$ is either 0 or 1.
A substring of $$$s$$$ is a contiguous subsequence of its characters.
You have to choose two substrings of $$$s$$$ (possibly intersecting, possibly the same, possibly non-intersecting — just any two substrings). After choosing them, you calculate the value of the chosen pair of substrings as follows:
Calculate the maximum possible value you can get, and print it in binary representation without leading zeroes.
The first line contains one integer $$$n$$$ — the number of characters in $$$s$$$.
The second line contains $$$s$$$ itself, consisting of exactly $$$n$$$ characters 0 and/or 1.
All non-example tests in this problem are generated randomly: every character of $$$s$$$ is chosen independently of other characters; for each character, the probability of it being 1 is exactly $$$\frac{1}{2}$$$.
This problem has exactly $$$40$$$ tests. Tests from $$$1$$$ to $$$3$$$ are the examples; tests from $$$4$$$ to $$$40$$$ are generated randomly. In tests from $$$4$$$ to $$$10$$$, $$$n = 5$$$; in tests from $$$11$$$ to $$$20$$$, $$$n = 1000$$$; in tests from $$$21$$$ to $$$40$$$, $$$n = 10^6$$$.
Print the maximum possible value you can get in binary representation without leading zeroes.
5 11010
11111
7 1110010
1111110
4 0000
0
In the first example, you can choose the substrings 11010 and 101. $$$f(s_1) = 26$$$, $$$f(s_2) = 5$$$, their bitwise OR is $$$31$$$, and the binary representation of $$$31$$$ is 11111.
In the second example, you can choose the substrings 1110010 and 11100.
Monocarp is playing a video game. In the game, he controls a spaceship and has to destroy an enemy spaceship.
Monocarp has two lasers installed on his spaceship. Both lasers $$$1$$$ and $$$2$$$ have two values:
When a laser is fully charged, Monocarp can either shoot it or wait for the other laser to charge and shoot both of them at the same time.
An enemy spaceship has $$$h$$$ durability and $$$s$$$ shield capacity. When Monocarp shoots an enemy spaceship, it receives $$$(P - s)$$$ damage (i. e. $$$(P - s)$$$ gets subtracted from its durability), where $$$P$$$ is the total power of the lasers that Monocarp shoots (i. e. $$$p_i$$$ if he only shoots laser $$$i$$$ and $$$p_1 + p_2$$$ if he shoots both lasers at the same time). An enemy spaceship is considered destroyed when its durability becomes $$$0$$$ or lower.
Initially, both lasers are zero charged.
What's the lowest amount of time it can take Monocarp to destroy an enemy spaceship?
The first line contains two integers $$$p_1$$$ and $$$t_1$$$ ($$$2 \le p_1 \le 5000$$$; $$$1 \le t_1 \le 10^{12}$$$) — the power and the reload time of the first laser.
The second line contains two integers $$$p_2$$$ and $$$t_2$$$ ($$$2 \le p_2 \le 5000$$$; $$$1 \le t_2 \le 10^{12}$$$) — the power and the reload time of the second laser.
The third line contains two integers $$$h$$$ and $$$s$$$ ($$$1 \le h \le 5000$$$; $$$1 \le s \lt \min(p_1, p_2)$$$) — the durability and the shield capacity of an enemy spaceship. Note that the last constraint implies that Monocarp will always be able to destroy an enemy spaceship.
Print a single integer — the lowest amount of time it can take Monocarp to destroy an enemy spaceship.
5 10 4 9 16 1
20
10 1 5000 100000 25 9
25
In the first example, Monocarp waits for both lasers to charge, then shoots both lasers at $$$10$$$, they deal $$$(5 + 4 - 1) = 8$$$ damage. Then he waits again and shoots lasers at $$$20$$$, dealing $$$8$$$ more damage.
In the second example, Monocarp doesn't wait for the second laser to charge. He just shoots the first laser $$$25$$$ times, dealing $$$(10 - 9) = 1$$$ damage each time.
You are given $$$n$$$ segments on the coordinate axis. The $$$i$$$-th segment is $$$[l_i, r_i]$$$. Let's denote the set of all integer points belonging to the $$$i$$$-th segment as $$$S_i$$$.
Let $$$A \cup B$$$ be the union of two sets $$$A$$$ and $$$B$$$, $$$A \cap B$$$ be the intersection of two sets $$$A$$$ and $$$B$$$, and $$$A \oplus B$$$ be the symmetric difference of $$$A$$$ and $$$B$$$ (a set which contains all elements of $$$A$$$ and all elements of $$$B$$$, except for the ones that belong to both sets).
Let $$$[\mathbin{op}_1, \mathbin{op}_2, \dots, \mathbin{op}_{n-1}]$$$ be an array where each element is either $$$\cup$$$, $$$\oplus$$$, or $$$\cap$$$. Over all $$$3^{n-1}$$$ ways to choose this array, calculate the sum of the following values:
$$$$$$|(((S_1\ \mathbin{op}_1\ S_2)\ \mathbin{op}_2\ S_3)\ \mathbin{op}_3\ S_4)\ \dots\ \mathbin{op}_{n-1}\ S_n|$$$$$$
In this expression, $$$|S|$$$ denotes the size of the set $$$S$$$.
The first line contains one integer $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$).
Then, $$$n$$$ lines follow. The $$$i$$$-th of them contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$0 \le l_i \le r_i \le 3 \cdot 10^5$$$).
Print one integer — the sum of $$$|(((S_1\ \mathbin{op}_1\ S_2)\ \mathbin{op}_2\ S_3)\ \mathbin{op}_3\ S_4)\ \dots\ \mathbin{op}_{n-1}\ S_n|$$$ over all possible ways to choose $$$[\mathbin{op}_1, \mathbin{op}_2, \dots, \mathbin{op}_{n-1}]$$$. Since the answer can be huge, print it modulo $$$998244353$$$.
4 3 5 4 8 2 2 1 9
162
4 1 9 3 5 4 8 2 2
102
Note that the memory limit is unusual.
Let's define the sequence of Fibonacci strings as follows: $$$f_0$$$ is 0, $$$f_1$$$ is 1, $$$f_i$$$ is $$$f_{i-1} + f_{i-2}$$$ for $$$i \gt 1$$$ ($$$+$$$ denotes the concatenation of two strings). So, for example, $$$f_2$$$ is 10, $$$f_3$$$ is 101, $$$f_4$$$ is 10110.
For a given string $$$s$$$, let's define $$$g(s)$$$ as the number of ways to cut it into several (any number, possibly even just one) strings such that none of these strings are Fibonacci strings. For example, if $$$s$$$ is 10110101, $$$g(s) = 3$$$ since there are three ways to cut it:
You are given a sequence of strings $$$s_1, s_2, \dots, s_n$$$. Calculate $$$g(s_1), g(s_1 + s_2), \dots, g(s_1 + s_2 + \ldots + s_n)$$$. Since these values can be huge, print them modulo $$$998244353$$$.
The first line of the input contains one integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^3$$$).
Then, $$$n$$$ lines follow. The $$$i$$$-th line contains the string $$$s_i$$$ ($$$1 \le |s_i| \le 10^3$$$), consisting of characters 0 and/or 1.
Print $$$n$$$ integers, where the $$$i$$$-th integer is $$$g(s_1 + s_2 + \ldots + s_i) \bmod 998244353$$$.
1 10110101
3
3 1111 1 0
2 3 3
6 10110101 100100001110 0000001100010001 1111 1001010100101010101001 000100000010101111
3 561 1466229 9887505 972227653 52128355