Argyle — a pattern of diamonds or squares arranged in a checkerboard order and forming parallel and transverse stripes of different colors. The name comes from the Scottish Campbell clan in the county of Argyll. This ornament became especially popular in the 20th century thanks to the company "Pringle of Scotland", which began producing high-end knitwear with the "Argyle" pattern, after which it became a hallmark of the aristocracy. Since then, the pattern has never gone out of fashion. There are a huge number of color variations of this ornament. This pattern is especially popular on sweaters, vests, cardigans, dresses, scarves, socks, and leg warmers.
Determine the number of red and green squares on a fabric of size $$$n \times n$$$.
The only line of input contains a natural number $$$n$$$ ($$$1 \le n \le 10^{9}$$$).
$$$\textbf{Note}$$$ that under the given constraints, you need to use a $$$64$$$-bit data type to store the answer, for example $$$\textbf{long}$$$ $$$\textbf{long}$$$ in $$$\textbf{C++}$$$, $$$\textbf{int64}$$$ in $$$\textbf{Free}$$$ $$$\textbf{Pascal}$$$, $$$\textbf{long}$$$ in $$$\textbf{Java}$$$.
Print two non-negative integers in two lines — the answer to the problem. In the first line print the number of red squares, in the second — the number of green squares.
Solutions that work correctly for $$$n \le 10^{5}$$$ will be awarded 50 points.
3
1 1
4
1 4
Peter and his friends are going to celebrate the successful end of the school year. For this, they decided to buy $$$n$$$ packs of orange juice and $$$m$$$ packs of apple juice and allocated $$$s$$$ rubles (russian currency) for these purposes.
One pack of any juice costs $$$r$$$ rubles. However, juice can also be bought by boxes. One box contains $$$k$$$ packs of juice of one kind and costs $$$p$$$ rubles (it is known that $$$k \cdot r \gt p$$$).
The friends want to buy as many packs of juice as possible with the money they have, but so that there are at least $$$n$$$ packs of orange juice and at least $$$m$$$ packs of apple juice.
How many packs of juice can the friends buy under these conditions?
The first line contains an integer $$$n$$$ $$$(1 \le n \le 5 \cdot 10^5)$$$ — the required number of packs of orange juice.
The second line contains an integer $$$m$$$ $$$(1 \le m \le 5 \cdot 10^5)$$$ — the required number of packs of apple juice.
The third line contains an integer $$$r$$$ $$$(1 \le r \le 1000)$$$ — the price of one pack of juice (of any kind).
The fourth line contains an integer $$$k$$$ $$$(2 \le k \le 10^6)$$$ — the number of packs of juice in one box.
The fifth line contains an integer $$$p$$$ $$$(1 \le p \lt k \cdot r)$$$ — the price of one box containing $$$k$$$ packs of juice.
The sixth line contains an integer $$$s$$$ $$$(1 \le s \le 10^9)$$$ — the amount of money allocated for buying juice.
Print one integer — the maximum possible total number of packs of juice that can be bought.
If it is impossible to buy juice while satisfying the described conditions, print $$$-1$$$.
Solutions that work correctly when at least one of the values $$$n$$$ or $$$m$$$ is divisible by $$$k$$$ will be awarded $$$25$$$ points.
878053701400
18
878052251200
25
878053751100
-1
In the first example, one needs to buy $$$8$$$ packs of orange juice and $$$7$$$ packs of apple juice. One pack costs $$$80$$$ rubles, and a box of $$$5$$$ packs costs $$$370$$$ rubles. For $$$1110$$$ rubles, it is possible to buy $$$3$$$ boxes of juice, for example, two boxes of orange juice and one box of apple juice. Then $$$1400 - 3 \cdot 370 = 290$$$ rubles will remain: $$$240$$$ rubles are enough for $$$3$$$ packs of apple juice (or $$$2$$$ packs of apple juice and $$$1$$$ pack of orange juice), and $$$50$$$ rubles will remain. The conditions will be satisfied, and in total $$$3 \cdot 5 + 3 = 18$$$ packs of juice will be bought.
In the second example, for $$$1200$$$ rubles it is possible to buy $$$5$$$ boxes of juice for $$$225$$$ rubles each. If we take three boxes of orange juice and two boxes of apple juice, then the conditions will be satisfied. Then $$$1200 - 5 \cdot 225 = 75$$$ rubles will remain, and nothing can be bought with them.
In the third example, for $$$1100$$$ rubles it is possible to buy $$$2$$$ boxes of juice for $$$375$$$ rubles each: one box of orange juice and one box of apple juice. Then $$$1100 - 2 \cdot 375 = 350$$$ rubles will remain, and three more packs of orange juice and two packs of apple juice need to be bought. At a pack price of $$$80$$$ rubles, this is impossible.
An art object consists of $$$n$$$ columns with heights $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ centimeters. Critics believe that the art object will look better if the column heights are nondecreasing, that is, the height of each column must be no less than the height of the previous one ($$$a_i \ge a_{i-1}$$$ for all $$$i \ge 2$$$).
Since the order of the columns cannot be changed (this would destroy the author's idea), the columns can be placed on a staircase whose step height is $$$d$$$. In this case, one column will stand on each step, and the first column must stand on the first step. Then the height of the first column $$$a_1$$$ increases by $$$d$$$, the height of the second column $$$a_2$$$ increases by $$$2d$$$, the value of $$$a_3$$$ increases by $$$3d$$$, and so on.
To keep the art object from becoming too bulky, it is necessary to find the minimum suitable step height $$$d$$$ such that the column heights become nondecreasing.
The first line of the input contains an integer $$$n$$$ ($$$1 \le n \le 2\cdot 10^5$$$) — the number of columns.
The next $$$n$$$ lines contain the heights of the columns $$$a_i$$$, $$$1\le a_i \le 10^9$$$.
The program must output the minimum suitable step height $$$d$$$. If the column heights are already nondecreasing, output $$$0$$$.
Solutions that work correctly for $$$n \le 2$$$ will be awarded $$$20$$$ points.
Solutions that work correctly for $$$a_i \le 10$$$ will be awarded $$$30$$$ points.
515275
3
In the first example, the column heights are $$$1, 5, 2, 7, 5$$$. If a staircase with step height $$$d=3$$$ is used, the column heights become $$$4, 11, 11, 19, 20$$$. If step height $$$d=2$$$ is used, the heights become $$$3, 9, 8, 15, 15$$$, and then column number 2 will be higher than column number 3.
In one of the restaurants, a dispute arose among $$$n$$$ chefs: what should the length of rice be? Each chef has their own opinion: the $$$i$$$-th chef believes that the length should be $$$h_i$$$ millimeters.
A chef can convince another chef if their opinions about the rice length differ by one (that is, the $$$i$$$-th chef can convince the $$$j$$$-th one if $$$|h_i - h_j| = 1$$$). If the $$$i$$$-th chef convinces the $$$j$$$-th chef, then the value of $$$h_j$$$ becomes equal to the value of $$$h_i$$$. A convinced chef may then change their opinion again.
The restaurant's purchasing manager needs to buy rice of one length. Determine the maximum number of chefs that can be satisfied after some chefs may convince each other (in other words — the largest number of chefs who can come to a common opinion about the rice length).
The first line of the input contains one natural number $$$n$$$ ($$$1 \leqslant n \leqslant 10^5$$$) — the number of chefs.
Each of the next $$$n$$$ lines contains one natural number $$$h_i$$$ ($$$1 \leqslant h_i \leqslant 10^9$$$) — the ideal rice length according to the $$$i$$$-th chef.
The program should output one number — the maximum number of chefs who can come to a common opinion about the rice length.
Solutions that work correctly when $$$n \leqslant 10^3$$$ and all $$$h_i$$$ are distinct will be awarded 20 points.
Solutions that work correctly when $$$n \leqslant 10^3$$$ will be awarded 60 points.
72342687
4
In the sample from the statement, the chefs have the following preferences for rice length: 2, 3, 4, 2, 6, 8, 7. First, the second chef will convince the third one that the rice length should be 3. Then the first chef will convince the second and third ones that 2 is a suitable length. Also, the fourth chef believes that 2 is a suitable length, so 4 chefs agreed that length 2 is suitable.
Peter is a beginner artist. Since he has little experience, he is currently practicing drawing harmonious stripes.
Each stripe drawn by Peter consists of $$$n$$$ consecutive cells, each of which can be painted in one of $$$m$$$ colors. The brightness of a stripe is defined as the sum of the absolute differences between the colors of adjacent cells. For example, the brightness of the stripe $$$\{3, 1, 5, 2\}$$$ is $$$|3-1| + |1-5| + |5-2| = 9$$$, and the brightness of the stripe $$$\{1, 1, 2\}$$$ is $$$|1-1| + |1-2| = 1$$$.
Like any artist, Peter has a very strong sense of beauty, and it tells him that the stripe will be more beautiful the smaller its brightness is. At the moment, the paint of color $$$i$$$ that Peter has is enough to paint no more than $$$a_i$$$ cells. Help the artist — determine the minimum brightness that a stripe drawn by Peter can have.
The first line contains the number $$$n$$$ ($$$1 \leq n \leq 10^9$$$) — the length of the stripe.
The second line contains the number $$$m$$$ ($$$1 \leq m \leq 3 \cdot 10^5$$$) — the number of colors available to Peter.
The $$$i$$$-th of the following $$$m$$$ lines contains the number $$$a_i$$$ ($$$0 \leq a_i \leq 10^9$$$) — the number of cells that can be painted with the paint of color $$$i$$$ that Peter has.
It is guaranteed that $$$n \leq a_1+\dots+a_m$$$ (i.e. Peter has enough paint to color all cells).
Print a single number — the minimum brightness that a stripe drawn by Peter can have.
Solutions that work correctly for $$$m \leq 3$$$ will be awarded 20 points.
Solutions that work correctly for $$$n, m \leq 6$$$ will be awarded 25 points.
Solutions that work correctly for $$$m \leq 100$$$ will be awarded 60 points.
Solutions that work correctly for $$$m \leq 1500$$$ will be awarded 70 points.
7502311
3
63143
1