A sequence of positive integers is $$$1$$$-stable if any two adjacent elements in it differ by at most $$$1$$$.
For two sequences of the same length, one sequence is lexicographically less than another if the first $$$k$$$ numbers in them coincide, and the $$$(k + 1)$$$-th number in the first sequence is less than the respective number in the second one.
A list of sequences is lexicographically ordered if each sequence is lexicographically less than the next one in the list.
It is clear that we can uniquely construct a lexicographically ordered list of all $$$n$$$-element $$$1$$$-stable sequences. For example, for $$$n = 3$$$, such list starts as follows: $$$$$$(1, 1, 1),\; (1, 1, 2),\; (1, 2, 1),\; (1, 2, 2),\; (1, 2, 3),\; (2, 1, 1),\; (2, 1, 2),\; \ldots$$$$$$
The lexicographical number of an $$$n$$$-element $$$1$$$-stable sequence is its number in the lexicographically ordered list of all $$$n$$$-element $$$1$$$-stable sequences. The sequences are numbered starting from $$$0$$$. For any $$$n$$$, the lexicographically ordered list of such sequences is obviously infinite. So, for any number, there exists a $$$1$$$-stable sequence with this lexicographical number.
You need to write a program that will find an $$$n$$$-element $$$1$$$-stable sequence by its lexicographical number $$$x$$$.
The first line contains two integers: $$$n$$$ and $$$x$$$ ($$$1 \leq n \leq 40$$$, $$$0 \leq x \leq 10^{18}$$$).
You need to output $$$n$$$ positive integers: the requested sequence.
1 10
11
2 10
4 5
The [REDACTED] company is considering several projects to launch.
Each project can be launched in one of the several possible ways, or not launched at all.
The team of analysts has provided the expected costs and revenue for each possible launch way of each project.
The system is set up so that the costs are spent from a fixed budget that has been approved by the management in advance. At the same time, any revenue received does not increase the budget for starting other projects that have not yet been launched.
The management is only interested in the maximum total revenue. In other words, they are not interested in the total costs, except that they fit within the specified budget.
As a highly qualified specialist, you are asked to find the maximum total revenue.
The first line contains two integers $$$n$$$ and $$$b$$$: the number of projects and the allocated budget ($$$1 \le n \le 20$$$, $$$0 \le b \le 10^9$$$).
Then, $$$n$$$ projects are listed, each on a new line. The description of the $$$i$$$-th project starts with a line containing an integer $$$k_i$$$: the number of possible launch ways for the project ($$$1 \le k_i \le 20$$$). Each of the next $$$k_i$$$ lines contains two integers $$$r_{ij}$$$ and $$$e_{ij}$$$: the revenue and costs, respectively, in the case of launching the $$$i$$$-th project in the $$$j$$$-th way ($$$0 \le r_{ij}, e_{ij} \le 10^9$$$).
The total number of all launch ways for all projects does not exceed $$$20$$$ ($$$\sum k_i \le 20$$$).
Output a single integer $$$r$$$: the maximum total revenue.
2 102100 1080 9110 1
100
2 52200 3100 2210 220 3
210
A colored weighted tree is a tree where each vertex $$$i$$$ has weight $$$w_i$$$ and color $$$c_i$$$. A "good" set of a colored weighted tree is any subset of the tree's vertices that satisfies the following conditions:
- no two vertices in the subset are connected by an edge,
- all vertices in the subset have different colors.
The weight of a "good" set is defined as the sum of the weights of the vertices in this set (an empty set has a weight of $$$0$$$).
Given a colored weighted tree, find the maximum weight of a "good" set in it.
The first line contains two integers, $$$n$$$ ($$$1 \le n \le 1000$$$) and $$$C$$$ ($$$1 \le C \le 10$$$): the number of vertices in the tree and the number of different colors, respectively.
The second and third lines contain $$$n$$$ integers each: $$$w_1, w_2, \ldots, w_n$$$ ($$$1 \le w_i \le 10^{9}$$$) and $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \le c_i \le C$$$): the weights of the vertices and their colors, respectively.
The next $$$n - 1$$$ lines describe the edges of the tree. The $$$j$$$-th of these lines contains two integers $$$u_j$$$ and $$$v_j$$$ ($$$1 \le u_j, v_j \le n$$$, $$$u_j \neq v_j$$$): the numbers of the vertices connected by the $$$j$$$-th edge. It is guaranteed that the given graph is a tree.
Output a single integer: the maximum possible weight of a "good" set in the given tree.
4 41 1 1 11 2 3 41 21 31 4
3
5 35 1 2 3 11 2 2 3 11 21 32 42 5
8
Evgeny doesn't like to work at all, but he really enjoys Da Hong Pao tea, which is known for its relaxing effect. During a tea session with Da Hong Pao, Evgeny wondered how he could maximize his total relaxation.
During the session, he is offered $$$n$$$ cups of different types of his favorite tea, each with its own relaxation coefficient $$$a_i$$$. The tea cups are arranged in a row, without gaps, equidistant from each other. To maintain the aesthetics that Evgeny values very much, he acts as follows: while there are still some cups left on the table, pick either the leftmost or the rightmost remaining cup, and drink all tea from that cup. After that, the server removes the cup from the table.
From the first cup he drinks during the session, Evgeny gets $$$x_1$$$ units of relaxation, where $$$x_1$$$ is the relaxation coefficient for the first cup of tea he drinks. From the next cup, he gets $$$2 x_2$$$ units of relaxation, where $$$x_2$$$ is the relaxation coefficient for the second cup of tea he drinks. And so on: from the $$$i$$$-th cup he drinks, Evgeny gets $$$i x_i$$$ units of relaxation.
Help Evgeny determine the maximum total amount of relaxation he can achieve during the Da Hong Pao session.
The first line contains an integer $$$n$$$ ($$$1 \le n \le 5000$$$).
The next line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 1000$$$): the relaxation coefficients of all the Da Hong Pao cups provided to Evgeny.
Output a single integer: the maximum total relaxation value that Evgeny can achieve during the Da Hong Pao session.
41 2 3 4
30
41 2 1 1
14
In the magical kingdom of Equilibria, an unexpected storm occurred after a powerful spell. As a result, the lands between the Great Library of Equilibria and the trading district were flooded. Your hero, a young mage, must travel from the library to the market to deliver important scrolls with spells. The flooded fields of the kingdom form a grid of size $$$n \times m$$$, and each cell of the grid contains water of a certain depth. The mage can only move right, left, and down on the grid ($$$(\mathit{row}, \mathit{col} + 1)$$$, $$$(\mathit{row}, \mathit{col} - 1)$$$, and $$$(\mathit{row} + 1, \mathit{col})$$$), starting his journey from the upper left corner ($$$(1, 1)$$$, the library) and ending at the lower right corner ($$$(n, m)$$$, the market). Your task is to find such a path that the maximum depth of water along this path is the minimum possible, so that your hero remains as dry as possible.
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n, m \le 500$$$): the dimensions of Equilibria. Each of the next $$$n$$$ lines contains $$$m$$$ integers $$$d_{i, j}$$$ ($$$0 \le d_{i, j} \le 10^9$$$, $$$d_{1, 1} = d_{n, m} = 0$$$), indicating the depth of water in each cell.
Output the maximum depth of water on the path you found.
3 30 1 99 1 99 1 0
1
5 30 1 19 9 21 1 12 9 91 1 0
2
A domino on a grid is a shape consisting of two unit squares with a common side. For an $$$m \times n$$$ rectangle, a domino tiling is a set of dominoes which are completely inside the rectangle such that each square of the rectangle is covered by exactly one of them. Two tilings $$$P$$$ and $$$Q$$$ are considered different if there are dominoes $$$p \in P$$$ and $$$q \in Q$$$ which share exactly one square.
How many ways are there to tile a rectangle of size $$$m \times n$$$ with dominoes? Since the number of ways can be very large, you need to output the answer modulo $$$10^9 + 7$$$.
The first line of input contains two integers $$$m$$$ and $$$n$$$: the height and width of the rectangle, respectively ($$$1 \le m \le 6$$$, $$$1 \le n \le 10^{18}$$$).
Output a single integer: the number of ways to tile the rectangle $$$m \times n$$$ with dominoes modulo $$$10^9 + 7$$$.
3 4
11
3 1
0
Butterball is on a diet, so until autumn, his diet will consist only of broccoli, rice, and chicken breast. Butterball can eat any amount of broccoli, but there are restrictions on rice and chicken breast.
Until autumn, Butterball will have exactly $$$n$$$ trips to the store, and for each trip, he knows in advance the amount of dry rice in grams $$$a_i$$$ and the amount of raw chicken breast in grams $$$b_i$$$ that he is going to buy. It is also known that one meal of Butterball will consist of $$$k$$$ grams of rice and chicken breast combined. But Butterball decided not to mix rice and chicken breast from different trips to the store, so a meal will always have one of the following types:
- $$$x$$$ grams of rice and $$$y$$$ grams of chicken breast which were bought on the same trip to the store, where $$$x + y = k$$$;
- $$$x_1, x_2, \ldots, x_r$$$ grams of rice ($$$x_1 + x_2 + \ldots + x_r = k$$$), where $$$x_i$$$ is a part of all the rice bought in one of the trips to the store;
- $$$y_1, y_2, \ldots, y_r$$$ grams of chicken breast ($$$y_1 + y_2 + \ldots + y_r = k$$$), where $$$y_i$$$ is a part of all the chicken breast bought in one of the trips to the store.
For example, if Butterball has two trips to the store, on the first trip he buys 200 grams of rice and 500 grams of chicken breast, and on the second trip he buys 100 grams of rice and 200 grams of chicken breast, then he will be able to prepare only 2 meals with $$$k = 400$$$. Like this, for instance:
- first meal: 100 grams of rice and 300 grams of chicken breast from the first trip to the store;
- second meal: 200 remaining grams of chicken breast from the first trip to the store and 200 grams of chicken breast from the second trip to the store.
Help Butterball determine the maximum number of meals he can prepare for himself until autumn!
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n, k \leq 500$$$): the number of trips to the store and the total weight of food in grams for one meal, respectively.
In the $$$i$$$-th of the following $$$n$$$ lines, two integers $$$a_i$$$ and $$$b_i$$$ ($$$0 \leq a_i, b_i \leq 10^9$$$) are given: the amount of grams of rice and chicken breast bought on the $$$i$$$-th trip to the store, respectively.
Output a single integer: the maximum number of meals that Butterball can prepare.
2 400200 500100 200
2
1 350100 250
1
2 500100 200300 100
0
The first example is described above.
In the second example: Butterball can prepare exactly one meal using all the products from the first (and only) trip to the store.
In the third example: Butterball will not be able to prepare any meals because, in both trips to the store, the total weight of rice and chicken breast is less than needed for one meal. Additionally, the total weight of rice from two trips is less than needed for one meal. The same statement is true for chicken breast.
Peter and Vasya are playing a game. They have three piles of stones with sizes $$$n_1$$$, $$$n_2$$$, and $$$n_3$$$ respectively. On each turn, it is allowed to take exactly $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_{k - 1}$$$, or $$$a_k$$$ stones from any one pile. Peter and Vasya take turns to take stones, with Peter starting first. The player who cannot make a move loses. Determine the name of the winner.
The first line contains three integers $$$n_1$$$, $$$n_2$$$, $$$n_3$$$ ($$$0 \leq n_1, n_2, n_3 \leq 100$$$).
The second line contains an integer $$$k$$$ ($$$1 \leq k \leq \max(n_1, n_2, n_3)$$$).
The third line contains $$$k$$$ integers in strictly increasing order: $$$a_1, a_2, \ldots, a_k$$$ ($$$1 \leq a_i \leq \max(n_1, n_2, n_3)$$$).
It is guaranteed that there is at least one move, and any $$$a_i$$$ can be taken on the first move.
Output the name of the winner: Peter or Vasya.
1 1 111
Peter
10 10 1022 3
Vasya
You are given a directed graph that is a rooted tree. The edges of the graph are directed from children to parents, and from each vertex, it is possible to reach the root through the edges. Each vertex of the graph contains an integer. It is guaranteed that all these integers are distinct.
Consider all paths from the leaves to the root; here, a leaf is a vertex without children. For each path, calculate the sum of the $$$k$$$ largest numbers occurring in its vertices, or all of them if there are fewer than $$$k$$$ numbers on the path. Find the maximum such sum.
The first line contains two integers $$$n$$$ and $$$k$$$ separated by a space — the number of vertices in the graph and the limit on the number of vertices taken on the path ($$$1 \leq n \leq 300\,000$$$, $$$1 \leq k \leq 300\,000$$$).
The next $$$n$$$ lines define the graph. The $$$i$$$-th of these lines contains two integers $$$p_i$$$ and $$$q_i$$$ separated by a space; here, $$$p_i$$$ is the number of the parent vertex of the $$$i$$$-th vertex, and $$$q_i$$$ is the number written in this vertex ($$$0 \leq q_i \leq 10^9$$$). For the root of the tree, $$$p_i = 0$$$; for all other vertices, $$$1 \leq p_i \leq n$$$. The numbers $$$q_i$$$ are all distinct.
It is guaranteed that the given graph is a rooted tree.
On the first line, output a single integer: the maximum sum of at most $$$k$$$ numbers on some path from a leaf to the root.
5 20 11 21 32 43 5
8
7 30 151 12 213 991 145 206 100
135