Those who are not familiar with movies often confuse the Star Wars and Star Trek sagas, which is offensive because Star Wars is widely superior. Esomer is tired of these offenses, so he wants to create a program that, given a character, responds whether it belongs to the Star Wars saga or the Star Trek saga. Unfortunately, he is not very good at programming, so he needs your help.
The input will consist of a single string $$$s$$$, which will be one of the following three options (without quotes): "Yoda", "Spock", or "Frodo".
In the case that $$$s$$$ is "Yoda", you should print: "Pertenece a Star Wars.".
In the case that $$$s$$$ is "Spock", you should print: "Pertenece a Star Trek.".
In the case that $$$s$$$ is "Frodo", you should print: "No pertenece ni a Star Wars ni a Star Trek.".
All of them without quotes.
Spock
Pertenece a Star Trek.
Yoda
Pertenece a Star Wars.
Frodo
No pertenece ni a Star Wars ni a Star Trek.
—
Problem idea: Esomer
Problem preparation: Esomer
Occurrences: Novice 1, Advanced 1
José has just learned the basic arithmetic operations (addition, subtraction, multiplication, and division). Since he is quite good at it, his friend Óscar, who is playing a new video game he bought, asks José for help with his homework. The teacher gives him two positive integers $$$a$$$ and $$$b$$$ and asks him to apply one of the $$$4$$$ mentioned operations to obtain the highest possible result. In other words, he is asked to find the maximum value of $$$a?b$$$, where $$$?$$$ can be addition, subtraction, multiplication, or division.
You are given two integers $$$a$$$ and $$$b$$$. $$$(1 \leq a, b \leq 100)$$$.
You have to print a number, the maximum value after applying an operation to $$$a$$$ and $$$b$$$.
6 3
18
8 1
9
—
Problem idea: Hectorungo18
Problem preparation: Hectorungo18
Ocurrences: Novice 2
Rafa and Jan are like joints, how good they are but how bad they are.
There is a bank with a stack of $$$n$$$ checks, each having a specific face value in dollars.
The bank has a unique policy: they allow their customers to redeem a limited number of checks per day.
Your task is to help the bank's customers determine the maximum total value they can redeem in a single day.
The first line contains two integers $$$n$$$ $$$(1 \leq n \leq 10^{4})$$$ and $$$k$$$ $$$(1 \leq k \leq n)$$$, representing the number of checks and the maximum number of checks the bank allows to be redeemed in a day, respectively.
The second line contains $$$n$$$ integers $$$c_{1}, c_{2}, ..., c_{n}$$$ $$$(1 \leq c_{i} \leq 10^4)$$$, representing the face values of the $$$n$$$ checks.
Output a single integer, the maximum total value that can be redeemed in a single day by choosing the optimal combination of $$$k$$$ checks.
3 211 5 10
21
The optimal strategy is to take the first and the third checks to get a sum of $$$21$$$ dollars.
—
Problem idea: danx
Problem preparation: danx
Ocurrences: Novice 3
Javier, the natty bodybuilder who bench presses $$$1073741824$$$ kg, is training bench press.
In order to reach the desired weight for the lift, Javier will have to use the $$$duplicator$$$. If he puts $$$x$$$ discs into the $$$duplicator$$$, after $$$1$$$ minute he will have twice as many. To use the machine again, he has to remove all the discs and put in the desired number again. Since he's loaded up on creatine and pre-workout, this action takes no time at all. Initially, he only has one disc that his friend Bumstead gave him. It's also important to note that the bar he uses for the lift is magical and weighs nothing.
Javier needs $$$n$$$ discs to do his exercise. You need to help him determine the minimum number of minutes it will take for him to reach the desired weight. If the minimum number of minutes is $$$m$$$, you also need to tell him how many discs he should put into the $$$duplicator$$$ in the $$$i$$$-th minute, in order to reach the weight in the minimum possible time.
If there are multiple ways to put discs into the $$$duplicator$$$ to reach the weight $$$n$$$ in $$$m$$$ minutes, you should print the lexicographically smallest sequence.
A sequence of numbers $$$a$$$ is lexicographically smaller than another sequence $$$b$$$ of the same length, if there exists an index $$$i$$$ such that $$$a_i \lt b_i$$$ and for all $$$j$$$ such that $$$1 \leq j \lt i$$$, it holds that $$$a_{j} = b_{j}$$$.
The only line contains an integer $$$n$$$ $$$(2 \leq n \leq 10^9)$$$, the weight that Javier wants to lift.
The first line of the output should contain an integer $$$m$$$, the minimum number of minutes Javier needs to perform his set with the desired weight.
The second line should contain $$$m$$$ integers, $$$x_1, x_2, \ldots, x_m$$$, where $$$x_i$$$ is the number of discs that Javier puts into the $$$duplicator$$$ in the $$$i$$$-th time. Remember that if there are multiple possible ways to reach the weight in $$$m$$$ minutes, you should print the sequence that is lexicographically smallest.
1024
10 1 2 4 8 16 32 64 128 256 512
33
6 1 1 2 4 8 16
—
Problem idea: Hectorungo18
Problem preparation: Hectorungo18
Ocurrences: Novice 4
A palindrome is a string of characters that reads the same from left to right as it does from right to left. Javier, being the absent-minded boy that he is, has been thinking that "palindromio" is the correct spelling for almost a year now! To do him a favor, let's create a new definition before he realizes that he's mistaken.
A "palindromio" is a string of digits from $$$0$$$ to $$$9$$$ that is exactly one position away from being a palindrome. $$$101$$$ and $$$22$$$ are palindromes, while $$$100$$$ and $$$20$$$ are "palindromios". Not satisfied with this, Javier now wants to know how many "palindromios" can be created using exactly $$$n$$$ digits from $$$0$$$ to $$$9$$$. Help him satisfy his curiosity.
The first line contains an integer $$$t$$$, ($$$1 \le t \le 100$$$), the number of questions Javier will ask you. Each of his questions will consist of a single integer $$$n$$$, the length of the "palindromio", ($$$1 \le n \le 50000$$$).
For each question, you should print the number of "palindromios" of length $$$n$$$. Since this number can be very very large, Javier will be satisfied if you print it $$$\mod {10^9 + 7}$$$. This operation is performed using $$$\%$$$ in C++ and Python. Note that $$$(a + b) \mod P$$$ is the same as $$$(a \mod P + b \mod P) \mod P$$$, and a similar thing applies with the product, so you can apply the modulo operation after every operation you make to avoid overflow. If you have questions about modulos, we will answer them in the clarifications.
4 2 3 2023 13
90 900 616533557 540000000
—
Problem idea: Javi
Problem preparation: Javi
Ocurrences: Novice 5
Harry is participating in the Hogwarts Informatics Olympiad. There is $$$1$$$ problem with many subtasks. However, Voldemort has cast a spell on the judges, making them believe that Harry has copied in some of his submissions. To find out how Harry is doing in the competition considering Voldemort's spell, Harry will ask you $$$q$$$ queries.
The queries can be of $$$3$$$ types:
- $$$1$$$ $$$k$$$: Harry gives you information about a submission. He provides $$$k$$$ numbers $$$x_1, x_2, \ldots, x_k$$$, where each $$$x_i$$$ represents the index of a subtask that Harry has solved correctly in this submission. All the $$$x_i$$$ are distinct. Note that Harry may solve a subtask correctly that he had already solved correctly in a previous submission.
- $$$2$$$ $$$i$$$: Harry tells you that the judges have invalidated the submission he specified in query $$$i$$$. It is guaranteed that query $$$i$$$ is of type $$$1$$$ and that Harry had already made that query. It is also guaranteed that the submission had not been invalidated yet.
- $$$3$$$: You must print the number of submissions that are currently increasing Harry's score (considering only the previous queries). A submission increases Harry's score if, for any of the subtasks he solves correctly, it is the first submission that Harry has specified to you and has not been invalidated with that correct subtask yet.
The first line contains an integer $$$t$$$, the number of cases to answer. ($$$1 \le t \le 100$$$).
The first line of each case contains an integer $$$q$$$, the number of queries that Harry asks you. $$$(2 \le q \le 2 \cdot 10^5)$$$.
The following $$$q$$$ lines contain the queries. Line $$$j$$$ contains an integer $$$type_j$$$, indicating the type of the query ($$$1 \le type_j \le 3$$$). If $$$type_j = 1$$$, it will be followed by an integer $$$k_j$$$ and $$$k_j$$$ integers $$$x_{j_1}, x_{j_2}, \ldots, x_{j_k}$$$, the subtasks that Harry solves in that submission, ($$$1 \le x_{j_i} \le 2 \cdot 10^5$$$). If $$$type_j = 2$$$, it will be followed by an integer $$$i_j$$$, the index of the query specifying the invalidated submission.
It is guaranteed that both the sum of $$$q$$$ and the sum of $$$\sum k_j$$$ over all cases are at most $$$2 \cdot 10^5$$$.
For each case, you must print the number of submissions that are increasing Harry's score for each query of type $$$3$$$ that you receive.
2101 3 3 2 531 1 31 1 22 132 332 43111 2 2 31 1 21 1 31 1 532 131 2 2 32 22 33
1 2 1 0 2 3 2
—
Problem idea: Esomer
Problem preparation: Esomer, Hectorungo18
Ocurrences: Novice 6
Litusiano has, yet again, found another 8-pages-long statement. Disappointed with the problemsetters who create such long statements, he has created a problem with a very short statement. Now he has gifted it to you so that you can enjoy a short statement, for once. Unfortunately, Esomer is very evil and he has intercepted Litusiano's gift, adding this whole useless paragraph to annoy Litusiano.
You are given an array $$$a$$$ of length $$$30$$$ and you need to construct a new array $$$b$$$ of minimum length such that:
- There are at least $$$a_i$$$ elements with bit $$$i$$$ set in their binary representation, for $$$0 \le i \lt 30$$$.
- The sum of all the elements is $$$s$$$.
- The bitwise XOR$$$^\dagger$$$ of all the elements is exactly $$$x$$$.
If such an array doesn't exist, output $$$-1$$$ instead.
$$$^\dagger$$$If you don't know what bitwise XOR is, remember that you can use the internet!.
The first line of the input contains a single integer $$$t$$$, the number of test cases. ($$$1 \le t \le 10^4$$$).
On the first line of each test case there are two integers, $$$s$$$ and $$$x$$$, the required sum of all the elements in $$$b$$$ and the required XOR of all the elements in $$$b$$$, respectively. ($$$0 \le s \le 10^{18}$$$; $$$0 \le x \lt 2^{30}$$$).
Then comes a line with $$$30$$$ integers, $$$a_1, a_2, \ldots, a_{30}$$$, each $$$a_i$$$ denotes the minimum number all elements in $$$b$$$ that must have the $$$i$$$-th bit set on their binary representation. ($$$0 \le a_i \le 10^9$$$).
For each test case, if there doesn't exist any array that satisfies the conditions, print $$$-1$$$. Otherwise, print the minimum length of such an array.
29 51 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 09 61 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 -1
39 11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 02147483648 11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0104 105 2 3 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 -1 6
—
Problem idea: Esomer
Problem preparation: Esomer
Ocurrences: Novice 7, Advanced 2
Dani is one of the best competitive programmers in the world, boyfriend of the jambilla, best friend of Innokentiy and bodybuilder.
One day in Menorca, he left some cookies at his bed and a lot of ants spawned there.
Hugo and Luis said him to trow the bed through the window and Dani did it, but Ilya and the funator were be very angry with them.
Now Dani needs help with the following problem:
There are $$$n$$$ type of ants, and $$$a_{i}$$$ ants of the $$$i$$$-th type, you have to find the smallest number of moves to throw at least $$$p$$$ ants through the window.
Note that int each move Dani can throw at most $$$m$$$ ants and $$$k$$$ ants of the same type.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ $$$(1 \leq t \leq 10^{4})$$$. The description of the test cases follows.
The first line consists in three integers $$$n$$$, $$$m$$$, $$$k$$$ $$$(1 \leq n \leq 10^{6} ; 1 \leq m, k \leq 10^{18})$$$ — the number of types of ants, the maximum number of ants that can be thrown on a move and the maximum number of ants of the same type that can be thrown on a move, respectively.
Then follows $$$n$$$ integers $$$a_{1}, a_{2}, ..., a_{n}$$$ $$$(1 \leq a_{i} \leq 10^{12})$$$ — the number of ants of each type.
The last line consist in an integer $$$p$$$ $$$(1 \leq p \leq \sum_{i = 1}^{n} a_{i})$$$ — the minimum number of ants that have to be thrown.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^{6}$$$.
For each testcase, output a single integer — the smallest number of moves.
4 4 3 2 3 7 2 1 13 3 2 2 2 2 3 6 2 3 2 10 1 10 1 1 1 1 1
5 3 5 1
The answer for the first testcase could be $$$1$$$-st move: $$$(3, 2, 2)$$$, $$$2$$$-nd move: $$$(1, 2, 2)$$$, $$$3$$$-rd move: $$$(1, 2, 1)$$$, $$$4$$$-th move: $$$(2, 3, 4)$$$, $$$5$$$-th move: $$$(2)$$$.
It can be proven that at least $$$5$$$ moves are needed.
The answer for the second testcase could be $$$1$$$-st move: $$$(1, 1)$$$, $$$2$$$-nd move: $$$(2, 3)$$$, $$$3$$$-rd move: $$$(3, 3)$$$.
It can be proven that at least $$$3$$$ moves are needed.
—
Problem idea: danx
Problem preparation: danx
Ocurrences: Novice 8, Advanced 4
The bank Monopoly has recently been very worried by the possibility of a robbery, as they don't want to lose their fake bills. To reinforce their security, they have implemented a system of security cameras in front of their vault. Now they are worried that it might have flaws, so they have asked for your help.
The room where the vault is located can be represented as an $$$n \times n$$$ grid, where the cell $$$(1, 1)$$$ is the entrance, and the vault is in the cell $$$(n, n)$$$. There are $$$m$$$ cameras in the room, each of them occupying exactly one cell. The cameras can point in $$$4$$$ different directions: up, down, left and right. Each camera initially points in one direction, which may be different between cameras. When a camera points in one direction, it covers all the cells in that direction, including the cell in which it is located.
More formally, let the camera be in the cell $$$(r, c)$$$, where $$$r$$$ represents the row from the top and $$$c$$$ the column from the left, then:
- If the camera points up, for all $$$1 \le i \le r$$$, the camera covers the cell $$$(i, c)$$$.
- If the camera points down, for all $$$r \le i \le n$$$, the camera covers the cell $$$(i, c)$$$.
- If the camera points left, for all $$$1 \le j \le c$$$, the camera covers the cell $$$(r, j)$$$.
- If the camera points right, for all $$$c \le j \le n$$$, the camera covers the cell $$$(r, j)$$$.
If a robber is at a cell covered by a camera, he will be caught.
Additionally, as Monopoly's owners are very paranoic, each second the cameras will rotate $$$90^\circ$$$ anticlockwise (i.e. if a camera points down, it will point to the right; if it points to the right, it will point up; and so on). The robbers that try to break into the vault will have to start at cell $$$(1, 1)$$$ and reach the cell $$$(n, n)$$$ without being seen by the cameras. Each second, robbers can do one of two things:
- Stay at the cell where they are.
- Move to an adjacent cell (i.e. a cell which shares a side with the cell they are in).
Note that the cameras and the robbers move simultaneously, so a robber can move to a cell which is currently covered by a camera as long as it is uncovered on the next second. See the samples section for an example of this.
Your task is to determine if a robber can reach the vault.
The first line contains a single integer $$$t$$$, denoting the number of test cases. ($$$1 \le t \le 100$$$).
The first line of each test case contains two integers $$$n$$$ and $$$m$$$, denoting the size of the grid and the number of cameras, respectively. ($$$1 \le n \le 1000$$$; $$$0 \le m \le \max(0, n^2 - 2)$$$).
Then follow $$$m$$$ lines, each of them with two integers $$$r$$$ and $$$c$$$, representing the row and column of the camera, and a character $$$d$$$ which will be one of 'U', 'D', 'L', 'R', representing the initial direction of the camera. ($$$1 \le r, c \le n$$$).
It is guaranteed that no two cameras share the same cell, that no cameras initially cover the cell $$$(1, 1)$$$, and that there isn't a camera at the cell $$$(n, n)$$$.
Additionally, it is guaranteed that the sum of $$$n$$$ over all test cases is at most $$$1000$$$.
For each test, you should output "YES" if a robber can reach the vault or "NO" if he can't.
33 12 2 U3 32 2 U3 2 R1 3 U3 21 3 U2 3 U
YES NO NO
—
Problem idea: Esomer
Problem preparation: Esomer
Ocurrences: Novice 9
The impacts of the creation of "palindromio" by Javier and his friends have reached Esomer (who is capable of measuring when the forces of order become unbalanced in the universe).
Esomer is able to sense that the Force has become unbalanced in an integer $$$x$$$. Being the busy sage that he is, he doesn't have time to restore it and will need to make use of his $$$n$$$ students to restore the Force. Each student has a power of $$$a_i$$$, and choosing them will reduce the difference of $$$x$$$ to $$$x - a_i$$$. Every day that passes, all his students increase their power by $$$1$$$.
Help him remedy this perturbation as soon as possible, that is, print the minimum number of days in which the difference $$$x$$$ can be reduced to exactly $$$0$$$ using his students.
Once Esomer has used one of his students, due to their fatigue, he will not be able to use them again.
The first line contains an integer $$$t$$$, ($$$1 \le t \le 10$$$), the number of cases to solve.
Each of the cases will consist of two integers $$$n$$$, the number of students he has ($$$1 \le n \le 200$$$), and $$$x$$$, the imbalance that has occurred in the force ($$$1 \le x \le 200$$$).
$$$n$$$ integers will follow, the sequence $$$a_1, a_2,..., a_n$$$, where $$$a_i$$$ represents the strength of the i-th student ($$$1 \le a_i \le x$$$).
It is guaranteed that the sums of $$$n$$$ and $$$x$$$ over all cases will not exceed $$$200$$$.
For each case, you should print a single integer, the minimum number of days that must pass for Esomer to reduce $$$x$$$ to $$$0$$$.
13 41 1 1
1
—
Problem idea: Javi
Problem preparation: Javi
Ocurrences: Advanced 3
Óscar is playing a video game. His goal is to collect as many coins as possible. To do this, he has to choose one of the $$$n$$$ available characters. The $$$i$$$-th character has an attack power of $$$a_i$$$ points and a defense power of $$$b_i$$$ points. To collect the coins, he must defeat monsters (there are $$$m$$$ monsters). The $$$j$$$-th monster has an attack power of $$$c_j$$$ points, a defense power of $$$d_j$$$ points, and rewards $$$e_j$$$ coins when defeated.
In order to defeat a monster, Óscar needs his character's attack power to be greater than or equal to the monster's defense power, and his character's defense power to be greater than or equal to the monster's attack power. In other words, character $$$i$$$ can defeat monster $$$j$$$ if and only if $$$a_i \geq d_j$$$ and $$$b_i \geq c_j$$$.
Óscar can only choose one character, but he can defeat as many monsters as he wants. Once a monster is defeated, it cannot be defeated again. What is the maximum number of coins that Óscar can collect?
The first line of the input contains an integer $$$t$$$, the number of test cases. ($$$1 \le t \le 100$$$).
The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$).
The next $$$n$$$ lines contain two integers each, $$$a_i$$$ and $$$b_i$$$; the attack and defense power of each character, respectively. ($$$1 \le a_i, b_i \le 10^9$$$).
The next $$$m$$$ lines contain three integers each, $$$c_j$$$, $$$d_j$$$, and $$$e_j$$$; the attack power, defense power, and coins rewarded by monster $$$j$$$. ($$$1 \le c_j, d_j, e_j \le 10^9$$$)
It is guaranteed that the sum of $$$n$$$ and $$$m$$$ over all test cases is at most $$$2 \cdot 10^5$$$.
For each test case, you should print the maximum number of coins that Óscar can collect with a single character.
14 53 14 54 22 23 5 12 1 11 1 14 4 13 3 1
4
16 62 72 54 17 51 27 56 8 14 4 68 1 13 6 37 2 48 4 8
9
—
Problem idea: Hectorungo18
Problem preparation: Esomer
Ocurrences: Novice 10, Advanced 5
Dani has two integers $$$n$$$ and $$$m$$$ and a button which does the following when pressed:
- Generates $$$n$$$ random intervals of the form $$$(l, r)$$$ where $$$1 \leq l \leq r \leq m$$$.
Dani has pressed the button two times, but he has only given you the $$$n$$$ randomly generated intervals from the first press of the button. Please, help Dani to know the probability of not having any pair of intersecting intervals.
A pair of intervals $$$(i, j)$$$ don't intersect if and only if $$$r_{i} \leq l_{j}$$$ or $$$r_{j} \leq l_{i}$$$. Note that it's not guaranteed that after the first button press no pair of intervals intersect. For more information check the notes section below the samples.
It can be proven that the probability can be represented as an simple fraction $$$P/Q$$$ where $$$Q$$$ is coprime to $$$998244353$$$ . Output the value of $$$P \cdot Q^{-1}$$$ modulo $$$998244353$$$ .
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ $$$(1 \leq t \leq 69)$$$. The description of the test cases follows.
The first line consists in two integers $$$n, m$$$ $$$(1 \leq n \leq 269 ; 1 \leq m \leq 6.9 \cdot 10^{6})$$$ — the number of generated intervals after pressing the button and the upper bound of the intervals endpoints, respectively.
Then follows $$$n$$$ lines, each one consisting in two integers $$$l_{i}, r_{i}$$$ $$$(1 \leq l_{i} \leq r_{i} \leq m)$$$ — the endpoints of the generated intervals.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$269$$$.
For each testcase, output a single integer — the probability of not having any pair of intersecting intervals modulo $$$998244353$$$.
81 32 23 43 31 33 32 41 13 44 105 72 23 49 92 151 32 52 698 119 101 101 12 113 33 3
831870295 726721889 259543532 10510086 0 0 1 501184665
In the first test case, there are $$$6$$$ possible distributions, but only $$$5$$$ are valid. This is because if the generated interval was $$$(1, 3)$$$ the intervals $$$(2, 2)$$$ and $$$(1, 3)$$$ would intersect.
In the fourth test case, there are $$$100$$$ possible distributions, but only $$$22$$$ are valid.
In the fifth testcase, the answer is $$$0$$$ because some of the intervals generated after the first press of the button intersect.
—
Problem idea: danx
Problem preparation: danx
Ocurrences: Advanced 6
There are $$$n$$$ towers at Helm's Deep, each of them has a power of $$$a_i$$$ and a strength of $$$b_i$$$. Rohan's strategists determine that the orcs will arrive in $$$q$$$ waves and that in the $$$j$$$-th wave $$$x_j$$$ orcs will attack tower $$$y_j$$$. In that wave, tower $$$y_j$$$ will take a damage of $$$max(0, x_j - a_{y_j} \cdot p_{y_j})$$$, where $$$p_{y_j}$$$ is the number of soldiers in tower $$$y_j$$$. Once any tower $$$i$$$ has taken an amount of damage that is at least $$$b_i$$$, it will be conquered. If some orcs attack an already conquered tower they will just go back to their lines confused (orcs aren't very intelligent). When a tower gets conquered, every soldier there will die. At the start of each wave (before the attack of that wave happens), the inner walls will get an amount of damage equal to the number of conquered towers at that moment. If the inner walls receive a lot of damage Rohan will fall and all hope for humans will be lost, so you want to minimize the damage received after the $$$q$$$ waves.
Rohan counts with $$$m$$$ soldiers and they ask you to help them locate the soldiers strategically. You must create the aforementioned array $$$p$$$ of length $$$n$$$, which must satisfy the following conditions:
- For all $$$i$$$, $$$0 \leq p_i \leq m$$$.
- $$$\sum p_i \le m$$$.
Let the minimum damage that the inner walls take over all possible arrays $$$p$$$ be $$$d$$$. You must determine the value of $$$d$$$ and the lexicographically smallest$$$^\dagger$$$ array $$$p$$$, so that the damage the inner walls take is exactly $$$d$$$.
$$$^\dagger$$$ An array $$$a$$$ is lexicographically smaller than a different array $$$b$$$ of the same length if, at the first position $$$i$$$ where they differ, $$$a_i \lt b_i$$$.
The first line of the input contains a single integer $$$t$$$, the number of test cases. ($$$1 \le t \le 100$$$).
The first line of each test case contains three integers $$$n$$$, $$$m$$$ and $$$q$$$, the number of towers, soldiers and waves, respectively. ($$$1 \le n \le 1000$$$; $$$0 \le m \le 1000$$$; $$$1 \le q \le 50000$$$).
Each of the following $$$n$$$ lines contains two integers, $$$a_i$$$ and $$$b_i$$$, the power and the strength of the $$$i$$$-th tower. ($$$1 \le a_i, b_i \le 10^9$$$).
Then come $$$q$$$ lines, each with two integers $$$x_j$$$ and $$$y_j$$$, the number of orcs and the tower they attack in the $$$j$$$-th wave, respectively. ($$$1 \le x_j \le 10^9$$$; $$$1 \le y_j \le n$$$).
It is guaranteed that neither the sum of $$$n$$$ nor the sum of $$$m$$$ will exceed $$$1000$$$ over all test cases, and that the sum of $$$q$$$ won't exceed $$$50000$$$ over all test cases.
For each test case, on the first line output $$$d$$$, the minimum damage the inner walls can take.
Then, output $$$n$$$ integers, the elements of the array $$$p$$$.
25 15 72 34 53 34 11 13 14 51 33 2100 12 39 45 9 41 11 11 11 11 13 54 55 56 5
2 1 0 1 0 4 0 0 0 0 0 5
—
Problem idea: Esomer
Problem preparation: Esomer
Ocurrences: Advanced 7
Omer is a mathematician who loves programming and the orange trees, when the office hours end he loves playing with his beautiful orange tree.
This orange tree consists of $$$n$$$ oranges numbered from $$$1$$$ to $$$n$$$, connected by $$$n-1$$$ bidirectional branches such that all oranges are connected between them by some sequence of branches. Also this orange tree is rooted in the orange $$$1$$$, and each orange has a weight $$$w_{i}$$$ $$$(1 \lt w_i \lt = n)$$$ where all $$$w_{i}$$$ are different, note that $$$w$$$ is a permutation of length $$$n$$$.
While playing with his orange tree, Omer asks himself some questions of the following form:
Given $$$u, a, b$$$ calculate the value $$$\sum_{i=a}^b f(u, i)$$$ where $$$f(u, i) = $$$ number of oranges with weight divisible by $$$i$$$ in the subtree rooted at orange $$$u$$$.
As he is very busy taking care of his children, he needs you to help him with his orange tree and to answer all his questions.
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 consists in two integers $$$n, q$$$ $$$(2 \leq n, q \leq 2 \cdot 10^{5})$$$ — the number of oranges and the number of questions, respectively.
The second line contains a permutation of length $$$n$$$, $$$w_{1}, w_{2}, ... w_{n}$$$ — the weights of the oranges.
Then follows $$$n-1$$$ lines, each one consisting in two integers $$$u_{i}, v_{i}$$$ $$$(1 \leq u_{i}, v_{i} \leq n)$$$ — meaning that there is a branch between the oranges $$$u$$$ and $$$v$$$.
Finally follows $$$q$$$ lines, each one consisting in three integers $$$u_{i}, a_{i}, b_{i}$$$ $$$(1 \leq u_{i} \leq n ; 1 \leq a_{i} \leq b_{i} \leq n)$$$ — the questions asked by Omer.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^{5}$$$.
It is guaranteed that the sum of $$$q$$$ over all test cases does not exceed $$$2 \cdot 10^{5}$$$.
For each testcase, output $$$q$$$ integers — the answer to the questions.
2 5 4 1 5 3 4 2 2 1 2 4 3 5 3 2 1 2 4 2 3 5 1 1 5 3 2 2 2 6 2 1 1 2 1 1 1 1 1 2 1 2 2 2 1 2 2 1 1 2 2 2
4 3 10 1 2 3 1 1 1 0
—
Problem idea: danx
Problem preparation: danx
Ocurrences: Advanced 8
Bea has two arrays $$$a$$$ and $$$b$$$, both of $$$n$$$ integers.
A permutation of length $$$n$$$ is an array of length $$$n$$$ where each number between $$$1$$$ and $$$n$$$ appears exactly once.
Your task is to find a permutation $$$p$$$ of length $$$n$$$ which maximizes the following value:
$$$(a_1 + b_{p_1})$$$ $$$\&$$$ $$$(a_2 + b_{p_2})$$$ $$$\&$$$ ... $$$\&$$$ $$$(a_n + b_{p_n})$$$.
$$$\&$$$ is the bitwise AND operator, If you don't know how it works, remember that you can search for it on the internet ;)
As there can be a lot of solutions, Bea also wants to find one that minimizes the maximum distance from the position of a value on the chosen permutation to it's original position in the sorted permutation, in other words, Bea wants to find one that minimizes the following value: $$$\max_{1 \leq i \leq n} (|i - pos_i|)$$$ where $$$pos_i$$$ is position of $$$i$$$ in the chosen permutation and $$$|x|$$$ is the absolute value of $$$x$$$.
Please, help Bea :(
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ $$$(1 \leq t \leq 100)$$$. The description of the test cases follows.
The first line consists in one integer $$$n$$$ $$$(2 \leq n \leq 1500)$$$ — the size of the arrays.
Then follows $$$n$$$ integers $$$a_{i}$$$ $$$(0 \leq a_{i} \leq 10^{9})$$$ — the values of $$$a$$$.
Finally follows $$$n$$$ integers $$$b_{i}$$$ $$$(0 \leq b_{i} \leq 10^{9})$$$ — the values of $$$b$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$1500$$$.
For each testcase, output two integers per line, the maximum possible value chosing the permutation optimally, and the minimum maximum distance from the position of a value on the chosen permutation to it's original position in the sorted permutation, so that the maximum value continues to be obtained.
455 13 4 10 03 0 2 11 1537 1 25 8 131 2 35 4 621000000000 10000000001000000000 1000000000
8 1 2 1 7 2 2000000000 0
—
Problem idea: danx
Problem preparation: danx
Ocurrences: Advanced 9
Esomer loves skiing. However, he hates ski lifts because they are very long and always very cold. Determined not to suffer any longer, he has tried to come up with a route that minimizes the time spent on ski lifts. Unfortunately, he is not very good at interpreting the map of the pistes, so he has asked for your help.
The ski resort that Esomer visits can be represented as a directed acyclic graph with $$$n$$$ nodes and $$$m$$$ edges (the pistes). Additionally, there are $$$k$$$ ski lifts that connect node $$$a$$$ to node $$$b$$$. Interestingly, all ski lifts satisfy the condition that it is always possible to reach $$$a$$$ from $$$b$$$ without using any ski lift. It takes Esomer $$$1$$$ minute to traverse a piste or use a ski lift.
Esomer is interested in how much time he needs to spend on ski lifts in order to spend a total of $$$x$$$ minutes at the ski resort, without stopping at any node even for a second, while starting at node $$$y$$$. Esomer can finish his route at any node and leave for home as soon as he has spent the required $$$x$$$ minutes.
Please help Esomer.
The first line contains an integer $$$t$$$, the number of test cases. ($$$1 \le t \le 100$$$).
For each test case, the first line contains four integers $$$n$$$, $$$m$$$ and $$$k$$$. ($$$2 \le n \le 10^5$$$; $$$1 \le m \le \min(10^5, \frac{n \cdot (n-1)}{2})$$$; $$$1 \le k \le 10^2$$$).
Then, there are $$$m$$$ lines, each containing two integers, $$$u$$$ and $$$v$$$, indicating that there is an edge from $$$u$$$ to $$$v$$$. ($$$1 \le u, v \le n$$$).
It is guaranteed that the graph formed by the $$$m$$$ edges is acyclic.
Next, there are $$$k$$$ lines, each containing two integers, $$$a$$$ and $$$b$$$, indicating that there is a ski lift from $$$a$$$ to $$$b$$$. ($$$1 \le a, b \le n$$$; $$$a \neq b$$$).
It is guaranteed that it is possible to reach $$$a$$$ from $$$b$$$ without using any ski lift.
Finally, there is a line containing two integers $$$x$$$ and $$$y$$$, the number of minutes Esomer wants to spend at the ski resort, and the node at which he starts, respectively. ($$$1 \le x \le 10^9$$$; $$$1 \le y \le n$$$). It is guaranteed that Esomer can reach a ski lift from node $$$y$$$.
It is guaranteed that the sum of $$$n$$$ and $$$m$$$ over all test cases is at most $$$10^5$$$, while the sum of $$$k$$$ over all test cases is at most $$$10^2$$$.
For each test case, you should print an integer $$$s$$$, the minimum number of minutes Esomer needs to spend on ski lifts in order to spend a total of $$$x$$$ minutes at the ski resort.
16 5 22 45 46 26 43 42 64 64 2
1
110 13 53 49 45 89 24 21 1010 99 87 55 29 310 23 28 102 94 34 15 712 7
2
—
Problem idea: Esomer
Problem preparation: Esomer
Ocurrences: Advanced 10