The secret object $$$X$$$-$$$0619$$$ is located on a rectangular area with dimensions $$$H \times W$$$ meters.
To set up video surveillance of the object's territory, it was decided to use special drones. Each of these drones can be configured to monitor a square area of arbitrary size and location. Every point on the object's territory must be within the surveillance range of at least one drone. Due to the possibility of other secret objects being located near the secret object $$$X$$$-$$$0619$$$, no point outside the object's territory should fall within the surveillance range of any drone.
Determine the minimum number of drones required for this.
The input consists of a single line containing two integers $$$H$$$ and $$$W$$$ $$$(1 \leqslant H, W \leqslant 1000)$$$ - the length and width of the secret object.
Output a single integer - the minimum number of drones required to monitor the object X-0619.
3 9
3
4 3
2
The jury really loves even numbers. Right now we have a number with $$$n$$$ digits, but it could be odd. We need to fix this urgently! To do this, you are allowed to perform the following operation exactly once:
For example, using this operation on the number $$$5317$$$ can yield the numbers $$$5137, 3517$$$, and $$$1357$$$. Please make the number even and make the jury happy!
The first line contains an integer $$$n$$$ $$$(1 \le n \le 10^3)$$$ — the number of digits in the number.
The second line contains an integer with $$$n$$$ digits. This number does not contain any zeros.
If you cannot make the jury happy, print «NO».
Otherwise, in the first line, print «YES». In the second line, print two integers $$$L,R$$$ $$$(1 \le L \le R \le n)$$$ — the boundaries of the subsegment on which you performed the operation. In the third line, print the number obtained after the operation.
If there are multiple possible answers, you can print any of them.
5 43153
NO
6 654321
YES 1 6 123456
Bystroszczyot Algebrovic wanted to come up with a method for generating numbers, so he created an algorithm that takes a positive integer $$$x$$$ and generates the result according to the following scheme:
- Reduce the current number $$$x$$$ to $$$x-1$$$
- Double the current number $$$x$$$ to $$$2 \cdot x$$$
All steps of the algorithm should alternate, meaning that the algorithm should work in the following order: $$$1,2,1,2,\dots$$$. Additionally, the algorithm can start not from the first step, but from the second step, and should perform the steps in the following order: $$$2,1,2,1,\dots$$$. For example, from the number $$$7$$$, the algorithm can generate the numbers: $$$7 \rightarrow 14 \rightarrow 13 \rightarrow 26 \rightarrow \dots$$$ or the numbers $$$7 \rightarrow 6 \rightarrow 12 \rightarrow 11 \rightarrow \dots$$$.
Now Bystroszczyot wants to know, for a given number $$$i$$$, which numbers can generate the number $$$i$$$ if the algorithm is started from them? More precisely, let's define the set $$$B_i$$$ as all numbers from which the number $$$i$$$ can be obtained after some (possibly zero) number of algorithm iterations, and let $$$|B_i|$$$ denote the quontity of numbers in the set $$$B_i$$$. The numbers in the set $$$B_i$$$ will be called generating numbers for the number $$$i$$$. Bystroszczyot is interested in finding the total number of generating numbers for all integers from $$$l$$$ to $$$r$$$, in other words, the value of $$$\sum\limits_{i = l}^{r} |B_i|$$$. Help him calculate the answer!
The input consists of a single line containing two integers $$$l$$$ and $$$r$$$ $$$(1 \le l \le r \le 10^{18})$$$.
Output a single integer — the answer to the problem.
9 14
34
An important exam is coming up, which will be taken by $$$n$$$ students. All students will be seated in one classroom, which has $$$n$$$ desks. Each student and desk is numbered from $$$1$$$ to $$$n$$$. In total, the students will take $$$m$$$ exams. You have been tasked with preparing a seating arrangement plan for each exam, satisfying the following conditions:
- On any given day, all students must sit at different desks, meaning that exactly one desk should be assigned to each student.
- Each time, the students must sit differently, meaning that there should not be two days where the seating arrangement plans are completely identical.
- No student should sit at the same desk for consecutive exams.
The seating arrangement plan for one exam is represented by $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i \le n)$$$, which means that the $$$1$$$st student should sit at desk $$$a_1$$$, the $$$2$$$nd student should sit at desk $$$a_2$$$, and so on, until the $$$n$$$th student sits at desk $$$a_n$$$.
The input consists of a single line containing two integers $$$n$$$ and $$$m$$$ $$$(1 \le n,m \le 10^3)$$$.
If it is not possible to satisfy the requirements, output «IMPOSSIBLE» on the first line. Otherwise, output «POSSIBLE» on the first line, followed by $$$m$$$ lines, each containing $$$n$$$ integers representing the seating arrangement for each exam.
6 3
POSSIBLE 1 2 3 4 5 6 6 5 4 3 2 1 1 3 2 5 6 4
4 30
IMPOSSIBLE
Construct a convex hexagon on the plane with an area of $$$S$$$, where all coordinates are integers.
In a single line, there is one integer $$$S$$$ $$$(3 \le S \le 10^9)$$$.
Output twelve integers $$$x_1,y_1,x_2,y_2,\ldots,x_6,y_6$$$ $$$(-10^9 \le x_i, y_i \le 10^9)$$$ — the coordinates of the hexagon's vertices. Output the vertices in the order of traversing the figure clockwise or counterclockwise. All points must be different.
22
3 7 5 8 8 5 6 2 3 3 2 5
On June 12th, the City Day of Izhevsk will be celebrated! In connection with the holiday, Izhevsk State Technical University (IzSTU or Istu) decided to hang a large sign saying "Izhevsk". To make it more beautiful and interesting, they decided to order several posters drawn in different styles. Each of them has a text written in such a way that when they are combined in a certain order, they form the word "Izhevsk".
Today, Hrisipp picked up the made posters from the store, and there were exactly three of them. Help him to connect them into one large poster.
In a single line, three non-empty strings of Latin letters are given, separated by a single space. The length of each string does not exceed $$$5$$$.
In one line, output three words - the correct arrangement of the posters. Separate them with spaces.
I zh evsk
I zh evsk
he Iz vsk
Iz he vsk
Consider a sequence of integers $$$a_1, a_2, \ldots, a_n$$$. Define the function $$$g(x,y)$$$ as follows:
You are given $$$q$$$ pairs of integers $$$l_1, r_1, \ldots, l_q, r_q$$$. Calculate $$$q$$$ values $$$g(l_1,r_1), g(l_2,r_2), \ldots, g(l_q, r_q)$$$.
The first line contains two integers $$$n,q$$$ $$$(1 \le n, q \le 3 \cdot 10^5)$$$.
The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ $$$(-100 \le a_i \le 100)$$$.
Then follow $$$q$$$ lines. Each line contains two integers $$$l_i, r_i$$$ $$$(1 \le l_i \le r_i \le n)$$$.
Print $$$q$$$ lines, each containing a single integer — the answer for the corresponding segment. Output the answers for segments $$$l,r$$$ in the same order as they are given in the input.
4 2 4 1 3 5 2 3 3 4
13 23
At one of the programming olympiads, a survey was conducted by the organizers. The theme of the survey was programming language knowledge. Each respondent was given $$$n$$$ answer choices to choose from, and they could choose as many options as they wanted. The last answer choice was "other", indicating that the respondent knows some programming languages that are not listed as options.
The results of the survey were compiled, specifically $$$n$$$ numbers $$$a_1, a_2, \ldots, a_n$$$. Exactly $$$a_1$$$ respondents chose the first option, exactly $$$a_2$$$ respondents chose the second option, and so on. Unfortunately, the number of people surveyed was not recorded in the results - their quantity was not fixed. However, now it is necessary to know at least an approximate number. You have been asked to determine, based on the available data, the minimum and maximum number of programmers who could have been surveyed to obtain such results. It can be assumed that each person chose at least one answer option (at the very least, they would choose the "other" option).
The first line contains a single integer $$$n$$$ $$$(1 \le n \le 5000)$$$.
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ $$$(0 \le a_i \le 10^9)$$$.
Output two integers - the minimum and maximum, respectively.
3 1 0 1
1 2
Afanasiy recently came up with a great theorem, the Great Theorem of Afanasiy! So, the Great Theorem of Afanasiy (abbreviated as GTA) states that any number can be represented as the product of two non-negative numbers without trailing zeros.
Afanasiy asks you to verify if his theorem holds true for a given number $$$n$$$.
You need to solve the problem independently for $$$t$$$ different sets of input data.
The first line contains a single integer $$$t$$$ $$$(1 \leqslant t \leqslant 10^5)$$$ — the number of tests.
In each of the next $$$t$$$ lines, there is a single integer $$$n$$$ $$$(1 \leqslant n \leqslant 10^{18})$$$ — the value of $$$n$$$ for each test.
For each set of input data, output two integers $$$a, b$$$ $$$(1 \leqslant a, b \leqslant n)$$$ that satisfy the GTA for the number $$$n$$$.
If there are multiple valid answers, you can output any of them.
2 55 40
11 5 5 8
Danil, a well-known space traveler, decided to play the game "Caravan" with you. He wrote down the sequence $$$1,2,3,\ldots,n$$$ (in that exact order) and then chose a subarray — two integers $$$l,r$$$ $$$(1 \le l \le r \le n)$$$ and multiplied all the numbers with indices from $$$l$$$ to $$$r$$$ (inclusive) by a positive integer $$$x$$$. After that, all the numbers were randomly shuffled.
Your task is to figure out how Danil changed the permutation.
The first line contains a single integer $$$n$$$ $$$(1 \leqslant n \leqslant 2 \cdot 10^5)$$$ — the length of the permutation.
The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ $$$(1 \leqslant a_i \leqslant 10^{18})$$$ — the multiplied numbers.
Output three integers $$$l, r, x$$$ $$$(1 \leqslant l \leqslant r \leqslant n; 2 \leqslant x)$$$ — the left boundary of the range, the right boundary of the range, and the scaling factor, respectively.
It is guaranteed that there is a valid answer. If there are multiple answers, you can output any of them.
8 6 8 8 6 1 10 7 2
3 5 2
5 3 5 111111111111111 222222222222222 4
1 2 111111111111111
In the first example, the sequence $$$1,2,3,4,5,6,7,8$$$ was transformed into $$$1,2,6,8,10,6,7,8$$$ and after shuffling became $$$6,8,8,6,1,10,7,2$$$.
$$$n$$$ participants have already been invited to a new drone race. According to the organizers' plan, as soon as the race starts, each participant's drone will start moving from its starting position to its finishing position along a straight trajectory. The organizers have already determined the starting position for each participant.
Initially, it was also planned to select a separate finishing position for each participant individually. However, now, for the sake of a spectacular finale, the race organizers want to move the finishing positions of all participants to a single point. Of course, the distance between the starting and finishing positions for all participants must be the same. It is not possible to change the starting positions of the participants, but it is possible to change the race distance.
Help the organizers find such a distance and the common finishing position, or report that they do not exist.
The first line contains a single integer $$$n$$$ $$$(1 \le n \le 10^5)$$$ - the number of race participants.
Then follows $$$n$$$ lines, each containing two integers $$$x_i, y_i$$$ $$$(-1000 \le x_i, y_i \le 1000)$$$ - the starting position of the $$$i$$$-th race participant. Participants can start from the same points.
If there is no suitable finishing position for all participants, print «NO».
Otherwise, print «YES». Then, on the second line, print three numbers $$$x_e, y_e, d$$$ - the coordinates of the finishing position and the distance from the start to the finish.
If there are multiple possible answers, you can print any of them.
Your answer will be considered correct if the race distance for all participants is equal with an accuracy of $$$10^{-6}$$$.
2 2 -1 4 -3
YES 2.000000 -3.000000 2.000000