Jesse has an integer $$$x$$$. He wants to find an integer $$$y$$$ ($$$0 \leq y \leq 100$$$) such that when you concatenate $$$(x+y)^2$$$ and $$$(x+y)^3$$$, you get a permutation of the digits $$$0\dots9$$$. More specifically, you get a sequence of digits where each digit $$$0...9$$$ occurs exactly once.
Can you help him find the integer?
For example, if $$$x = 27$$$, $$$y = 42$$$ would be a valid answer answer since $$$(27+42)^2 = 4761$$$ and $$$(27+42)^3 = 328509$$$. When you concatenate them, you get $$$4761328509$$$, which is a permutation of the digits $$$0...9$$$.
Note that leading zeroes are discarded before concatentation.
The first line contains a single integer $$$x$$$ ($$$0 \leq x \leq 50$$$)
Print a single integer $$$y$$$ ($$$0 \leq y \leq 100$$$) $$$-$$$ Jesse's desired integer. If there are multiple answers, print any.
27
42
The sample is the example explained in the statement.
Problem Credits: Eric Hsu
For a positive integer $$$x$$$, define the cascading sum of $$$x$$$ as the sum of all of $$$x$$$'s nonempty prefixes.
For example, the cascading sum of $$$2023$$$ is $$$2023+202+20+2=2247$$$.
You are given $$$q$$$ queries, where each query gives you a positive integer $$$n$$$. For each query, output the number of positive integers $$$m$$$ such that $$$m \le n$$$ and $$$m$$$ is not the cascading sum of any number.
The first line consists of an integer $$$q$$$, the number of queries ($$$1 \leq q \leq 10^5$$$). The description of the queries follows.
The first line of each query contains a single integer $$$n$$$ $$$(1 \leq n \leq 10^{18})$$$.
For each query, output the number of positive values which are not cascading sums and are at most $$$n$$$.
5 4 10 220 3000 3500
0 1 21 299 349
For the first query, $$$m = 1, 2, 3, 4$$$ are all cascading sums. For example, $$$3$$$ is the cascading sum of $$$3$$$. Therefore, there are $$$0$$$ values.
For the second query, $$$10$$$ is the only value which is not a cascading sum, so there is $$$1$$$ value.
Problem Credits: Anonymous Red Panda
Daniel has $$$n$$$ trees in his backyard, each numbered from $$$1$$$ to $$$n$$$, and he is currently in the tree numbered $$$1$$$. These trees are very special, and can grow cereal on them! When Daniel is hungry, he travels from tree to tree and eats cereal from the trees that he reaches. Furthermore, each tree has a different type of cereal on it, and he would like to eat as many different varieties of cereal as possible.
Unfortunately, traveling from tree to tree takes a lot of energy. Specifically, traveling from tree $$$a$$$ to tree $$$b$$$ takes $$$a | b$$$ energy, where $$$|$$$ denotes the bitwise OR operator. However, once he has traveled on a path from $$$a$$$ to $$$b$$$, it no longer takes energy for it to travel on that path.
Recently, the cereal trees have been taking a long time to regrow their cereal, meaning every day, there is exactly one cereal tree that has no cereal on it. Daniel is trying to plan his meals for the next $$$d$$$ days. On a day $$$i$$$, he knows that there will be no cereal on tree $$$t_i$$$, and therefore will decide to skip visiting that tree that day. It is guaranteed that tree $$$1$$$ is never skipped. Note that each day is independent of other days - an empty tree on day $$$1$$$ will not stay empty on day $$$2$$$, and paths traveled on day $$$1$$$ reset on day $$$2$$$.
Daniel is very lazy, so can you help him figure out the smallest amount of energy he can spend to reach all cereal-bearing trees for each of the next $$$d$$$ days?
The first line of input contains $$$2$$$ integers $$$n$$$ ($$$2\le n \le 10^5$$$) and $$$d$$$ ($$$1\le d \le 10^5$$$). Then $$$d$$$ lines follow.
Each of these $$$d$$$ lines contains one integer $$$t_i$$$ ($$$2\le t_i \le n$$$).
For each value of $$$t_i$$$ from the input, output onto separate lines the minimum amount of energy Daniel can spend to reach all cereal-bearing trees each day.
5 2 3 4
13 11
When tree $$$3$$$ has no cereal, Daniel can use paths $$$1-2$$$, $$$1-4$$$, and $$$5-4$$$, leading to a total energy of $$$3 + 5 + 5 = 13$$$.
When tree $$$4$$$ has no cereal, Daniel can use paths $$$1-2$$$, $$$2-3$$$, and $$$1-5$$$, leading to a total energy of $$$3 + 3 + 5 = 11$$$.
Problem Credits: Daniel Kim
Sengoku Nadeko has been given an array $$$a$$$ of $$$n$$$ values. Please help her find the minimum number of element modifications needed to make to $$$a$$$ such that it is possible to construct an array $$$b$$$ of $$$n+1$$$ values that satisfies $$$a_i = max(b_i, b_{i+1})$$$ for all $$$i$$$ from $$$0$$$ to $$$n-1$$$.
Sengoku Nadeko actually has $$$t$$$ ($$$1 \leq t \leq 10^4$$$) independent test cases to solve.
The first line of each test case will contain a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$). The next line will contain n integers where the $$$i$$$-th integer is $$$a_i$$$ ($$$0 \le a_i \le 10^9$$$).
It is guaranteed that the sum of $$$n$$$ over all test cases won't exceed $$$2\cdot10^5$$$.
For each test case, output the minimum number of elements that need to be modified in $$$a$$$ such that there exists an array $$$b$$$ that satisfies the conditions in the problem statement.
142 4 6 3
1
In the example, modifying $$$a_4$$$ from $$$3$$$ to be $$$8$$$ makes $$$a=[2, 4, 6, 8]$$$, so a possible $$$b$$$ could be $$$b=[2, 1, 4, 6, 8]$$$.
Problem Credits: Eric Yachbes
Michael has gotten the internship of a lifetime! He will be working (unpaid, obviously) at Thomas' zoo in the red panda enclosure.
The enclosure can be described as a tree of $$$n$$$ nodes, rooted at node $$$1$$$. Each node contains a house which has exactly one red panda in it. Every afternoon, Michael will be in charge of organized nap-time for the pandas, which involves all $$$n$$$ red pandas reaching the root of the tree to take a nap. It works as follows:
- In one second, Michael may let any number of pandas out of their homes. Then, all pandas that have been let out of their home, other than those at the root, climb up one node in the tree towards the root. The process repeats until Michael has placed all $$$n$$$ pandas.
- If two red pandas ever occupy the same node other than the root, they will start a fight, so this cannot happen.
Note that the panda that lives in node $$$1$$$ must still be let out of its house to join the other pandas (and hug them).
Michael wants to accomplish this task as fast as possible, so he can eat his lunchtime Raisin Brain cereal. What is the minimum time (in seconds) that it will take for Michael to finish placing all pandas, and what is a possible way he can achieve it? Note that Michael will be finished once he places the last panda, not when all pandas reach the root.
The problem has $$$t$$$ ($$$1 \leq t \leq 10^4$$$) independent test cases.
For each test case, the first line will contain $$$n$$$ ($$$2 \leq n \leq 2\cdot10^5$$$). The next $$$n - 1$$$ lines contain the edges of the tree. Each line will have two integers, $$$u$$$ and $$$v$$$, meaning there is an edge between nodes $$$u$$$ and $$$v$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases will not exceed $$$2 \cdot 10^5$$$.
For each test case, print the minimum number of seconds it will take Michael to place the pandas.
Then, in a new line, print $$$i$$$ integers, where the $$$i$$$-th integer is the second during which Michael should let out the panda in node $$$i$$$. If there are multiple possible solutions, print any.
241 23 24 151 21 33 45 3
1 1 1 1 1 2 1 1 1 1 2
For the first test case, Michael can release all pandas at once.
For the second test case, Michael can't release all pandas at once since the pandas at nodes $$$4$$$ and $$$5$$$ will start a fight.
Problem Credits: Allen Wu
Alice has a candy machine, which can be represented as a tree of size $$$n$$$. The nodes are labelled $$$1, 2, \dots, n$$$, and rooted at node $$$1$$$. Node $$$u$$$ initially contains the candy labelled $$$u$$$. If $$$u$$$ is a non-leaf node (a node with one or more children), then it starts with exactly one candy of type $$$u$$$; otherwise, it starts with an infinite number of candies.
She can spend $$$1$$$ dollar to get the candy at the root, making the root empty. Afterwards, a candy from one of its children is dropped into the node. The candy that drops is chosen with probability according to the weight of the edge. This creates a new empty node, and the process continues until there are no more empty nodes.
More formally, if node $$$u$$$ is empty and has children $$$v_1, v_2, \ldots, v_k$$$ with associated costs $$$w_1, w_2, \ldots, w_k$$$, then the probability of getting a candy from node $$$v_i$$$ is $$$\frac{w_i}{\sum w}$$$.
For each $$$i$$$ from $$$1$$$ to $$$n$$$, calculate the expected amount of money she has to spend in order to get a candy of type $$$i$$$.
The first line contains a single integer $$$t$$$ ($$$1\leq t\leq 10^4$$$), the number of test cases.
Then follow the descriptions of the test cases.
The first line of each test case contains a single integer $$$n$$$ ($$$1\leq n\leq 2\cdot 10^5$$$) — the size of the candy machine.
The next $$$n-1$$$ lines contain three integers $$$u, v, w$$$ ($$$1\leq u,v\leq n$$$, $$$1\leq w\leq 10^9$$$) — the endpoints and weight of each edge. It is guaranteed that the edges form a tree.
The sum of $$$n$$$ over all test cases will not exceed $$$2\cdot 10^5$$$.
For each test case, output one line with $$$n$$$ integers, where the $$$i$$$-th integer is the expected amount of money she needs to spend to get a candy of type $$$i$$$. Output the answer modulo $$$998\,244\,353$$$.
Formally, let $$$M = 998\,244\,353$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \le x \lt M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.
321 2 551 2 101 3 92 4 72 5 6121 2 51 3 42 4 91 5 135 6 123 7 93 8 67 9 18 10 23 11 172 12 6
1 2 1 698771050 443664160 570425351 715408460 1 199648876 499122183 532397001 153576057 307152113 720954281 831870330 942786379 166374124 146800657 199648887
In the first test case, candy $$$1$$$ will fall out in $$$1$$$ drop, and in the next candy $$$2$$$ is guaranteed to fall out.
In the second test case, candy $$$1$$$ will once again fall out in $$$1$$$ drop. The expected drops is $$$\frac{29}{10}$$$ for candy $$$2$$$ and $$$\frac{28}{9}$$$ for candy $$$3$$$.
Batrick has gifted Envy a field of $$$n$$$ pumpkins for Halloween! The pumpkins are arranged in a row numbered $$$1 \dots n$$$ from left to right. Pumpkin $$$i$$$ has tastiness $$$a_i$$$ and quality $$$b_i$$$, and Envy wishes to maximize the sum of the tastiness of the pumpkins he eats. Envy will perform $$$n$$$ operations, and on the $$$i$$$-th operation, he can do one of the following:
$$$1$$$: Carve a jack-o-lantern into the $$$i$$$-th pumpkin, illuminating all pumpkins at most $$$b_i$$$ spaces away.
$$$2$$$: Eat the $$$i$$$-th pumpkin only if it is lit up by a jack-o'-lantern, gaining tastiness $$$a_i$$$. This destroys the pumpkin.
$$$3$$$: Swap the $$$i$$$-th pumpkin with the $$$i - 1$$$-th pumpkin, if it exists. Note that the pumpkins retain their original properties after the swap, so their $$$a$$$ and $$$b$$$ values will be swapped, as well as the status of whether they have been carved or not. As such, the pumpkins that are illuminated may change as a result of a swap.
What is the maximum sum of $$$a_i$$$ over all pumpkins Envy consumes?
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 1000$$$). The description of the test cases follows.
The first line of each testcase contains an integer, $$$n$$$ ($$$1 \leq n \leq 5000$$$).
The second line contains $$$n$$$ integers, $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$).
The line after contains $$$n$$$ more integers, $$$b_1, b_2, \dots, b_n$$$ ($$$0 \leq b_i \lt n$$$).
It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$5000$$$.
For each test case, output the maximum tastiness sum Envy can achieve.
233 1 22 2 251 1 5 5 53 2 0 1 0
3 15
In the first test case Envy can carve pumpkin $$$1$$$ and eat pumpkins $$$2$$$ and $$$3$$$.
In the second test case Envy should carve pumpkin $$$1$$$, swap pumpkins $$$1$$$ and $$$2$$$, then eat the remaining pumpkins.
Problem Credits: Patrick Deng
Ryan loves to eat Honey Nut Cereal, but there is a shortage of honey. To get honey, you obviously need to pollinate the flowers.
A flower of size $$$n$$$ resides on a square grid of length $$$2n + 1$$$. The rows are numbered $$$1\dots2n+1$$$ from top to bottom, and the columns are numbered $$$1\dots2n+1$$$ from left to right. The center of the flower is at the cell in row $$$n + 1$$$ and column $$$n + 1$$$. Any cell with a Manhattan distance $$$x$$$ from the center such that $$$1 \leq x \leq n$$$ contains a petal. Note that the center doesn't contain a petal. Below is an example of such a flower.
a flower of size $$$3$$$ You want to cover only the petals of the flower with L-shaped pieces such as the one below. Each petal should be covered by exactly one L-shaped piece. An L-shaped piece is a $$$2\times2$$$ square with one cell removed. You may rotate it however you choose.
L-shaped piece Tell Ryan if it is possible to pollinate the flower, and if it is, give him a valid configuration of L-shaped pieces that pollinates the flower.
The first line of input contains $$$t$$$, the number of test cases ($$$1 \leq t \leq 500$$$).
Each test case will be one line of input, containing $$$n$$$ ($$$1 \leq n \leq 1000$$$), the size of the flower. It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$1000$$$.
If it is possible to pollinate the flower, print an integer $$$l$$$, denoting the number of L-shapes you will use. If it is impossible, print -1.
If it is possible, you must print another $$$l$$$ lines, each describing an L-shaped piece you use. Each line should contain six integers, $$$x_1$$$ $$$y_1$$$ $$$x_2$$$ $$$y_2$$$ $$$x_3$$$ $$$y_3$$$, where ($$$x_1$$$, $$$y_1$$$), ($$$x_2$$$, $$$y_2$$$), and ($$$x_3$$$, $$$y_3$$$) are the cells taken up by the L-shaped piece if ($$$x$$$, $$$y$$$) refers to the cell at row $$$x$$$ and column $$$y$$$.
12
4 3 1 3 2 4 2 1 3 2 2 2 3 2 4 3 4 3 5 4 3 4 4 5 3
Here is an example of a pollinated flower of size $$$2$$$.
Problem Credits: Ariel Shehter
Tina wonders how strong the friendships of the CerealCodes team are. She has a tree of $$$n$$$ ($$$n$$$ is even) nodes, where each node represents one CerealCodes team member. A tree is an undirected connected graph with $$$n - 1$$$ edges.
She also knows of $$$\frac{n}{2}$$$ pairs of friends, where pair $$$i$$$ consists of nodes $$$a_i$$$ and $$$b_i$$$. Each node on the tree belongs to exactly one of these pairs.
For each edge on the tree, Tina wants to know, if that edge was removed from the tree, what would be the minimum $$$i$$$ (if it exists) such that $$$a_i$$$ and $$$b_i$$$ are disconnected?
Tina needs to solve $$$t$$$ ($$$1 \leq t \leq 10^4$$$) separate test cases.
Each test case begins with a line containing an even integer $$$n$$$ ($$$2 \leq n \leq 5\cdot10^5$$$), the number of nodes in the tree.
$$$n-1$$$ lines follow, where the $$$i$$$th of these lines is the $$$i$$$th edge of the tree, $$$u_i$$$ and $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$). This means that there is an edge between nodes $$$u_i$$$ and $$$v_i$$$. These edges will form a tree.
Lastly, there are $$$\frac{n}{2}$$$ more lines, which are the pairs of friends. The $$$i$$$th of these lines contains two integers, $$$a_i$$$ and $$$b_i$$$. Each integer from $$$1 \dots n$$$ belongs to exactly one pair.
It is guaranteed that the sum of $$$n$$$ over all test cases won't exceed $$$5\cdot10^5$$$.
For each test case, print a line containing $$$n-1$$$ integers, where the $$$i$$$th integer is the minimum $$$i$$$ such that $$$a_i$$$ and $$$b_i$$$ are disconnected if the $$$i$$$th edge was removed. If no such pair exists, print $$$-1$$$.
261 21 34 25 22 61 42 53 641 23 24 32 31 4
1 3 1 2 3 2 1 2
The tree in the first test case Problem Credits: Timothy Gao
It's him and I, Aquemini.
You, the aquamist, are initially given $$$n$$$ stacks that can each hold up to $$$m$$$ blocks. Initially, each stack $$$i$$$ except the $$$n$$$-th stack is full with $$$m$$$ blocks that are all labeled $$$i$$$ (blocks with the same label are indistinguishable from each other). The $$$n$$$-th stack is initially empty, having no blocks on it.
In a single move, you can do the following:
- Take a block off the top of a stack and place it on top of another stack, without causing a stack to have more than $$$m$$$ blocks on it.
You are also given the final arrangement of labeled blocks in each stack, ordered from the bottom to the top of the stack, and your goal is to determine a sequence of moves to get from the initial arrangement to this final arrangement.
The first line contains two integers, $$$n$$$ and $$$m$$$ $$$(3 \le n \le 50, 1 \le m \le 100)$$$.
Next, $$$n$$$ lines follow. On the $$$i$$$-th of these lines, there is first a single integer $$$s_i$$$ and then there are $$$s_i$$$ integers that follow $$$(0 \le s_i \le m)$$$. The $$$j$$$-th of these integers on the $$$i$$$-th line, $$$a_{i,j}$$$, denotes that the $$$j$$$-th-from-the-bottom block on the $$$i$$$-th stack has the label $$$a_{i,j}$$$ in the final arrangement.
It is guaranteed that the number of blocks with a label $$$i$$$ is the same between the initial arrangement and final arrangement for all values of $$$i$$$.
First print a single number $$$k$$$, the number of moves in your sequence $$$(0 \le k \lt 2 \cdot 10^6)$$$. You do NOT have to minimize the number of moves in the sequence. It is provable that there always exists a solution in less than $$$2 \cdot 10^6$$$ moves given the specified input conditions.
Next, print $$$k$$$ lines. On the $$$i$$$-th line, print two numbers $$$x_i$$$ and $$$y_i$$$, denoting that on the $$$i$$$-th move, you will take a block from the top of stack $$$x_i$$$ and move it to the top of stack $$$y_i$$$. It must be the case that there exists at least one block on stack $$$x_i$$$ and less than $$$m$$$ blocks on stack $$$y_i$$$ before this move is made.
4 3 3 2 1 1 3 2 3 2 2 3 3 1 1
9 1 4 1 4 1 4 2 1 2 1 3 2 1 2 4 1 4 1
The following diagram shows the final arrangement of all the stacks from left to right.
Problem Credits: Eric Yachbes
Roses really smell like poopoo.
One afternoon, "Andre 3000" and "Big Boi" decided to go outside and pick roses. There are $$$n$$$ roses indexed $$$0$$$ through $$$n-1$$$. Both Andre 3000 and Big Boi decide that certain roses will smell good if picked after others. Their actions can be represented by two arrays given in the input, $$$a$$$ and $$$b$$$.
Specifically, after picking rose $$$i$$$, Andre 3000 will look at $$$a_i$$$. If $$$a_i$$$ is $$$-1$$$, he will stop picking roses. Otherwise, he will pick rose $$$a_i$$$ $$$(a_i \gt i)$$$. Likewise, after picking rose $$$i$$$, Big Boi will stop picking roses if $$$b_i = -1$$$, otherwise he will pick rose $$$b_i$$$ $$$(b_i \gt i)$$$.
Andre 3000 and Big Boi will both start by initially picking the same rose and want to know if it is possible that they will ever pick the same rose again. If this is the case for some initial rose picked by both Andre 3000 and Big Boi, print that initial rose's index. Otherwise, print $$$-1$$$. If there are multiple solutions, you can print any.
The first line contains a single integer $$$n$$$ $$$(1 \le n \le 10^6)$$$. The next line contains $$$n$$$ integers where the $$$i$$$-th integer is $$$a_i$$$ $$$(a_i = -1$$$ OR $$$i \lt a_i \lt n)$$$. The next line contains $$$N$$$ integers where the $$$i$$$-th integer is $$$b_i$$$ $$$(b_i = -1$$$ OR $$$i \lt b_i \lt n)$$$.
Print the index of any rose such that if both Andre 3000 and Big Boi start by picking that rose, there exists another different rose such that they will both eventually pick that other rose too. If no such initial rose exists, print $$$-1$$$.
5 1 3 -1 4 -1 2 4 3 -1 -1
0
4 1 2 -1 -1 3 3 -1 -1
-1
In the first example, let's say Andre 3000 and Big Boi both start by picking rose $$$0$$$. After picking rose $$$0$$$, Andre 3000 will pick rose $$$1$$$ then $$$3$$$ then $$$4$$$ and then will stop picking roses. After picking rose $$$0$$$, Big Boi will pick rose $$$2$$$ then $$$3$$$ then stop picking roses. Since, both Andre 3000 and Big Boi pick rose $$$3$$$ some point after both starting by picking rose $$$0$$$, rose $$$0$$$ is a valid starting rose.
In the second example, it can be seen that there is no rose such that if both Andre 3000 and Big Boi start by picking that rose, there exists another different rose such that they will both eventually pick that other rose too.
Problem Credits: Eric Yachbes