Grammy loves playing the worldwide famous game League of Legends.
In the latest version, there is a special rule that players can choose to play with. Under this rule, $$$10$$$ players will be divided into Red team and Blue team. Each team consists of $$$5$$$ players and every player has an initial HP value. If none of all $$$5$$$ players from one team has positive HP value, this team will lose this game. In each turn, the team can choose a player and reduce his HP value by $$$1$$$. Blue team will start first.
Now Grammy wants to know if both teams play in optimal strategy, which team will win the game.
The input contains only a single case.
There are $$$5$$$ integers $$$B_1,B_2,B_3,B_4,B_5$$$ ($$$1 \leq B_i \leq 4\times10^8$$$) in the first line, indicating the HP value of each player in Blue team.
There are $$$5$$$ integers $$$R_1,R_2,R_3,R_4,R_5$$$ ($$$1 \leq R_i \leq 4\times10^8$$$) in the second line, indicating the HP value of each player in Red team.
If Blue team will win, output "Blue" in one line. Otherwise, output "Red" in one line.
1 1 2 3 4 2 4 1 5 3
Red
2 3 4 5 6 1 2 3 4 5
Blue
There are $$$n$$$ ancient Greek maps describing the fabled islands Atlantis. The maps are labeled by $$$1,2,\dots,n$$$. The $$$i$$$-th map shows the rectangle area $$$R_i$$$ is a part of Atlantis. The sides of all rectangles are parallel to the axes. There may be multiple islands, and the rectangles may overlap.
Unfortunately, some maps are even unreliable so they will not be considered. You will be given $$$q$$$ queries. In the $$$i$$$-th query, you will be given two integers $$$s_i$$$ and $$$t_i$$$ ($$$1\leq s_i\leq t_i\leq n$$$). Please write a program to figure out the total area of Atlantis when all maps labeled by $$$k$$$ ($$$s_i\leq k\leq t_i$$$) are unreliable.
The input contains only a single case.
The first line of the input contains two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n,q \leq 100\,000$$$), denoting the number of maps and the number of queries.
In the next $$$n$$$ lines, the $$$i$$$-th line contains four integers $$$xa_i$$$, $$$ya_i$$$, $$$xb_i$$$ and $$$yb_i$$$ ($$$0\le xa_i \lt xb_i\leq 2\,000$$$, $$$0\le ya_i \lt yb_i\leq 2\,000$$$), describing the $$$i$$$-th map $$$R_i$$$. $$$(xa_i,ya_i)$$$ is the southwest corner of $$$R_i$$$, and $$$(xb_i,yb_i)$$$ is the northeast corner of $$$R_i$$$.
In the next $$$q$$$ lines, the $$$i$$$-th line $$$(1 \le i \le q)$$$ contains two integers $$$s_i$$$ and $$$t_i$$$ ($$$1\leq s_i\leq t_i\leq n$$$), describing the $$$i$$$-th query.
For each query, print a single line containing an integer, denoting the total area using the information of all reliable maps in this query.
3 6 10 10 20 20 12 12 22 22 15 15 25 25 1 1 2 2 3 3 1 2 2 3 1 3
151 175 136 100 100 0
You are given eight points in three-dimensional space, please check if they can form a cube.
A cube is a regular hexahedron, bounded by six square faces, with three meeting at each vertex.
The first line contains a single integer $$$T$$$ ($$$1 \leq T \leq 100$$$), denoting the number of test cases.
For each test case, each of the following eight lines containing three integers $$$x,y,z$$$ ($$$-100 \leq x,y,z \leq 100$$$), denoting the coordinates of the eight points, respectively.
For each test case, output a single line "YES" if the points can form a cube, or "NO" if they don't.
3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -4 -6 -2 5 9 10 12 -11 11 -9 4 8 -2 -16 9 7 -1 21 -7 -6 19 10 -1 0 0 0 0 2 2 1 0 0 1 0 2 0 2 0 0 0 2 1 2 0 1 2 2 0
NO YES NO
There is an undirected graph with $$$n$$$ vertices and $$$m$$$ edges. The vertices are labelled by $$$1,2,\dots,n$$$. The $$$i$$$-th edge connects the $$$u_i$$$-th vertex and the $$$v_i$$$-th vertex, the length of which is $$$w_i$$$. Here, $$$u_i$$$'s binary representation is always a prefix of $$$v_i$$$'s binary representation. Both binary representations are considered without leading zeros. For example, $$$u_i=2_{10}=\textbf{10}_2$$$, $$$v_i=5_{10}=\textbf{10}1_{2}$$$.
You will be given $$$q$$$ queries. In the $$$i$$$-th query, you will be given two integers $$$s_i$$$ and $$$t_i$$$. Please write a program to figure out the length of the shortest path from the $$$s_i$$$-th vertex to the $$$t_i$$$-th vertex, or determine there is no path between them.
The input contains only a single case.
The first line of the input contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 100\,000$$$, $$$1\leq m\leq 200\,000$$$), denoting the number of vertices and the number of edges.
In the next $$$m$$$ lines, the $$$i$$$-th line $$$(1 \le i \le m)$$$ contains three integers $$$u_i,v_i$$$ and $$$w_i$$$ ($$$1\le u_i \lt v_i\leq n$$$, $$$1\leq w_i\leq 10^9$$$), describing the $$$i$$$-th edge. It is guaranteed that $$$u_i$$$'s binary representation is a prefix of $$$v_i$$$'s binary representation.
In the next line, there contains a single integer $$$q$$$ ($$$1\leq q\leq 200\,000$$$), denoting the number of queries.
In the next $$$q$$$ lines, the $$$i$$$-th line $$$(1 \le i \le q)$$$ contains two integers $$$s_i$$$ and $$$t_i$$$ ($$$1\leq s_i,t_i\leq n$$$, $$$s_i\neq t_i$$$), describing the $$$i$$$-th query.
For each query, print a single line containing an integer, denoting the length of the shortest path. If there is no path, print "-1" instead.
5 6 1 2 4 1 3 2 1 4 5 1 5 8 2 4 3 2 5 2 4 2 3 1 4 1 5 4 5
6 5 6 5
3 1 1 2 100 3 1 2 1 3 2 3
100 -1 -1
A string is palindromic iff it reads the same right to left as left to right. For example "abba", "zjcpcjz" are palindromes. Chenjb loves palindromes, and he owns an extremely long palindrome string $$$S$$$.
Yesterday, RMB player Chenjb paid to open $$$m$$$ boxes in a popular mobile game. Every time he pays to open a box, he will get an item called "SSR" (Specially Super Rare) with the probability of $$$0.003\%$$$. Every time Chenjb got such an item, he would either delete a character or modify a character in his own string $$$S$$$ to celebrate his luck.
Today, Chenjb wants his string $$$S$$$ to be palindrome again by removing some characters from $$$S$$$. Please write a program to help him find the longest palindromic subsequence of the current string $$$S$$$.
The input contains only a single case.
The first line contains a string $$$S$$$ which consists of $$$n$$$ ($$$1 \leq n \leq 10^7$$$) lower-case English letters, denoting the current string.
The second line contains a single integer $$$m$$$ ($$$1\leq m\leq 10^7$$$), denoting the number of boxes Chenjb opened yesterday.
Print a single line containing an integer, denoting the length of the longest subsequence of $$$S$$$.
abadba 31274
5
There are $$$n$$$ robots and $$$m$$$ energy bars in the Dream Kingdom. DreamGrid, the king, is trying to make a fair distribution of the energy bars. A fair distribution exists if and only if the number of the energy bars is a multiple of the number of robots.
The only tool DreamGrid has is a powerful laser gun. Every time he turns on the laser gun, he can do exactly one of the two things:
- Create a new energy bar.
- Destroy a robot.
To avoid the extinction of robots, it's forbidden to destroy all the $$$n$$$ robots. It takes one dollar to turn on the laser gun once. You are asked to find the minimum cost of making a fair distribution.
There are multiple test cases. The first line of the input contains an integer $$$T$$$ ($$$1 \le T \le 1\,000$$$), indicating the number of test cases. For each test case:
The only line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 10^8$$$), indicating the initial number of robots and energy bars.
For each test case output one line containing an integer, indicating the minimum cost to get a fair distribution.
3 3 12 10 6 8 20
0 4 2
For the third sample, the best way is to destroy a robot and create an energy bar. After that, we have $$$7$$$ robots and $$$21$$$ energy bars, which leads to a fair distribution.
"HearthStone" is an online digital collectible card game developed and published by Blizzard Entertainment.
In the game, players have to summon minions and cast spells to attack their opponent.
The following 5 paragraphs illustrate the rules that you need to know in order to solve this problem.
Each minion has its attack value and its hitpoint value.
When a minion receives damage, its hitpoint value decreases by the damage value.
Whenever a minion has a non-positive hitpoint value, it dies.
Minions can have "Deathrattle($$$x$$$/$$$y$$$)" properties, that is, when this minion dies, another minion with $$$x$$$ attack and $$$y$$$ hitpoint will be summoned instantly. Additionally, the summoned minion does not have any "Deathrattle" property.
"Defile" is a spell. When cast, the spell will deal $$$1$$$ damage to all minions, and if any minion dies, the spell will be automatically cast again.
Grammy is a famous player who ranked top $$$10^9$$$ among all "HearthStone" players. Nonetheless, she is unhappy because she does not know how to use "defile" just like the textbook. She wants to do some practice.
$$$n$$$ minions have been placed on the battlefield. The $$$i$$$-th of them have $$$0$$$ attack, $$$10^9$$$ hitpoint, and "Deathrattle($$$i$$$/$$$i$$$)". Grammy can modify each minion's hitpoint to another positive value before she cast the last "Defile" in her hand, can you help her to find out a way to modify each minion's hitpoint so that the recasting effect of the spell will be triggered $$$2n$$$ times? In other words, the spell is cast $$$2n+1$$$ times in total, manually or automatically.
The input contains only a single case.
The only line of the input contains a positive integer $$$n$$$ ($$$1\leq n\leq 1\,000\,000$$$), indicating the total number of minions on the battlefield.
If the solution exists, output $$$n$$$ integers in one line, the $$$i$$$-th one represents the hitpoint value of the $$$i$$$-th minion after Grammy's modification.
Otherwise output "-1" in one line.
If there are multiple solutions, output any.
3
-1
8
8 1 13 11 2 4 5 6
The rules of "HearthStone" in this problem might be different from the original game, so please read the statement carefully.
The original problem name is "Separation Judgement Problem of Rope-made 3 Cycle Venn Diagram with Overlapping Intersections", but it can't fit into the margin.
Three cyclic ropes are lying on the table, the projection of which forms a Venn Diagram.
As the illustration shows, these ropes (indexed from one to three) have six overlapping intersections, indexed from one to six respectively.
Grammy wants to pull the ropes apart, but it seems that they are tied together, so she needs to cut a subset of the three ropes with scissors. She is wondering how many different ways are there to choose the subset so that these ropes are separable afterward. Can you tell her the answer?
Note: Two subsets are different if and only if there is at least one rope being chosen in one of the subsets and not being chosen in the other. The empty set should also be considered.
The input contains only a single case.
The only line of the input consists of $$$6$$$ boolean variables (either "true" or "false") in one line, the $$$i$$$-th one representing whether the larger-indexed rope is on top of the other or not at the $$$i$$$-th intersection.
One integer, the answer to the problem.
true false false true true false
6
There is a connected undirected graph with $$$n$$$ vertices and $$$m$$$ edges. Vertices are indexed from $$$1$$$ to $$$n$$$. There is infinite jewelry in vertex $$$i$$$ ($$$2\leq i\leq n$$$), each valued $$$a_i$$$. Grammy starts at point $$$1$$$. Going through each edge consumes $$$1$$$ unit of time. She can pick up a piece of jewelry at vertex $$$i$$$ and put it down at vertex $$$1$$$. Picking up and putting down a piece of jewelry can be done instantly. Additionally, she can carry at most 1 piece of jewelry at any time. When she put down a piece of jewelry valued $$$x$$$ at vertex $$$1$$$, she obtains the value of it. Now, for each $$$k$$$ between $$$1$$$ and $$$T$$$ (inclusive) she wonders what is the maximum value she can get in $$$k$$$ units of time.
The input contains only a single case.
The first line contains three integers $$$n$$$, $$$m$$$, and $$$T$$$ ($$$1\leq n,m,T\leq 3\,000$$$).
The second line contains $$$n-1$$$ integers $$$a_2, a_3, \dots, a_n$$$ ($$$1\leq a_i\leq 3\,000$$$).
The following $$$m$$$ lines describe $$$m$$$ edges. Each line contains 2 integers $$$x_i$$$ and $$$y_i$$$ ($$$1\leq x_i,y_i\leq n$$$), representing a bidirectional edge between vertex $$$x_i$$$ and vertex $$$y_i$$$.
Note that the graph may contain self-loops or duplicated edges.
Print $$$T$$$ integers in one line, the $$$k$$$-th ($$$1\leq k\leq T$$$) of which denoting the maximum value she can get in $$$k$$$ units of time.
5 6 5 2 3 4 5 1 2 4 5 1 4 2 3 1 3 3 3
0 4 4 8 8
Grammy's kingdom is in danger. Some foreign invaders have intruded into her kingdom and they are destroying the traffic system. There are $$$n$$$ stations indexed from $$$1$$$ to $$$n$$$ in the traffic system. Moreover, there are $$$m$$$ ($$$m\leq n$$$) airports located in some of the stations. If you are in station $$$i$$$, you can transfer to station $$$i+1$$$ if $$$i$$$ and $$$i+1$$$ haven't been destroyed. If you are in station $$$i$$$ with an airport, you can fly to station $$$j$$$ if $$$i\leq j$$$ and station $$$j$$$ has an airport and both of the stations haven't been destroyed. We define the stability $$$G$$$ of the system as the number of routes that still available.
Formally, $$$G=\sum_{1\leq i\leq j\leq n}$$$[a person in station $$$i$$$ can transfer to station $$$j$$$ via several stations or airports].
At each moment $$$i$$$ ($$$1\leq i\leq n$$$), the invaders will randomly choose an undestroyed station $$$x$$$ and destroy it as well as the airport in it (If there exists an airport in it).
We define $$$E(x)$$$ as the expected value of $$$x$$$. Grammy wonders the value of $$$\sum_{i=1}^n E(G_i)$$$ modulo $$$998\,244\,353$$$. Could you please help her? Here, $$$G_i$$$ denotes the value of the stability $$$G$$$ after the invaders destroying the $$$i$$$-th chosen station at the $$$i$$$-th moment.
The input contains only a single case.
The first line contains two positive integers $$$n$$$ and $$$m$$$ ($$$1\leq n\leq 2\,000\,000$$$, $$$0\leq m\leq n$$$), denoting the number of stations and the number of airports.
The second line contains $$$m$$$ distinct integers $$$x_1, x_2, \dots, x_m$$$ ($$$1\leq x_i\leq n$$$), denoting the indexes of station that has an airport.
Output one integer, the value of $$$\sum_{i=1}^n E(G_i)$$$ modulo $$$998\,244\,353$$$.
1 0
0
3 3 1 2 3
4
6 2 2 4
16637434
It can be proved that the answer can be represented as a rational number $$$\dfrac pq$$$ with $$$\gcd(p,q)=1$$$. Therefore, you are asked to find the value of $$$pq^{-1} \bmod 998\,244\,353$$$. It can be shown that $$$q \bmod 998\,244\,353\neq 0$$$ under the given constraints of the problem.
Grammy is a CS professor at Sakuya Academy and she teaches Game Theory this semester.
Including Grammy herself, there are $$$n$$$ people in the class. Today, in order to attract students' interest, she decides to play a game with all students.
For each student, Grammy will pick an integer $$$x$$$ ($$$1 \leq x \leq 20)$$$. Without knowing what Grammy picks, the student will also pick another integer $$$y$$$ ($$$1 \leq y \leq 20)$$$. In the next step, Grammy calculate the score through the following procedure with each student independently.
- Grammy will give the student $$$x$$$ points.
- The student will give Grammy $$$y$$$ points.
- If Grammy's integer $$$x$$$ is strictly greater than $$$y$$$, then she will obtain $$$10$$$ extra points from the student.
- If Grammy's integer $$$x$$$ is strictly less than $$$y$$$, then she will give $$$10$$$ extra points to the student.
Now Grammy wants to know the expected amount of points she may win from all students if she chooses to pick the integer randomly and independently, which means for all integers in $$$[1,20]$$$, they all share the same possibility. Since students are very clever, you may assume that they will follow the optimal strategy in this game to maximize their final score.
Note that during the game, if one gives out points, he will lose the same amount of points. Moreover, the total point one obtains can be negative.
The input contains only a single case.
The only line of the input contains an integer $$$n$$$ ($$$1 \leq n \leq 1\,000$$$), indicating the total number of people in the class (Including Grammy).
Output the answer in one line. Your answer will be considered correct if and only if the absolute or relative error does not exceed $$$10^{-4}$$$.
1
0.0000