The seat numbering in a new "Lastochka" train carriage is shown in the diagram below:
| $$$\fbox{ 1 }$$$ $$$\fbox{ 5 }$$$ | $$$\fbox{13}$$$ $$$\fbox{17}$$$ | $$$\fbox{25}$$$ $$$\fbox{29}$$$ | ... |
| $$$\fbox{ 2 }$$$ $$$\fbox{ 6 }$$$ | $$$\fbox{14}$$$ $$$\fbox{18}$$$ | $$$\fbox{26}$$$ $$$\fbox{30}$$$ | ... |
| $$$\fbox{ 4 }$$$ $$$\fbox{ 8 }$$$ | $$$\fbox{16}$$$ $$$\fbox{20}$$$ | $$$\fbox{28}$$$ $$$\fbox{32}$$$ | ... |
| aisle | |||
| $$$\fbox{10}$$$ $$$\fbox{12}$$$ | $$$\fbox{22}$$$ $$$\fbox{24}$$$ | $$$\fbox{34}$$$ $$$\fbox{36}$$$ | ... |
| $$$\fbox{ 9 }$$$ $$$\fbox{11}$$$ | $$$\fbox{21}$$$ $$$\fbox{23}$$$ | $$$\fbox{33}$$$ $$$\fbox{35}$$$ | ... |
According to the diagram, there are blocks of 6 seats on one side of the aisle, and blocks of 4 seats on the other. All odd-numbered seats are located along the carriage walls (by the windows). Note that some seat numbers do not exist—for example, seats 3, 7, 15, 19, etc., are missing. The pattern for the subsequent numbering can be deduced from the diagram.
Vasya has purchased a ticket for seat number $$$x$$$. List the other seats in the same box as seat $$$x$$$ such that Petya ends up sitting next to Vasya.
A single integer $$$x$$$ is provided — the number of Vasya's seat ($$$1 \leq x \leq 10^9$$$).
Output several integers — all other seat numbers located in the same box as seat $$$x$$$. The numbers must be printed in ascending order. If Vasya made a mistake when telling the number to Petya, and a seat with number $$$x$$$ does not exist, then output -1.
Solutions that work for $$$x \le 36$$$ will be awarded 50 points.
6
1 2 4 5 8
21
22 23 24
3
-1
The Fibonacci sequence begins with the numbers $$$F_1=1$$$ and $$$F_2=1$$$. Each subsequent number is the sum of the two preceding ones. The indexing starts at one.
You are to construct a sequence of $$$n$$$ numbers that includes one "restart" after position $$$i$$$: that is, the first $$$i$$$ Fibonacci numbers ($$$2 \leq i \leq n - 2$$$) are written down, after which the sequence begins anew from $$$F_1$$$ and $$$F_2$$$ and continues following the same rule until there are exactly $$$n$$$ numbers in the sequence.
Choose the value of $$$i$$$ such that the sum of all $$$n$$$ numbers is minimized. If multiple positions yield the same sum, choose the smallest $$$i$$$.
A single integer $$$n$$$ ($$$6 \le n \le 80$$$).
On the first line, output the chosen position $$$i$$$. On the second line, output the $$$n$$$ numbers of the resulting sequence, separated by spaces.
Each passed test yields an equal number of points; a complete solution receives 100 points.
6
3 1 1 2 1 1 2
7
3 1 1 2 1 1 2 3
Note that the answer may exceed the maximum value of a 32-bit integer variable; therefore, you must use a 64-bit integer data type (the 'int64' type in Pascal, 'long long' in C++, and 'long' in Java and C#). In Python, no additional steps are required.
The mad genius Dr. Shpuntik is assembling an army of robotic "hedgehogs" out of scrap metal. Before him lies a massive iron structure consisting of $$$n$$$ circular components (gears) connected by $$$m$$$ steel rods (each rod connects exactly two components). To activate a single robotic hedgehog, the doctor must select one component and a subset of the steel rods attached to it — these will serve as the "spines." For a robotic hedgehog to be considered valid and ready for operation, it must have at least three spines.
Shpuntik dislikes monotony, so every robot he creates must be unique. Two robotic hedgehogs are considered distinct if they are based on different components, or if they have different sets of spines (i.e., the sets of rods chosen from the same component are not identical). The doctor wants to determine the total number of distinct, valid robotic hedgehogs that can be formed from his structure. There are so many potential hedgehogs that Shpuntik cannot manage the count on his own. Since the number of robots can be extremely large, please output the answer modulo $$$10^9 + 7$$$.
Formally: you are given an undirected graph. You need to calculate the number of subgraphs that take the form of a "hedgehog" — a structure consisting of a central vertex connected by edges to at least three other vertices, with no additional edges included. Note that while the vertices at the ends of the "spines" might be connected to each other in the original graph, these connections are not included when defining the "hedgehog" subgraph. Two "hedgehogs" are considered distinct if there is at least one vertex present in one that is not present in the other. You need to calculate the remainder when the number of "hedgehogs" is divided by $$$10^9 + 7.$$$
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 3 \cdot 10^5$$$, $$$n - 1 \le m \le 3 \cdot 10^5$$$), representing the number of components and the number of rods in the structure, respectively. The following $$$m$$$ lines contain descriptions of the rods. Each line contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$), representing the endpoints of a rod. It is guaranteed that the structure is connected and that no rod description is repeated.
Output a single integer — the number of distinct hedgehog-robots in the given construction, modulo $$$10^9 + 7$$$ (i.e., the remainder when divided by $$$10^9 + 7$$$).
Subtask 1 (up to 20 points): $$$n, m \le 15$$$
Subtask 2 (up to 24 points): $$$n, m \le 2000$$$
Subtask 3 (up to 56 points): $$$n, m \le 3 \cdot 10^5$$$
4 31 21 31 4
1
5 41 21 31 41 5
5
A note on the Python language: two numbers separated by a space can be read as follows:
n, m = map(int, input().split())
We are given data on the profit of an IT company over $$$n$$$ consecutive days. For an aesthetically pleasing report, we need to select the maximum number of days such that the following two conditions are met:
The first line of the input contains an integer $$$n$$$ ($$$1 \le n \le 10^4$$$).
The next $$$n$$$ lines contain integers in the range from $$$0$$$ to $$$10^5$$$ — the company's profit for each of the $$$n$$$ days.
Output a single integer — the maximum number of days in the report.
Subtask 1 (up to 50 points): $$$n \le 10$$$
Subtask 2 (up to 50 points): $$$n \le 5000$$$
74213105
3
3321
1
In the first example, you can select days numbered 2, 4, and 7 for the report.
Grandmother stores jam in a long container divided into $$$N$$$ consecutive sections. Section $$$i$$$ contains $$$a_i$$$ units of jam.
Grandmother chooses a non-empty contiguous range of sections—from section $$$i$$$ to section $$$j$$$ inclusive — and collects all the jam from these sections into jars (she does this exactly once). The boundaries of this range can be the partitions between sections or the ends of the container.
Each jar has a capacity of $$$M$$$. Grandmother fills only complete jars; any remaining jam that is insufficient to fill another full jar is discarded.
Find the minimum amount of jam that must be discarded.
The first line contains two integers $$$N$$$ and $$$M$$$ ($$$1 \le N \le 2\,000\,000$$$, $$$N \lt M \le 10\,000\,001$$$).
The second line contains $$$N$$$ integers $$$a_1, a_2, \ldots, a_N$$$ ($$$1 \le a_i \le 10^9$$$).
Output a single integer — the minimum amount of jam discarded.
Subtask 1 (up to 30 points): $$$N \le 2\,000$$$.
Subtask 2 (up to 30 points): $$$N \le 200\,000$$$.
Subtask 3 (up to 40 points): no additional constraints.
3 105 8 6
3
1 22
0
1 100000011000000000
9999901
Additional test cases, which were not present during the competition, have been added to the problem.
Note for Python users. A sequence of integers separated by spaces can be read as follows:
a = [int(x) for x in input().split()]
Note on fast I/O. The final subtask involves a large volume of input data. In some programming languages, you may need to use specific techniques to speed up input operations.
In C++, simply add the following lines to the beginning of your main function:
ios_base::sync_with_stdio(false);
cin.tie(0);
In Java, use BufferedInputStream and read integers directly from the byte stream. Using Scanner for large inputs can be too slow.
In C#, use BufferedStream wrapped around Console.OpenStandardInput() and read integers from the byte stream. Reading an entire line using Console.ReadLine().Split() creates many string objects, which can be both time-consuming and memory-intensive.
Python users are advised to submit their solutions using PyPy.