John bought a brand new smart watch, this smart watch keeps record of his exercises, mainly, the number of steps John takes during the day. The watch has a feature called "exercise mode", when exercise mode is enabled the watch will "beep" each minute showing the total amount of steps taken since the "exercise mode" was enabled. To take advantage of this feature, John decided to exercise each morning before going to work, his morning exercise will be a walk through a road nearby where he can get fresh air and walk withouth the need to stop to cross streets.
Since John will perform the walk in the mornings, John decided to walk until he has taken at least $$$3000$$$ steps after a watch "beep", but no more than $$$15$$$ minutes to avoid having to rush to get to his office in time. John is very consistent with the amount of $$$X$$$ steps he takes each minute, this means, John takes exactly $$$X$$$ steps each minute, no more, no less.
Given the amount $$$X$$$ of stepss John takes each minute, help John find how many minutes he has to walk to finish his morning exercise.
The first and only line of input contains a single integer number $$$X (1 \leq X \leq 3000)$$$, the number of steps John takes in a minute.
Output a line a single integer number, representing how many minutes John has to walk to finish his morning exercise.
1
15
300
10
2999
2
3000
1
Jaime transportation company started operations in Quadradonia this year, the business was growing and Jaime was transporting packages between any destination in Quadradonia until new law enforced rules to transit in the city. Quadronia has been divided in sectors and is represented by a rectangular shaped matrix of $$$N$$$ rows and $$$M$$$ columns, forming $$$N$$$x$$$M$$$ sectors. The new law enforces that a vehicle can transit on the sector located at the $$$i$$$-th row and $$$j$$$-th column of Quadradonia, if and only if, the truck has been approved with the $$$M_{i,j}$$$ stamp, and can move only to those sectors that share a side in the sectors map if the vehicle has the required stamp to its destination.
The new law has brought problems to Jaime, but not much of them, Jaime currently can operate all his business moving trucks in one sector each, making sure he needs only one stamp per truck, however, the main warehouse where Jaime operates his business is not in the same sector as his home, therefore, Jaime will need to get stamps for his car so he can transit to work each morning. As each required stamp approval needs to be requested independently, and only one request per vehicle is processed at a time, Jaime wants to get the minimum number of stamps for his car.
Given the map of sectors of Quadradonia, the coordinates of the sector where Jaime's home and the main warehouse are located, help Jaime find the minimum number of stamps he must get for him to be able to travel from his home to the main warehouse.
The first line contains two integer numbers separated by a space $$$N$$$ and $$$M$$$ ($$$1 \leq N,M \leq 100$$$) representing the number of rows and columns in Quadradonia sectors map. The next line contains two integer numbers $$$r_h$$$ ($$$1 \leq r_h \leq N$$$), and $$$c_h$$$ ($$$1 \leq c_h, leq M$$$), representing the row and column of the sector where Jaime's home is located. The next line contains two integer numbers $$$r_w$$$ ($$$1 \leq r_w \leq N$$$), and $$$c_w$$$ ($$$1 \leq c_w \leq M$$$), representing the row and column of the sector where the main warehouse is located. Each of the next $$$N$$$ lines contains $$$M$$$ integer numbers separated by a space, where the $$$j$$$-th number of the $$$i$$$-th line represents the stamp $$$M_{i,j}$$$ required to transit in the sector of the $$$i$$$-th row and $$$j$$$-th column ($$$1 \leq M_{i,j} \leq 10$$$).
Output a line containing an integer number, the minimum number of stamps Jaime must get so he can transit from his home sector to the main warehouse sector.
5 5 1 1 5 3 1 2 3 2 3 6 2 5 7 3 4 7 3 4 5 3 2 1 3 5 5 2 3 7 9
4
The tech company, Weta, has announced that it will continue to make layoffs once a week for the next $$$M$$$ weeks.
For the layoffs, Weta has established that it will fire all employees who have a score greater than $$$Q_i$$$. $$$Q_i$$$ is different every week, and obviously the current week score must be lower than the previous one.
Fortunately, the employees know about this in advance. That is why everyone who would be affected by the week's layoff must make their score equal to $$$Q_i$$$.
Weta will not notice this, since Weta does not care about the number of employees fired, but the sum of the employees score.
You, as the representative of the employees, must give Weta the sum of the scores once they have all adjusted their scores to avoid being fired.
Note that only employees with a score greater than $$$Q_i$$$ can change their score.
The first line of input contains two integer $$$N$$$, $$$M$$$ ($$$1$$$ $$$\leq$$$ $$$M$$$ < $$$N$$$ $$$\leq$$$ $$$10^5$$$), the number of employees in Weta and the number of layoffs.
The next line contains $$$N$$$ integers $$$S_i$$$ ($$$1$$$ $$$\leq$$$ $$$S_i$$$ $$$\leq$$$ $$$10^9$$$)
The following $$$M$$$ lines describe the layoffs. The i-th of them contains $$$Q_i$$$, the score for the layoff of the $$$i-th$$$ week. ($$$1$$$ $$$\leq$$$ $$$Q_i$$$ $$$\leq$$$ $$$10^9$$$)
Print $$$M$$$ lines with the sum of employees' scores.
5 3 2 3 5 5 10 8 7 1
23 22 5
Denji is trying to kill the algorithm demon. To kill him, Denji must perform this task.
An operation can be one of the following:
- Add a number to the end of the array.
- Delete from the array the number added in operation i.
- Add X to the number added in operation i.
- Print the number of smaller elements than the number added in operation i.
Unfortunately, Denji only knows how to use chainsaws, not computers, so he asked for your help to kill the algorithm demon.
The first line of input contains an integer $$$M$$$ ($$$1$$$ $$$\leq$$$ $$$M$$$ $$$\leq$$$ $$$10^5$$$).
The following m lines describe the operations. The i-th of them begins with a number $$$type$$$ ($$$type$$$ $$$\in$$$ {1,2,3,4}), which will represent the type of the operation given.
If $$$type$$$ = 1, there will be one more integer in the line: $$$A$$$ (1 $$$\leq$$$ $$$A$$$ $$$\leq$$$ $$$10^9$$$), which correspond the operation 1.
If $$$type$$$ = 2, there will be one more integer in the line: $$$B$$$ (1 $$$\leq$$$ $$$B$$$ $$$ \lt $$$ $$$i$$$), which correspond the operation 2. It is guaranteed that the number added in operation $$$B$$$ is still in the array.
If $$$type = 3$$$, there will be two integers more in the line: $$$B$$$, $$$A$$$ (1 $$$\leq$$$ $$$B$$$ $$$ \lt $$$ $$$i$$$; 1 $$$\leq$$$ $$$A$$$ $$$\leq$$$ $$$10^9$$$), which correspond the operation 3. It is guaranteed that the number added in operation $$$B$$$ is still in the array.
If $$$type$$$ = 4, there will be one more integer in the line: $$$B$$$ (1 $$$\leq$$$ $$$B$$$ $$$ \lt $$$ $$$i$$$), which correspond the operation 4. It is guaranteed that the number added in operation $$$B$$$ is still in the array.
It is guaranteed that the first operation is of type 1.
For each operation 4, please print a line containing the answer.
5 1 4 1 5 1 4 4 2 4 3
2 0
9 1 5 1 5 1 10 4 3 2 2 4 3 3 3 7 4 3 4 1
2 1 1 0
The exam period is approaching in Huron Academy. Legendary Huron is studying for his math exam and is trying to solve the following problem:
He is given a system of $$$m$$$ expressions with $$$n$$$ variables $$$a_0, a_1, \dots, a_{n-1}$$$. Each expression is of the form:
$$$$$$a_{x_i}+a_{y_i} \square_i c_i$$$$$$
Where $$$c_i$$$ is an integer equal to $$$0$$$, $$$1$$$ or $$$2$$$, and $$$\square_i$$$ is any of the following symbols:
- "=". Which denotes $$$a_{x_i}+a_{y_i} = c_i$$$.
- "!=". Which denotes $$$a_{x_i}+a_{y_i} \neq c_i$$$.
- "<". Which denotes $$$a_{x_i}+a_{y_i} \lt c_i$$$.
- ">". Which denotes $$$a_{x_i}+a_{y_i} \gt c_i$$$.
- "<=". Which denotes $$$a_{x_i}+a_{y_i} \leq c_i$$$.
- ">=". Which denotes $$$a_{x_i}+a_{y_i} \geq c_i$$$.
Legendary Huron needs to find out if there are integers $$$a_0, a_1, \dots, a_{n-1}$$$ that satisfies the system of expressions, such that $$$0 \leq a_i \leq 1$$$ for all $$$0 \leq i \leq n-1$$$. Help Legendary Huron to solve this problem.
The first line contains two integres $$$n$$$ and $$$m$$$ ($$$1 \leq n,m \leq 10^5$$$).
The following $$$m$$$ lines contains each two integers $$$x_i$$$ and $$$y_j$$$ ($$$0 \leq x_i, y_i \leq n-1$$$), followed by a string $$$\square_i$$$ ($$$\square_i$$$ is "=", "!=", "<", ">", "<=" or ">=", without the quotation marks) and other integer $$$c_i$$$ ($$$0 \leq c_i \leq 2$$$), denoting that the $$$i$$$-th expression is $$$a_{x_i}+a_{y_i} \square_i c_i$$$.
Print "Yes" (without the quotation marks) if there exists a solution for the system of expressions; otherwise print "No".
3 3 0 1 = 0 1 2 = 1 0 2 = 1
Yes
3 3 0 1 = 0 1 2 = 1 0 2 = 0
No
12 6 0 1 = 2 2 3 != 0 4 5 < 2 6 7 > 1 8 9 <= 1 10 11 >= 0
Yes
Legendary Huron has a fence with $$$n$$$ planks, numbered from $$$0$$$ to $$$n-1$$$. Each plank has a brightness value, where the $$$i$$$-th plank initially has brightness $$$a_i$$$.
He also has a painting machine that can be used to paint a contiguous sequence of planks. This painting machine has $$$n$$$ paint slots numbered from $$$0$$$ to $$$n-1$$$, where the paint in the $$$i$$$-th slot has brightness $$$b_i$$$. To use this machine, Legendary Huron first selects a range of planks $$$[l,r]$$$ to paint them and an initial paint slot $$$k$$$, then the painting machine recolors the $$$l$$$-th plank using its $$$k-th$$$ paint slot, recolors the $$$(l+1)$$$-th plank using its $$$((k+1) \% n)$$$-th paint slot, ..., recolors the $$$r$$$-th plank using its $$$((k+r-l) \% n)$$$-th paint slot. In other words, it changes the brightness of the $$$i$$$-th plank to $$$b_{(k+i-l)\%n}$$$ for all $$$i \in [l,r]$$$.
Legendary Huron is a fan of beautiful fences. He defines the beauty of a sequence of $$$m$$$ planks with brightness $$$c_0, c_1, \dots, c_{m-1}$$$ as follows:
$$$$$$ \max_{0 \leq i \leq j \lt m}(c_j-c_i) $$$$$$
During the following $$$q$$$ days, Legendary Huron will perform one of two possible actions: repainting a sequence of planks using his painting machine or taking a photo of a sequence of planks. The action of Legendary Huron in the $$$i$$$-th day can be represented in the following way:
- Given three integers $$$l$$$, $$$r$$$, $$$k$$$, he will repaint the planks in the range $$$[l,r]$$$ and the initial paint slot for the painting machine will be the $$$k$$$-th slot. After repainting the planks, he wants to know the beauty of the whole fence.
- Given two integers $$$l$$$ and $$$r$$$, he will take a photo of the planks in the range $$$[l,r]$$$. After taking the photo, he wants to know the beauty of the sequence of planks that appears in the photo.
Help Legendary Huron to find the required beauty after each action.
The first line contain two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n,q \leq 2 \cdot 10^5$$$).
The second line contain $$$n$$$ integers $$$a_0, a_1, \dots, a_{n-1}$$$ ($$$|a_i| \leq 10^9$$$).
The third line contain $$$n$$$ integers $$$b_0, b_1, \dots, b_{n-1}$$$ ($$$|b_i| \leq 10^9$$$).
The following $$$q$$$ lines starts with an integer $$$t$$$ ($$$t \in \{1,2\}$$$). If $$$t=1$$$, then three integers $$$l$$$, $$$r$$$, $$$k$$$ follows ($$$0 \leq l \leq r \leq n - 1$$$ and $$$0 \leq k \leq n - 1$$$), denoting that Legendary Huron will repaint planks as described above. If $$$t=2$$$, then two integers $$$l$$$ and $$$r$$$ follows ($$$0 \leq l \leq r \leq n - 1$$$), denoting that Legendary Huron will take a photo as described above.
After each action, print one line with the required beauty.
4 5 1 3 2 5 2 6 4 9 2 0 1 2 2 3 1 0 3 2 2 0 1 2 2 3
2 3 5 5 4
4 2 -1 2 4 6 1 1 1 1 2 0 3 1 0 0 3
7 5
It's finals time in university and Gustavo has been worried about his modern art appreciation exams.
Of course this is not like any other modern art appreciation class, this class uses advanced programs to evaluate the paintings, and give the correct interpretation of them instead of this false idea that museums seek to sell, saying that there is an open interpretation for modern art (false of course).
The final exam consist of developing a faster algorithm to retrieve the correct interpretation of a painting.
To main algorithm is too hard to explain in this brief problem description, but an important part of the exam is to reflect the picture in several axes, and then reevaluate its interpretation, just to be sure that even changing its point of view it will always give the same interpretation.
Tomorrow is due date and Gustavo is almost done with the exam, he already implemented the main algorithm to interpret pictures, but he is also getting sleepy and still needs to implement a code to reflect the picture correctly, but he is already too tired to do it.
So you like a good friend are here to help him.
There will be 5 different queries that you need to respond:
- r a: reflect the picture by axe a
- r b: reflect the picture by axe b
- r c: reflect the picture by axe c
- r d: reflect the picture by axe d
- q x y: id of pixel in position (x, y)
The initial id's of the pixels are in order from left to right, and then from top to bottom.
The evaluated paintings are always a perfect square for this exam.
In the first line there will be two integers n $$$(1 \leq n \leq 10^9)$$$, q $$$(1 \leq q \leq 10^5)$$$, the size of the painting and the number of queries respectively.
In the next q lines, there will be one query, it will correspond to one of the query types listed before.
For each query of type (q x y), print a line with the current index of the pixel in that position. Where $$$'x'$$$ is the number of the row from top to bottom and $$$'y'$$$ is the number of the column from left to right.
4 3 q 2 3 r a q 2 3
7 10
Riko was given an interesting problem as part of her graph theory homework.
You are given a graph with $$$n$$$ vertices and $$$m$$$ edges. Some of the edges are directed, while the rest are undirected. You must determine if it's possible to assign directions to all the undirected edges in such a way that the edges of the resulting directed graph can be partitioned into directed edge-disjoint cycles.
Help Riko solve her homework so she can go read her books!
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 300$$$, $$$1 \le m \le \frac{n(n - 1)}{2}$$$) — the number of vertices and the number of edges in the graph respectively.
Each of the following $$$m$$$ lines contains three integers $$$u, v, d$$$ describing an edge. ($$$1 \le u \le n$$$, $$$1 \le v \le n$$$, $$$d \in \{0, 1\}$$$, $$$u \neq v$$$) If $$$d = 0$$$ then this is an undirected edge between vertices $$$u$$$ and $$$v$$$. If $$$d = 1$$$ then this is a directed edge from vertex $$$u$$$ to vertex $$$v$$$.
It is guaranteed that any two vertices have at most one edge connecting them.
Print a single line containing YES if it is possible to direct the edges as desired, and NO otherwise.
6 12 1 2 1 1 3 1 1 5 0 1 6 0 2 3 0 2 4 0 2 6 1 3 4 1 3 5 0 4 5 1 6 4 1 6 5 0
YES
6 12 1 2 1 1 3 1 1 5 0 6 1 1 2 3 0 2 4 0 2 6 1 3 4 1 3 5 0 4 5 1 6 4 1 6 5 1
NO
Ivan learned how to do RMQ queries, so he was introduced to the RMQ mega query. Given a set of distinct indices $$$ind$$$, ordered in increasing order $$$ind_1 \lt ind_2 \lt \dots \lt ind_m$$$. An RMQ mega query with these indices, over the sequence $$$a$$$, is defined as:
$$$$$$\sum_{i=1}^m\sum_{j=i}^m \max{ \left( a_{ind_i},\, \dots, \, a_{ind_j}\right) }$$$$$$
Ivan just learned how to solve them, now he proposes $$$q$$$ mega queries.
the first line receives a single integer $$$n$$$ ($$$1 \le n \le 5\times {10}^5$$$), indicating the size of the sequence $$$a$$$.
The second line contains $$$n$$$ integers $$$a_i$$$ ($$$1 \le a_i \le {10}^9$$$) separated by spaces, representing the sequence $$$a$$$.
The third line receives a single integer $$$q$$$ ($$$1 \le q \le 3\times {10}^5$$$), indicating the number of mega queries.
The following $$$2q$$$ lines contain the mega queries.
The first line of each mega query is an integer $$$m$$$ ($$$1 \le m \le n$$$), the number of indices in the mega query.
The second line of each mega query contains the indices $$$ind$$$, ordered in increasing order.
The sum total of the $$$m$$$ is at most $$$5\times {10}^5$$$.
For each query, print a single line with an integer indicating the answer.
6 2 7 5 8 1 2 5 2 1 6 6 1 2 3 4 5 6 4 1 3 5 6 4 1 3 4 5 4 2 4 5 6
12 136 51 63 60
The president of Treetopia has built $$$n - 1$$$ bidirectional roads connecting the $$$n$$$ cities in the country, in such a way that it is possible to travel from any city to any other using the constructed roads.
To simplify traffic, the president decided to assign a direction to each road so that it is only possible to traverse it in that direction. Additionally, she determined $$$n$$$ values $$$b_0, b_1, \dots, b_{n - 1}$$$ such that the beauty of a city with exactly $$$k$$$ outgoing roads (that is, $$$k$$$ roads that are directed away from the city) is equal to $$$b_k$$$.
The president wants to assign the directions of each road in such a way that the sum of the beauties of all the cities is maximized. What is the maximum sum of beauties she can achieve?
The first line of the input contains an integer $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$) — the number of cities in Treetopia.
The next line contains $$$n - 1$$$ integers $$$b_0, b_1, \dots, b_{n - 1}$$$ ($$$1 \le b_i \le 10^9$$$), where $$$b_k$$$ represents the beauty of a city with exactly $$$k$$$ outgoing roads.
Each of the next $$$n - 1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$), describing a road between cities $$$u$$$ to $$$v$$$. It is guaranteed that it is possible to go from any city to any other using these roads.
Print a single integer — the maximum possible sum of beauties of all the cities after directing the roads.
5 1 2 3 3 1 1 2 1 3 2 4 2 5
9
2 2 3 1 2
5
10 2 5 4 1 2 5 3 1 5 7 1 9 5 3 5 4 6 3 9 8 5 8 1 7 10 9 4 2
47
A telephone keypad is a keypad installed on a push-button telephone or similar telecommunication device which usually contains $$$10$$$ keys, each of which represents a digit used to dial a telephone number. Today most telephones have an integrated memory, this memory allows users to store common used telephone numbers using a string identifier making it easier for the user to dial numbers without the need of having it memorized or stored in a paper agenda. In order for users to store the string identifier the keypad associates letters to some of the key digits, traditionally this is named as "letter mapping" and the most common one is shown in the following table:
| Digit | Letters |
| 2 | abc |
| 3 | def |
| 4 | ghi |
| 5 | jkl |
| 6 | mno |
| 7 | pqrs |
| 8 | tuv |
| 9 | wxyz |
Using this "letter mapping" the user could store the string to identify a telephone number using the keypad, for example, to store the identifier "jhon" the user can press the keypad in the following order: "5466". One problem of this approach is that several identifiers can be represented pressing the keypad in the same order, for example, "5466" that can be used to represent "jhon", can represent also "kino".
Jaime has a list of $$$N$$$ identifiers to be stored in his grandfathers old telephone, they suspect a lot of these identifiers can be represented with the same numbers, however, they have not been able to verify their claim, that is why they asked for your help to given the list of identifiers and a set of $$$Q$$$ keypad presses to query, find how many identifiers of the list can be represented with each of the keypad presses.
The first line of input contains two integer numbers $$$N$$$ ($$$1 \leq N \leq 10^5$$$) and $$$Q$$$ ($$$1 \leq Q \leq 10^5$$$), representing the number of identifiers in the list and the number of keypad presses to query. Each of the next $$$N$$$ lines contains one of the strings of the list of identifiers, each string consists only of lowercase english alphabet letters and have a length between 1 and 10 characters. Each of the next $$$Q$$$ lines contains a keypad press to query, each of the keypad presses contains between 1 and 10 digits between 2 and 9.
For each query in the input print a line with a single integer, representing the number of identifiers in the list that can be represented using the keypad presses in the query.
4 5 jhon abcde a kino 5466 2 22233 2222 5466
2 1 1 0 2
Ladybug is an agent specialized in snatch-and-grab jobs, now he has a job that requires him to go to station $$$X$$$ and grab a certain suitcase, starting from station 1.
To do that he will be travelling through the stations via a bullet train, so he can move from station $$$A$$$ to station $$$B$$$ if and only if there exists a train line that connects such stations, it is always possible to reach any station from any other station and that path is unique.
One thing about agent ladybug is that he has very bad luck, he forgot the map of the train lines in the taxi, so, he does not know how to get to station $$$X$$$ from his initial station, the lack of a map will not stop him, he will travel through the stations without the map, knowing that eventually he will reach his destination.
Each station has signs that indicate what other stations are reachable taking a train from there. If the agent hasn't already reached station $$$X$$$, he will need to pick an arbitrary station to go to. He will not pick a station he has already visited, except if he reached a dead end (he cannot go to a new station) and return from where he came from.
It's guaranteed that he will at some point reach the station $$$X$$$ with this method, but because he has very bad luck, that will end up taking him the longest amount of rides possible. Help his contractor know how many rides the agent has to take to reach station $$$X$$$.
Note:
- A ride is a movement between stations.
- If station $$$Y$$$ has a sign that indicates the agent can reach station $$$X$$$ taking a train from that station, the agent will take that train first.
The first contains two integers separated by a space $$$N$$$ ($$$2 \leq N \leq 10^6$$$) and $$$X$$$ ($$$2 \leq X \leq N$$$), indicating the number of stations in train network and the station where the agent should grab the suitcase. Each of the next $$$N - 1$$$ lines contains two integer numbers $$$A$$$ and $$$B$$$ ($$$1 \leq A, B \leq N$$$), indicating that there is a sign at station $$$A$$$ which indicates there is a train the agent can use to reach station $$$B$$$ from $$$A$$$, and viceversa.
Print one line with an integer number, representing the amount of rides the agent needs to take to reach station $$$X$$$.
5 5 1 2 2 3 3 4 4 5
4
7 4 2 1 3 1 2 4 2 5 3 6 3 7
8
2 2 1 2
1