An infinite grid is filled with consecutive natural numbers arranged in the form of concentric rhombuses. The filling of each rhombus starts from its top cell and goes clockwise — see the figure. The cell containing the number 1 is called the central cell.
Write a program that, for a given pair of values x and y, will find the number in the cell that is x steps horizontally and y steps vertically away from the central cell.
Two integers $$$x$$$ and $$$y$$$ are entered, each on a separate line ($$$-10^6 \le x, y \le 10^6$$$).
Output a single integer — the answer.
Subtask 1 (up to 36 points): $$$-3 \le x, y \le 3$$$.
Subtask 2 (up to 32 points): $$$-1000 \le x, y \le 1000$$$.
Subtask 3 (up to 32 points): $$$-10^6 \le x, y \le 10^6$$$.
2 1
16
-1 -2
21
Note that the answer in the last subtask may be quite large and may not fit into a 32-bit data type. It is recommended to use a 64-bit data type, for example, the long long type in C++, the int64 type in Pascal, the long type in Java and C#. Python automatically works with integers of any length.
The alphabet of a certain language consists of only three letters — a, o, and c. Determine the maximum number of words of length N that can exist in the language, if each letter of the alphabet can appear in a word no more than K times.
Two integers $$$N$$$ and $$$K$$$ are entered, each on a separate line ($$$1 \le N, K \le 30$$$).
Print a single integer — the number of words.
Subtask 1 (up to 25 points): $$$K \le 2$$$
Subtask 2 (up to 35 points): $$$N \le 15$$$
Subtask 3 (up to 40 points): $$$N \le 30$$$
2 1
6
2 2
9
In the first example, the answer is 6 — these are the words ao, oa, oc, co, ac, and ca. In the second example, the answer is 9, as it also includes the words aa, oo, and cc.
Note that the answer in the last subtask can be quite large and may not fit into a 32-bit data type. It is recommended to use a 64-bit data type, for example, the long long type in C++, the int64 type in Pascal, the long type in Java and C#. Python automatically works with integers of any length.
Experienced employee Ivan Ivanovich is often sent on business trips to various cities. In the near future, he is scheduled to make $$$N$$$ business trips. For each trip, the range of days and the city where Ivan Ivanovich should be on those days are known.
Unfortunately, when scheduling business trips, the management sometimes makes mistakes. It may happen that on some day Ivan Ivanovich is supposed to be in two (or more) different cities at the same time. Write a program to count the number of such days.
The first line contains the number of business trips $$$N$$$ ($$$2 \le N \le 10^5$$$).
In each of the following $$$N$$$ lines, the start day $$$d_1$$$, the end day $$$d_2$$$ of the next business trip ($$$1 \le d_1 \le d_2 \le 10^9$$$), and the city number $$$c$$$ ($$$1 \le c \le 10^9$$$) are written separated by a space. The input data is sorted in non-decreasing order of $$$d_1$$$.
Print a single integer — the number of days in question.
Solutions that work correctly for $$$N \le 1000$$$, $$$d_2 \le 1000$$$, can score up to 50 points.
3 1 7 5 2 4 5 2 3 2
2
In the example, on the second and third days, Ivan Ivanovich is supposed to be simultaneously in cities 2 and 5.
Let's assume that all cities are located close to each other, so travel time is not considered in this problem.
Note for Python programmers: three numbers written separated by a space can be read as follows:
d1, d2, c = map(int, input().split())
Let's call a non-negative integer fun if it consists of no more than two different digits — for example, 555, 272772, 100.
Calculate the number of ways the input number can be represented as the sum of two fun numbers. Swapping the addends does not yield a new way.
A non-negative integer $$$n$$$ is entered ($$$0 \le n \le 10^9$$$).
Print a single integer — the number of ways to represent $$$n$$$ as the sum of two fun numbers without considering the order of the addends.
Subtask 1 (up to 30 points): $$$n \le 100$$$.
Subtask 2 (up to 30 points): $$$n \le 10^4$$$.
Subtask 3 (up to 40 points): $$$n \le 10^9$$$.
3
2
123
52
In the first example, the number 3 can be represented in two ways: 0 + 3 and 1 + 2.
A correct bracket sequence (CBS) is defined as a string consisting only of round brackets, where each closing bracket has a corresponding opening bracket, and vice versa. Examples of CBS: '()', '(())', '()(())'. Examples of strings that are not CBS: '())', ')(', '(()'.
We call a CBS of length $$$2n$$$ symmetric if for any $$$i$$$ from $$$1$$$ to $$$n$$$, it is true that the $$$i$$$-th bracket from the beginning is not equal to the $$$i$$$-th bracket from the end. For example, for $$$n=3$$$ the following CBS are symmetric: '((()))', '()()()', and '(()())'.
Write a program that calculates the number of symmetric CBS of length $$$2n$$$.
A single integer $$$n$$$ is input ($$$1 \le n \le 50$$$).
Output a single integer — the number of symmetric CBS of length $$$2n$$$.
Subtask 1 (up to 45 points): $$$n \le 10$$$
Subtask 2 (up to 25 points): $$$n \le 20$$$
Subtask 3 (up to 30 points): $$$n \le 50$$$
3
3
Note that the answer in the last subtask can be quite large and may not fit into a 32-bit data type. It is recommended to use a 64-bit data type, for example, the long long type in C++, the int64 type in Pascal, the long type in Java and C#. Python automatically works with integers of any length.