Implement a uniform generator of pseudo-random pairs of integers ($$$a$$$, $$$b$$$) such that $$$1 \le a \le b \le k$$$. Explanation: each valid pair should be generated with equal probability upon each call to the generator.
The first line of the input contains an integer $$$k$$$ ($$$2 \le k \le 10^9$$$).
The second line contains an integer $$$n$$$ — the number of pairs to generate ($$$1 \le n \le 10000$$$).
Using the created generator, generate and output $$$n$$$ pairs. Output each pair on a separate line, separate elements of pairs with a space.
53
1 4 3 5 2 2
When checking solutions, it will be checked whether the resulting sample follows a uniform distribution law over the interval of acceptable values. No other quality checks of your generator will be performed.
There is a bishop on a chessboard of size $$$n$$$ x $$$n$$$. In one move, the bishop can move any number of cells diagonally.
Determine the number of possible paths for the bishop from cell ($$$x_1$$$, $$$y_1$$$) to cell ($$$x_2$$$, $$$y_2$$$) with the minimum number of moves.
The first line of input contains an integer $$$n$$$ - the size of the board ($$$1 \le n \le 10^{9}$$$). The second line of input contains two integers $$$x_1$$$ and $$$y_1$$$, and the third line contains two integers $$$x_2$$$ and $$$y_2$$$ ($$$1 \le x_1, y_1, x_2, y_2 \le n$$$).
Output a single integer - the number of different paths containing the minimum number of moves.
53 24 5
2
Illustration for the example in the statement:
A correct bracket sequence (CBS) is a string consisting only of round brackets, where each closing bracket has a corresponding opening one, and vice versa.
Examples of CBS: '()', '(())', '()(())'. Examples of strings that are not CBS: '())', ')(', '(()'.
A more strict definition of CBS:
Write a program to count the number of such CBS of length $$$2n$$$ that will remain CBS if you remove two central brackets (i.e., the brackets with numbers $$$n$$$ and $$$n+1$$$). For example, when $$$n$$$=3, the answer is 3 — these are the strings '((()))', '()()()', and '(()())'.
Input one integer $$$n$$$ ($$$1 \le n \le 30$$$).
Output one integer — the number of searched CBS.
3
3
Virtual memory technology allows running programs that require more memory than is installed in the computer. In most modern architectures, virtual memory is organized using page addressing. Let's consider this technology in a simplified way.
The entire virtual memory is divided into pages — fixed-length memory areas. When a program accesses a certain address, the page number is calculated from the address, and it is checked whether the page is in physical memory or swapped out to disk.
If the required page is swapped out to disk, it needs to be moved to physical memory. However, since physical memory is occupied by other pages, some page from physical memory needs to be moved to disk first. To determine the number of the page to be swapped out, the LRU (least recently used) method is used: the page that has not been accessed for the longest time will be moved to disk. If there are several such pages, let this be the page with the lowest number among them.
Your task is to simulate the operation of the described system.
The first line contains an integer $$$n$$$ — the size of virtual memory in pages ($$$1 \le n \le 2 \cdot 10^5$$$).
The second line contains an integer $$$m$$$ — the size of physical memory in pages ($$$1 \le m \le n$$$).
The third line contains an integer $$$k$$$ — the number of page accesses ($$$1 \le k \le 2 \cdot 10^5$$$).
The fourth line contains $$$k$$$ integers from $$$1$$$ to $$$n$$$ — the page numbers in the order of their access.
Before the program starts, the pages with numbers from 1 to $$$m$$$ are in physical memory, and the pages with numbers from $$$m+1$$$ to $$$n$$$ are on the disk.
Output $$$m$$$ integers in ascending order — the page numbers that are in physical memory at the end of the program.
3221 3
1 3
The statement of this problem is very simple: find the last non-zero digit in the number $$$1^1 \cdot 2^2 \cdot 3^3 ... \cdot n^n$$$.
Input contains one integer number $$$n$$$ ($$$1 \le n \le 10^6$$$).
Output one integer number from 1 to 9.
5
4
The factory has $$$N-1$$$ workshops for the production of various details. Each workshop has exactly one outgoing conveyor on which details are transferred to some other workshop. At the same time, each workshop is capable of receiving (and then sending through its conveyor) any number of details sent by other workshops to it.
It's almost time for assembly! Recently, yet one workshop with the number $$$N$$$ for the final assembly of products has been opened at the factory. Now it is necessary to build one or more additional conveyors so that any detail can eventually reach the workshop $$$N$$$.
Building conveyors is costly. For each workshop, the cost of building one additional conveyor outgoing from it is known (note that the destination workshop does not affect the cost). Determine the minimum sum required for building new conveyors, as well as which conveyors should be built. It is allowed to build several additional conveyors for any of the $$$N$$$ workshops.
The first line of the input data contains an integer $$$N$$$ ($$$3 \le N \le 2 \cdot 10^5$$$).
The second line contains $$${N-1}$$$ natural numbers $$$e_1$$$, $$$e_2$$$, $$$\dots$$$, $$$e_{N-1}$$$ ($$$e_i \le {N-1}$$$) — the numbers of the workshops where the conveyors arrive, outgoing from workshops with numbers $$$1$$$, $$$2$$$, $$$\dots$$$, $$${N-1}$$$, respectively.
The third line contains $$$N$$$ integers $$$c_1$$$, $$$c_2$$$, $$$\dots$$$, $$$c_N$$$ ($$$1 \le c_i \le 10^9$$$) — the costs of building one additional conveyor, transferring parts from workshops with numbers $$$1, 2, \dots, N$$$ respectively.
The first line of the output should contain two numbers $$$S$$$ and $$$K$$$ — the total cost of building new conveyors and their quantity.
Next, print $$$K$$$ lines containing two natural numbers $$$a_j$$$ and $$$b_j$$$, where $$$a_j$$$ is the number of the workshop where the $$$j$$$th new conveyor comes from, and $$$b_j$$$ is the number of the workshop where this conveyor arrives.
If there are multiple correct answers, output any.
42 3 114 13 12 11
12 1 3 4
52 1 4 31 1 1 1 1
2 2 2 3 4 5
Illustration for the first example:
Modest boy Misha calls a natural number modest if it has exactly 7 natural divisors. Help Misha find the number of modest numbers in the range from $$$a$$$ to $$$b$$$, inclusive.
Two integers $$$a$$$ and $$$b$$$ are entered, each on a separate line ($$$1 \le a \le b \le 10^{18}$$$).
Output one integer — the number of modest numbers in the range from $$$a$$$ to $$$b$$$.
50100
1
In the example, there is only one modest number in the range from 50 to 100 — it is the number 64.
One of the indicators of a scientist's productivity is the Hirsch index. The Hirsch index of a scientist is equal to $$$H$$$ if they have published at least $$$H$$$ scientific papers, each of which has at least $$$H$$$ citations (but not have $$$H+1$$$ papers with $$$H+1$$$ citations). For example, if a scientist has published 4 papers with 7, 4, 5, and 2 citations respectively, then their Hirsch index is 3.
To obtain a grant, the scientist Ivan Ivanovich needs to raise his Hirsch index to at least $$$H$$$. To achieve this, Ivan Ivanovich has made an agreement with his colleagues that they will add citations to his papers in their new articles, but no more than two citations in each article. Note that the same citation cannot appear twice in an article.
Determine the minimum number of new articles that Ivan Ivanovich's colleagues must publish in order for his Hirsch index becomes at least $$$H$$$.
The first line of the input contains an integer $$$N$$$ — the number of articles by Ivan Ivanovich ($$$1 \le N \le 10^5$$$).
The next line contains integers $$$L_1$$$, $$$L_2$$$, ..., $$$L_N$$$ — the current number of citations for each article ($$$0 \le L_i \le 10^9$$$).
The last line contains an integer $$$H$$$ ($$$1 \le H \le N$$$) — the required Hirsch index.
Output a single integer — the minimum number of new articles that Ivan Ivanovich's colleagues must publish.
4 7 4 5 2 4
2
3 1 1 2 2
1
Given a set of points on the plane. Find the smallest convex polygon containing all these points.
Two variants of the answer are required. In the first variant, you need to select the points that are at the vertices of the desired polygon. In the second answer, you need to select all points that are on the border of the desired polygon — both at the vertices and on the sides.
The first line of the input contains an integer $$$n$$$ — the number of points ($$$3 \le n \le 10^5$$$).
Each of the next $$$n$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ — the coordinates of the next point ($$$-10^9 \le x_i, y_i \le 10^9$$$).
It is guaranteed that no two points coincide and there exist three points that do not lie on the same line.
In the first line of the answer, output an integer $$$n_1$$$ — the number of points at the vertices of the polygon.
In each of the next $$$n_1$$$ lines, output a pair of integers — the coordinates of the next point in counterclockwise order. The first point should be the lowest, and if there are several such points, then the leftmost one.
In the next line, output an integer $$$n_2$$$ — the number of points at the vertices and on the sides of the polygon.
In each of the next $$$n_2$$$ lines, output a pair of integers — the coordinates of the next point in counterclockwise order. Similarly, the first point should be the lowest, and if there are several such points, then the leftmost one.
61 13 51 47 33 34 2
4 1 1 7 3 3 5 1 4 5 1 1 4 2 7 3 3 5 1 4
Illustration for the example from the statement:
There are $$$N$$$ stones in a pile. Two players take turns. On each turn, a player can take from $$$1$$$ to $$$K$$$ stones, but cannot take the same amount as their opponent took on the previous turn. The player who cannot make a move loses. Determine who will win if both players play optimally.
The first line of input contains an integer $$$T$$$ — the number of game rounds ($$$1 \le T \le 10$$$). The next $$$T$$$ lines contain two integers $$$N_i$$$ and $$$K_i$$$ each ($$$2 \le N_i \le 5000$$$, $$$2 \le K_i \le N_i$$$).
For each round, output 1 on a separate line if the first player wins, and 2 if the second player wins.
2 4 2 4 3
1 2
In the example, for $$$N=4$$$, $$$K=2$$$, the first player wins. He will take one stone. Now his opponent has only one move — to take two stones, and then the first player will take the remaining stone.
For $$$N=4$$$, $$$K=3$$$, the second player wins. If the first player takes 1 or 3 stones, the second player will take the remaining 3 or 1. If the first player takes 2 stones, the second player will take 1, and the first player will have no valid moves.
This version of the problem differs from the previous one only in the restriction on $$$N$$$.
There are $$$N$$$ stones in a pile. Two players take turns. On each turn, a player can take from $$$1$$$ to $$$K$$$ stones, but cannot take the same amount as their opponent took on the previous turn. The player who cannot make a move loses. Determine who will win if both players play optimally.
The first line of input contains an integer $$$T$$$ — the number of game rounds ($$$1 \le T \le 10$$$). The next $$$T$$$ lines contain two integers $$$N_i$$$ and $$$K_i$$$ each ($$$2 \le N_i \le 10^6$$$, $$$2 \le K_i \le N_i$$$).
For each round, output 1 on a separate line if the first player wins, and 2 if the second player wins.
2 4 2 4 3
1 2
In the example, for $$$N=4$$$, $$$K=2$$$, the first player wins. He will take one stone. Now his opponent has only one move — to take two stones, and then the first player will take the remaining stone.
For $$$N=4$$$, $$$K=3$$$, the second player wins. If the first player takes 1 or 3 stones, the second player will take the remaining 3 or 1. If the first player takes 2 stones, the second player will take 1, and the first player will have no valid moves.
Check the correctness of an arithmetic equality that can contain only decimal digits and the signs '+' and '-' (unary and binary). The equality should contain exactly one '='. The equality should not contain other characters including spaces. Leading zeros are allowed. Unary operations can be used multiple times in a row.
Examples of correct, incorrect, and malformed equalities:
The first line of input contains the equality (up to $$$3 \cdot 10^6$$$ characters, ASCII codes from 32 to 127 inclusive). The line ends with the end of line.
Output 'YES' if the equality is correct, 'NO' if it is incorrect but well-formed, and 'ERROR' if the equality is malformed.
-5+10+3=2+6
YES
2+2=5
NO
2*2=4
ERROR