Today in the math class, Sasha was told about Pascal's triangle. In this triangle, ones are placed at the top and on the sides. Each number is equal to the sum of the two numbers above it. The first six rows of the triangle look like this:
Using this rule, the triangle can be made as large as desired. Sasha wondered if the number $$$n$$$ is in this triangle and where it is located. After quickly solving the problem, Sasha rewarded himself with a chocolate. Can you solve this problem too?
The input consists of a single natural number $$$n$$$ $$$(1\le n \le 10^{6})$$$.
If the number $$$n$$$ is in the triangle, output two non-negative integers $$$x, y$$$ $$$(0 \le y \le x \le 10^{18})$$$ - the row number and the position in this row where the number $$$n$$$ is located in the triangle. It is guaranteed that these constraints are sufficient to output the answer.
If the number $$$n$$$ is not in the triangle, output a single number $$$-1$$$.
Remember that the numbering of rows starts from $$$0$$$ and the numbering of numbers in each row also starts from $$$0$$$.
If there are multiple positions with the number $$$n$$$, you can output any of them.
1
0 0
2
2 1
10
5 3
Fedya was very happy to learn about the concept of GCD (Greatest Common Divisor) of numbers.
The greatest common divisor (GCD) of two natural numbers $$$m$$$ and $$$n$$$ is the largest of their common divisors. The concept of the greatest common divisor is naturally extended to sets of more than two natural numbers, as the greatest of the common divisors of all these numbers.
But what is the GCD of a single number? Let's assume that for natural numbers, it is the number itself. However, Fedya doesn't like such a boring generalization and he came up with his own concept - GSD.
Let's call the greatest substring divisor (GSD) of a number the greatest common divisor of all its non-empty substrings.
A substring is a continuous sequence of characters within a string. For example, for the number $$$171$$$, the substrings are: $$$1$$$, $$$17$$$, $$$171$$$, $$$7$$$, $$$71$$$, and $$$1$$$, while the numbers $$$11$$$ and $$$2$$$ are not its substrings.
Given a natural number $$$n$$$ $$$(1 \le n \le 10^{10^6})$$$, find its GSD.
There is a single natural number $$$n$$$ $$$(1 \le n \le 10^{10^6})$$$. It is guaranteed that $$$n$$$ does not contain $$$0$$$.
Output the GSD($$$n$$$).
6
6
28
2
171
1
The condition presents all substrings of the number $$$171$$$ from the third example, their GCD is equal to $$$1$$$.
Arthur and Nikita, tired of playing chess, came up with a new game. Each player starts with a number, $$$a$$$ and $$$b$$$ respectively. First, Arthur appends $$$n$$$ digits to the right of his number $$$a$$$, then Nikita appends $$$m$$$ digits to the right of his number $$$b$$$. The winner is the player whose resulting number is greater. Your task is to determine the outcome of the game given the numbers $$$a$$$, $$$b$$$, $$$n$$$, and $$$m$$$, assuming that both players follow an optimal strategy.
The input consists of a single line containing four integers $$$a$$$, $$$b$$$, $$$n$$$, and $$$m$$$ $$$(1 \le a, b, n, m \le 10^9)$$$.
Output the word "Arthur" if Arthur wins, "Nikita" if Nikita wins, and "Draw" if the game ends in a tie.
1 2 3 4
Nikita
54 54 54 54
Draw
11 10 2 2
Arthur
Olya has a garden with $$$n$$$ roses. All roses are arranged in a row and numbered from $$$1$$$ to $$$n$$$. The height of the $$$i$$$-th rose is $$$a_i$$$ centimeters.
Olya wants each rose to look beautiful. She believes that a rose looks beautiful if the heights of its neighbors have the same parity; the edge roses are always considered beautiful.
To make the garden beautiful, Olya has a magic fertilizer that instantly increases the height of any rose by $$$1$$$ centimeter. Olya does not want to spend a lot of fertilizer, so she needs to know the minimum number of times she needs to apply the fertilizer to make all the roses in the garden beautiful.
The first line contains an integer $$$n$$$ $$$(1 \le n \le 100000)$$$ — the number of roses in the garden.
The second line contains $$$n$$$ integers $$$a_i$$$ $$$(1 \le a_i \le 10^9)$$$ — the heights of all roses in the order of their numbers.
Output a single integer — the minimum number of times the fertilizer needs to be applied to make all the roses look beautiful.
3 5 4 5
0
3 5 5 5
0
7 3 12 4 6 2 3 3
3
There is only one way to change the garden — apply the magic fertilizer to the roses.
Once Maxim thought that it would be great to solve programming problems every day, it would definitely brighten up his life. Then he saw that on a popular website, statistics are kept not only on the number of consecutive days that Maxim solves problems, but also on the number of problems solved per month (it is well known that month $$$k$$$ has $$$k$$$ days).
Now Maxim has set himself a new challenge — to solve problems every day so that the number of problems solved per month is always not less than the number of consecutive days that Maxim solves problems. Moreover, every day he must solve at least one problem.
The number of problems solved per month means the number of problems solved in the last $$$k$$$ days, including the current day. That is, if the day is in the middle of the month, then all problems solved from the middle of last month to the present day are summed up. For example, on May 16, it will be considered that the total number of problems solved for the month is the sum of the problems solved from April 17 to May 16 inclusive.
It is known that he already meets this condition for $$$n$$$ days. It is interesting what is the minimum number of problems that Maxim solved during this period.
The input consists of a single line containing two integers $$$k, n$$$ ($$$1 \le k, n \le 10^6$$$) — the number of days in the month and the duration of the challenge.
Output a single number — the minimum number of problems that Maxim solved during these $$$n$$$ days.
2 3
4
30 15
15
30 365
2405
Let's consider the first example:
Diana dreamed of a strange black and white field, in which each cell is painted either black or white. Diana immediately came up with the idea of building a wall at the junction of two cells, but only if they are of different colors; it is not allowed to build walls on the border of the field.
But now she wonders what is the length of the side of the largest square that can be enclosed by walls according to the described rules. Only you can save her by telepathically sending the answer to her dream. Hurry up! Diana is about to wake up and go to school.
If it is impossible to enclose a square, output 0.
The first line contains two natural numbers $$$n, m$$$ $$$(3 \le n, m; n \cdot m \le 3 \cdot 10^5 )$$$ — the dimensions of the field. Then $$$n$$$ lines of length $$$m$$$ are entered, describing the field.
Output a single number - the length of the side of the largest square.
5 6 BBBBWB WBWWBW BWBWBB BWWBBW WBWBBW
2
4 4 WBWB BWWW WWWB BWBW
0
3 3 BWW WBW WWB
1
The picture corresponds to the first example, the desired square with a side of 2 is highlighted, it is obvious that a larger square cannot be enclosed:
The castle of King Timur is under siege: a monster with clawed paws has appeared outside the city walls. To banish the monster, the wizard of the castle, Emil, will need a lot of time to cast a repelling spell, so he asks the king to hold the monster back for as long as possible.
The wall of the castle will hold the monster. The wall is divided into $$$n$$$ parts of equal width, numbered from $$$1$$$ to $$$n$$$. Each part of the wall has its own height $$$h_i$$$. To penetrate the castle, the monster will have to destroy the entire wall. The destruction of the wall occurs as follows: the monster (which has exactly $$$k$$$ claws on its paws) approaches a certain part of the wall (without spending time on it) and, if the height of the part of the wall is divisible by $$$k$$$, instantly destroys that part (reduces the height to 0). Otherwise, it takes $$$1$$$ minute to reduce the height of that part from $$$h_i$$$ to $$$\lfloor \frac{h_i}{k} \rfloor$$$ (division rounded down to the nearest integer). The monster repeats this procedure until the entire wall is destroyed, i.e. the height of all parts is reduced to zero.
In addition to the wall, Timur has $$$m$$$ scrolls with spells of power $$$c$$$. Timur can use each of the scrolls to increase the height of one (any) part of the wall by a value chosen by him from $$$1$$$ to $$$c$$$. At the same time, magic will affect no more than one part of the wall, and the scrolls can only be used before the monster starts breaking the wall.
Help King Timur determine the maximum number of minutes the wall can hold the monster after being reinforced.
The first line contains two integers separated by a space: $$$n, k$$$ $$$(1 \le n \le 10^5; 2 \le k \le 10^4)$$$ — the number of parts of the wall and the number of claws on the monster's paws, respectively.
The second line contains $$$n$$$ integers separated by a space: $$$h_i$$$ $$$(0 \le h_i \le 10^9)$$$ — the heights of the parts of the wall.
The third line contains two integers separated by a space: $$$m, c$$$ $$$(0 \le m \le n; 1 \le c \le 10^9)$$$ — the number of scrolls and their power.
Output a single number — the maximum time in minutes that the wall can hold the monster.
5 2 1 1 1 2 2 3 1
7
5 2 1 1 1 2 2 3 4
8
4 9 10 85 9 3 0 7
4
Let's consider the third example:
In total, the monster destroys the wall in $$$4=2+1+0+1$$$ minutes, and King Timur cannot increase this time, since there are no magic scrolls.
Once Senya was walking around Kaliningrad and discovered an interesting graph store called "Ostovok". This store stood out from many ordinary graph stores in that it only sold spanning trees (see definition). Upon entering the store, Senya discovered the only remaining graph on the counter - a complete graph on $$$n$$$ vertices (denoted $$$K_n$$$). Senya decided to buy as many spanning trees as possible, and the store clerk, the full Lady Lucy Decart, was ready to cut any spanning tree from the graph that Senya indicated to her. The cost of a spanning tree is equal to its diameter (see definition). When a spanning tree is cut from the graph, the vertices in the graph remain, but the edges contained in the spanning tree disappear.
It is necessary to find the maximum number of spanning trees that Senya can cut from $$$K_n$$$, and their total cost should be as minimal as possible. In other words, it is necessary to find as many non-intersecting spanning trees as possible, and among all such sets, the one in which the sum of the diameters of the spanning trees is minimal.
A spanning tree of a graph is a tree, a subgraph of the given graph, with the same number of vertices as the original graph.
A tree is a connected graph without cycles. Connectivity means the existence of a path between any pair of vertices.
A subgraph is a part of a graph in which we take some of its vertices and edges. In other words, the graph $$$H$$$ is a subgraph of the graph $$$G$$$ if the vertices and edges of $$$H$$$ are a subset of the vertices and edges of $$$G$$$.
The diameter of a graph is the number equal to the distance between the farthest apart vertices of the graph.
The input consists of a single number $$$n$$$ ($$$2\le n \le 1000$$$) - the number of vertices in the complete graph.
In the first line, output a single number $$$k$$$ - the maximum number of spanning trees that Senya can buy.
Then output $$$k$$$ sets of $$$n-1$$$ lines each, each describing one of the $$$k$$$ spanning trees as $$$n-1$$$ edges.
If there are multiple optimal answers, any of them can be output.
The spanning trees in the output are separated by line breaks for ease of understanding, but it is not necessary to include line breaks between the spanning trees.
2
1 1 2
3
1 1 2 1 3
4
2 1 2 2 3 3 4 1 3 1 4 2 4
Illustrations for examples, edges of the same color form spanning trees.
In the third example, a variant of dividing into two spanning trees, each with a diameter of $$$3$$$, is proposed, i.e. the sum of the diameters is $$$6$$$. It can be proven that a larger number of spanning trees cannot be obtained, and it is impossible to divide the graph $$$K_4$$$ into two spanning trees with a sum of diameters less than $$$6$$$.
