Monocarp decided to buy ball ornaments to decorate his Christmas tree. There are only three colors of ornaments in the shop nearby: red, yellow, and blue. Fortunately, there are infinitely many ornaments of each color.
One red ornament costs $$$r$$$ burles, one yellow ornament — $$$y$$$ burles, and one blue ornament — $$$b$$$ burles.
Monocarp has $$$n$$$ burles and would like to buy as many ornaments as possible. But he considers Christmas tree to be beautifully decorated only if the numbers of ornaments of each color differ by not more than one. More formally, if Monocarp will buy $$$cnt_r$$$ red ornaments, $$$cnt_y$$$ yellow ornaments, and $$$cnt_b$$$ blue ornaments then the following conditions should be fulfilled: $$$|cnt_r - cnt_y| \le 1$$$, $$$|cnt_r - cnt_b| \le 1$$$, $$$|cnt_y - cnt_b| \le 1$$$.
Calculate the maximum possible total number of ornaments Monocarp can buy in such a way that the numbers of ornaments of each color differ by not more than one.
The first line contains one integer $$$n$$$ ($$$1 \le n \le 1000$$$) — the amount of money Monokarp has.
The second line contains one integer $$$r$$$ ($$$1 \le r \le n$$$) — the cost of one red ornament.
The third line contains one integer $$$y$$$ ($$$1 \le y \le n$$$) — the cost of one yellow ornament.
The fourth line contains one integer $$$b$$$ ($$$1 \le b \le n$$$) — the cost of one blue ornament.
Print the maximum possible total number of ornaments Monocarp can buy in such a way that the numbers of ornaments of each color differ by not more than one.
12 2 2 2
6
26 1 4 7
7
17 4 2 3
5
100 100 100 100
1
In the first sample, Monocarp can buy two ornaments of each color and will spend all $$$12$$$ burles he has. In total, he can buy at most $$$6$$$ ornaments.
In the second sample, Monocarp can buy $$$3$$$ red ornaments, $$$2$$$ yellow ornaments, and $$$2$$$ blue ornaments and will spend $$$3 \cdot 1 + 2 \cdot 4 + 2 \cdot 7 = 25$$$ burles. In total Monocarp can buy at most $$$7$$$ ornaments. Monocarp still has $$$1$$$ burle left, but he won't buy extra red ornament, since it will break the beautiful decoration of the Christmas tree described in the statement.
In the third sample, Monocarp can buy $$$1$$$ red ornament, $$$2$$$ yellow ornaments, and $$$2$$$ blue ornaments and will spend $$$1 \cdot 4 + 2 \cdot 2 + 2 \cdot 3 = 14$$$ burles. In total, he can buy at most $$$5$$$ ornaments.
There are $$$n$$$ soldiers in the line, standing shoulder to shoulder from left to right. Each soldier's head is turned either to the left or to the right, that is, each of the soldiers is looking either strictly to the left or strictly to the right.
You need to give some of the soldiers an order to turn their heads in the opposite direction. That means, after executing this order, a soldier looking to the left should turn his head to the right, and a soldier looking to the right should turn his head to the left. After executing the order, there should exist a soldier such that all other soldiers look at him (it doesn't matter in which direction that soldier looks). Only the soldiers who were given the order turn their heads.
For example, if there are $$$5$$$ soldiers in the line, the first three soldiers are looking to the right, and the fifth soldier is looking to the left, then they all are looking at the fourth soldier.
Find the minimum number of soldiers who should be given the order to turn their heads so that all the soldiers were looking in the direction of some single soldier.
The first line contains an integer $$$n$$$ ($$$2 \le n \le 2\,000$$$) — the number of soldiers in the line.
The second line contains a string $$$s$$$ of length $$$n$$$, consisting of the letters "L" and "R". If the $$$i$$$-th character of the string is "L", then the $$$i$$$-th soldier is looking to the left. If the $$$i$$$-th character of the string is "R", then the $$$i$$$-th soldier is looking to the right.
Print the minimum number of soldiers who should be given the order to turn their heads so that there exists a soldier such that all other soldiers look at him (it doesn't matter in which direction that soldier looks).
6 LRRRLR
2
3 LLL
0
10 LLRRLRRRRL
3
In the first example, you need to give the order, for example, to the first and sixth soldiers. After that, the line would look like "RRRRLL". So everyone except the fifth soldier would be looking at the fifth soldier.
In the second example, all the soldiers are looking to the left, so the second and third soldiers are looking at the first soldier, so you don't need to give any orders.
Recently a new building with a new layout was constructed in Monocarp's hometown. According to this new layout, the building consists of three types of apartments: three-room, five-room, and seven-room apartments. It's also known that each room of each apartment has exactly one window. In other words, a three-room apartment has three windows, a five-room — five windows, and a seven-room — seven windows.
Monocarp went around the building and counted $$$n$$$ windows. Now he is wondering, how many apartments of each type the building may have.
Unfortunately, Monocarp only recently has learned to count, so he is asking you to help him to calculate the possible quantities of three-room, five-room, and seven-room apartments in the building that has $$$n$$$ windows. If there are multiple answers, you can print any of them.
The first line contains one integer $$$n$$$ ($$$1 \le n \le 10^{18}$$$) — the number of windows in the building.
If a building with the new layout and the given number of windows just can't exist, print $$$-1$$$.
Otherwise, print three non-negative integers — the possible number of three-room, five-room, and seven-room apartments. If there are multiple answers, print any of them.
30
2 2 2
67
7 5 3
4
-1
In the first sample, one of possible answers is $$$2$$$ three-room apartments, $$$2$$$ five-room apartments, and $$$2$$$ seven-room apartments. So the number of windows is equal to $$$2 \cdot 3 + 2 \cdot 5 + 2 \cdot 7 = 30$$$.
You have $$$n$$$ barrels lined up in a row, numbered from left to right from one. Initially, the $$$i$$$-th barrel contains $$$a_i$$$ liters of water.
You can pour water from one barrel to another. In one act of pouring, you can choose two different barrels $$$x$$$ and $$$y$$$ (the $$$x$$$-th barrel shouldn't be empty) and pour any possible amount of water from barrel $$$x$$$ to barrel $$$y$$$ (possibly, all water). You may assume that barrels have infinite capacity, so you can pour any amount of water in each of them.
Calculate the maximum possible difference between the maximum and the minimum amount of water in the barrels, if you can pour water at most $$$k$$$ times.
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \lt n \le 2 \cdot 10^5$$$) — the number of barrels and the number of pourings you can make.
The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^{9}$$$), where $$$a_i$$$ is the initial amount of water the $$$i$$$-th barrel has.
Print the maximum possible difference between the maximum and the minimum amount of water in the barrels, if you can pour water at most $$$k$$$ times.
4 1 5 5 5 5
10
3 2 0 0 0
0
In the first example, you can pour all water from the second barrel to the fourth one. Then amount of water in each barrel will be equal to $$$[5, 0, 5, 10]$$$, and difference between the maximum and the minimum will be equal to $$$10$$$.
In the second example, all barrels are empty, so we can't have anything to pour. The difference between the maximum and the minimum will be equal to $$$0$$$.
Numbers $$$1, 2, 3, \dots n$$$ (each integer from $$$1$$$ to $$$n$$$ once) are written on a board. In one operation you can erase any two numbers $$$a$$$ and $$$b$$$ from the board and write one integer $$$\frac{a + b}{2}$$$ rounded up instead.
You should perform the given operation $$$n - 1$$$ times and make the resulting number that will be left on the board as small as possible.
It's easy to see that after $$$n - 1$$$ operations, there will be left only one number. Your goal is to minimize it.
The first line contains one integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of integers written on the board initially.
In the first line, print the minimum possible number left on the board after $$$n - 1$$$ operations. Each of the next $$$n - 1$$$ lines should contain two integers — numbers $$$a$$$ and $$$b$$$ chosen and erased in each operation.
4
2 2 4 3 3 3 1
In the first sample, numbers $$$[1, 2, 3, 4]$$$ are written on the board initially. In the first operation, numbers $$$2$$$ and $$$4$$$ are erased and number $$$3$$$ are written instead. So, after the first operation, the numbers $$$[1, 3, 3]$$$ will be written. After the second operation, the numbers $$$[1, 3]$$$ will be written. Finally, after the third operation, the only number left is $$$2$$$.
Monocarp saved up $$$n$$$ burles and decided to deposit all his $$$n$$$ burles in a local bank.
Unfortunately, Monokarp hasn't read the license agreement, that's why now he has only two types of operations with money in the deposit (fortunately, he can make any number of operations of each type):
Assume that Monocarp put all his $$$n$$$ burles in the bank account and he has no more money left, so he can work only with money he put in the bank.
Calculate the maximum possible amount of burles Monocarp can obtain from his bank account using only described operations.
The first line contains three integers $$$n$$$, $$$a$$$, and $$$b$$$ ($$$1 \le a, b \le n \le 10^{6}$$$) — the number of burles Monocarp deposited initially, the number of burles he can withdraw from the account in one operation, and the number of burles he can deposit to the account in one operation.
Print the maximum possible amount of burles Monocarp can obtain from his bank account using only operations described in the statement.
17 5 3
17
97 10 6
96
77141 21540 3108
77136
Monocarp has opened his own car park. There are $$$n$$$ parking spaces in total, located from left to right. Monocarp decided to number all his parking spaces, but since he really doesn't like the digit $$$k$$$, the numbering would be peculiar.
Monocarp will number the parking spaces one by one (starting from the leftmost) with integers starting from one. If the next number that Monocarp wants to use for the current parking space contains the digit $$$k$$$ in its notation, then Monocarp will skip this number and move on to the next number until he finds a number that does not contain the digit $$$k$$$ in its notation. This would be the number that Monocarp will use for the current parking space; then he will continue assigning numbers to the next parking spaces.
For example, if Monocarp doesn't like the digit $$$1$$$ and there are $$$12$$$ spaces in his car park, they will be numbered as follows: $$$[2, 3, 4, 5, 6, 7, 8, 9, 20, 22, 23, 24]$$$.
Your task is to find the number that Monocarp will assign to the last (i. e. $$$n$$$-th) parking space.
The first line contains two integers $$$n$$$ and $$$k$$$ $$$(1 \le n \le 10^{9}, 0 \le k \le 9)$$$ — the number of parking spaces and the digit that Monocarp doesn't like.
Print the number that Vasily will assign to the $$$n$$$-th parking space.
12 1
24
12 2
14
18 0
19
1000000000 5
2620708101
The first example is described in the statement.
In the second example, there are $$$12$$$ parking spaces, and the digit that Monocarp doesn't like is $$$2$$$. The parking space numbers will thus look like this: $$$[1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14]$$$. Therefore, the $$$12$$$-th parking space will have the number $$$14$$$.
In the third example, there are $$$18$$$ parking spaces, and the digit that Monocarp doesn't like is $$$0$$$. The parking space numbers will thus look like this: $$$[1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18, 19]$$$. Therefore, the $$$18$$$-th parking space will have the number $$$19$$$.
You have a string $$$s$$$ consisting of $$$n$$$ characters. Each character is either 0 or 1.
You can perform operations on the string. Each operation consists of two steps:
Note that both steps are mandatory in each operation, and their order cannot be changed.
For example, if you have a string $$$s =$$$ 111010, the first operation can be one of the following:
You finish performing operations when the string $$$s$$$ becomes empty. What is the maximum number of operations you can perform?
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the string $$$s$$$.
The second line contains string $$$s$$$ of $$$n$$$ characters. Each character is either 0 or 1.
Print a single integer — the maximum number of operations you can perform.
6 111010
3
1 0
1
1 1
1
2 11
1
6 101010
3
You are given a string $$$s$$$. You have to reverse it — that is, the first letter should become equal to the last letter before the reversal, the second letter should become equal to the second-to-last letter before the reversal — and so on. For example, if your goal is to reverse the string "abddea", you should get the string "aeddba". To accomplish your goal, you can swap the neighboring elements of the string.
Your task is to calculate the minimum number of swaps you have to perform to reverse the given string.
The first line contains one integer $$$n$$$ ($$$2 \le n \le 200\,000$$$) — the length of $$$s$$$.
The second line contains $$$s$$$ — a string consisting of $$$n$$$ lowercase Latin letters.
Print one integer — the minimum number of swaps of neighboring elements you have to perform to reverse the string.
5 aaaza
2
6 cbaabc
0
9 icpcsguru
30
In the first example, you have to swap the third and the fourth elements, so the string becomes "aazaa". Then you have to swap the second and the third elements, so the string becomes "azaaa". So, it is possible to reverse the string in two swaps.
Since the string in the second example is a palindrome, you don't have to do anything to reverse it.
You have a string $$$s$$$ consisting of lowercase letters of the Latin alphabet.
You need to split this string into substrings according to the following requirements:
Therefore, if we concatenate all the resulting substrings in the same order, we'll get the original string $$$s$$$.
A substring of the string $$$s$$$ is a non-empty sequence of consecutive letters of the string $$$s$$$.
For example, the string aadddzxxz can be split into substrings aa, ddd and zxxz.
Find the maximum number of substrings that the string $$$s$$$ can be split into, and also the sizes of each of these substrings. If the string $$$s$$$ cannot be split as described, report it.
The first line contains an integer $$$n$$$ ($$$2 \le n \le 4 \cdot 10^5$$$) — the length of the string $$$s$$$.
The second line contains a string $$$s$$$ of length $$$n$$$ consisting of lowercase letters of the Latin alphabet.
If the string cannot be split into substrings of greater than one length that start and end with the same letter, print $$$-1$$$.
Otherwise, in the first line, print $$$k$$$ — the maximum number of substrings that the string $$$s$$$ can be split into. In the second line, print $$$k$$$ integers — the sizes of substrings that the string $$$s$$$ can be split into, in order from left to right. The sum of the output $$$k$$$ numbers must be equal to $$$n$$$.
4 aaaa
2 2 2
15 abcbcaccbbcabca
3 6 5 4
4 abcd
-1
5 abcda
1 5
In the first example, the string can be split into two substrings of length two, each of which starts and ends with the letter a.
In the second example, the string can be split into three substrings abcbca, ccbbc and abca.
Recently you've discovered a new shooter. They say it has realistic game mechanics.
Your character has a gun with magazine size equal to $$$k$$$ and should exterminate $$$n$$$ waves of monsters. The $$$i$$$-th wave consists of $$$a_i$$$ monsters and happens from the $$$l_i$$$-th moment of time up to the $$$r_i$$$-th moments of time. All $$$a_i$$$ monsters spawn at moment $$$l_i$$$ and you have to exterminate all of them before the moment $$$r_i$$$ ends (you can kill monsters right at moment $$$r_i$$$). For every two consecutive waves, the second wave starts not earlier than the first wave ends (though the second wave can start at the same moment when the first wave ends) — formally, the condition $$$r_i \le l_{i + 1}$$$ holds. Take a look at the notes for the examples to understand the process better.
You are confident in yours and your character's skills so you can assume that aiming and shooting are instant and you need exactly one bullet to kill one monster. But reloading takes exactly $$$1$$$ unit of time.
One of the realistic mechanics is a mechanic of reloading: when you reload you throw away the old magazine with all remaining bullets in it. That's why constant reloads may cost you excessive amounts of spent bullets.
You've taken a liking to this mechanic so now you are wondering: what is the minimum possible number of bullets you need to spend (both used and thrown) to exterminate all waves.
Note that you don't throw the remaining bullets away after eradicating all monsters, and you start with a full magazine.
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2000$$$; $$$1 \le k \le 10^9$$$) — the number of waves and magazine size.
The next $$$n$$$ lines contain descriptions of waves. The $$$i$$$-th line contains three integers $$$l_i$$$, $$$r_i$$$ and $$$a_i$$$ ($$$1 \le l_i \le r_i \le 10^9$$$; $$$1 \le a_i \le 10^9$$$) — the period of time when the $$$i$$$-th wave happens and the number of monsters in it.
It's guaranteed that waves don't overlap (but may touch) and are given in the order they occur, i. e. $$$r_i \le l_{i + 1}$$$.
If there is no way to clear all waves, print $$$-1$$$. Otherwise, print the minimum possible number of bullets you need to spend (both used and thrown) to clear all waves.
2 3 2 3 6 3 4 3
9
2 5 3 7 11 10 12 15
30
5 42 42 42 42 42 43 42 43 44 42 44 45 42 45 45 1
-1
1 10 100 111 1
1
In the first example:
In the second example:
You are given a directed acyclic graph (a directed graph that does not contain cycles) of $$$n$$$ vertices and $$$m$$$ arcs. The $$$i$$$-th arc leads from the vertex $$$x_i$$$ to the vertex $$$y_i$$$ and has the weight $$$w_i$$$.
Your task is to select an integer $$$a_v$$$ for each vertex $$$v$$$, and then write a number $$$b_i$$$ on each arcs $$$i$$$ such that $$$b_i = a_{x_i} - a_{y_i}$$$. You must select the numbers so that:
It can be shown that for any directed acyclic graph with non-negative $$$w_i$$$, such a way to choose numbers exists.
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 18$$$; $$$0 \le m \le \dfrac{n(n - 1)}{2}$$$).
Then $$$m$$$ lines follow, the $$$i$$$-th of them contains three integers $$$x_i$$$, $$$y_i$$$ and $$$w_i$$$ ($$$1 \le x_i, y_i \le n$$$, $$$1 \le w_i \le 10^5$$$, $$$x_i \ne y_i$$$) — the description of the $$$i$$$-th arc.
It is guaranteed that the lines describe $$$m$$$ arcs of a directed acyclic graph without multiple arcs between the same pair of vertices.
Print $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$0 \le a_v \le 10^9$$$), which must be written on the vertices so that all $$$b_i$$$ are positive, and the value of the expression $$$\sum \limits_{i = 1}^{m} w_i b_i$$$ is the lowest possible. If there are several answers, print any of them. It can be shown that the answer always exists, and at least one of the optimal answers satisfies the constraints $$$0 \le a_v \le 10^9$$$.
3 2 2 1 4 1 3 2
1 2 0
5 4 1 2 1 2 3 1 1 3 6 4 5 8
43 42 41 1337 1336
5 5 1 2 1 2 3 1 3 4 1 1 5 1 5 4 10
4 3 2 1 2