As we all know, the scoring rule for volleyball is as follows:
- A team wins when it reaches 25 points and leads the other team by 2 or more points. If the game ties at 24 points, it will continue until a team gains 2 or more points than the other team.
Wuye and Qingcheng meet again in the county's preliminary match. The rule of the match is best-of-three. Please be a scorer, output the score of each game, and at the end of the match, output which team wins.
Each line contains two integers $$$opt, x$$$. When $$$opt = 1$$$, it means Qingcheng scores $$$x$$$ balls consecutively, and when $$$opt=2$$$, it means Wuye scores $$$x$$$ balls consecutively.
When one of the teams wins the match, stop reading. The input guarantees that it describes a legitimate volleyball game, i.e., there will be no exception with regard to the score.
In the first $$$2$$$ or $$$3$$$ lines, output the score of each game. Qingcheng is in the front of Wuye.
At the end of the match, output another line. If Qingcheng wins the match, output $$$1$$$, otherwise output $$$2$$$.
2 25 1 24 1 1 2 24 1 24 2 1 1 1 2 1 2 1
0:25 25:0 25:27 2
1 25 2 25 1 2 1 1 2 3 1 3 1 1 1 3 2 3 1 1 1 2 2 3 1 3 2 2 1 3 2 4 1 3 2 1 2 4 2 1 2 3 1 2 2 2
25:0 0:25 24:26 2
Subtask 1 (50pts): It is guaranteed that $$$x=1$$$, that is, each line of input describes only one ball.
Subtask 2 (50pts): The number of input lines is guaranteed to be less than $$$1000$$$ lines. Scores are guaranteed to be within $$$1000$$$ at all times.
According to Wikipedia, Mahjong or mah-jongg is a tile-based game that was developed in the 19th century in China and has spread throughout the world since the early 20th century. It's a strategic game and the goal of the game is to draw tiles to form a legal hand with 14 tiles.
In the traditional game of Mahjong, there are many different types of tiles. For each type of tiles, there could be different symbols on it representing different numbers. For example, the graph below lists the same type of tiles, and they represent 1 to 9 respectively.
To simplify the game for this problem, we invent a generalized Mahjong. In our game, there is only one type of tiles, and the numbers on them are 1, 2, 3, ... to $$$n$$$. ($$$n$$$ could be larger than 9). For example, when $$$n = 6$$$, we have the following 6 tiles of the same type of tile.
In the generalized Mahjong, there can be an unlimited number of tiles for each symbol, and the number of tiles in each player's hands is unlimited as well. $$$x$$$ and $$$y$$$ will be given as input to define "Pong" and "Chow", in order to explain what is a legal hand.
- "Pong" means $$$x$$$ tiles of the same symbol (number) on them. For example, the picture below shows one case of "Pong" when $$$x = 3$$$, and when $$$x = 2$$$. They are 3 tiles of 3, and 2 tiles of 3.
- "Chow" means $$$y$$$ suited tiles in sequence. The picture below shows two cases when $$$y = 3$$$, and when $$$y = 2$$$, and one invalid "Chow" as well. The leftmost is (4, 5, 6), the middle is (7, 8), and the rightmost is (1, 9). The rightmost is not a valid "Chow".
A legal hand in the generalized Mahjong means that all tiles in one player's hands are a combination of "Pong"s and "Chow"s without any extra tiles.
The picture below shows a legal hand when $$$n = 9, x = 3$$$, and $$$y = 3$$$. This is also the first sample test case below.
The picture below shows how the hand of tiles can be divided into "Pong"s and "Chow"s. It's (1, 1, 1) "Pong", (9, 9, 9) "Pong", (1, 2, 3) "Chow", (4, 5, 6) "Chow", (6, 7, 8) "Chow".
Now given $$$n, x, y$$$, the modified rules explained above, and a hand of tiles, please print 'Yes' if it's a legal hand; otherwise please print out 'No'.
The first line contains three integers, representing $$$n$$$ ($$$1 \leq n \leq 10^3$$$), $$$x$$$, and $$$y$$$ ($$$1 \leq x, y \leq 10^9$$$).
The second line contains $$$n$$$ integers $$$a_1, \dots, a_n$$$, where $$$a_i$$$ is the number of the $$$i$$$th tile.
If the hand of tiles is legal, print Yes, otherwise print No.
9 3 3 4 1 1 1 1 2 1 1 3
Yes
9 3 4 2 1 0 2 2 2 0 1 2
No
Subtask 1 (40pts): $$$n=x=y=3$$$.
Subtask 2 (30pts): $$$y=n+1$$$.
Subtask 3 (30pts): No special restrictions.
For $$$100\%$$$ of data, $$$n \leq 1000$$$, $$$1 \leq x,y \leq 10^9$$$, $$$0 \le a_i \le 10^9$$$.
The law of twenty-eight (the Pareto law) is also known as the law of 80/20, and it is also called Barrett's law, Julen's law, the law of the critical minority, the law of the unimportant majority, the law of the least effort, the principle of imbalance. It is widely used in Sociology and business management. It was discovered by Pareto, an Italian economist in the late 19th and 20th centuries. He believes that in any set of things, the most important part only accounts for a small part of it, about $$$20 \%$$$ , and the remaining $$$80\%$$$, although in the majority, is secondary, so it is also known as the law of twenty-eight.
A popular example is that, the $$$80\%$$$ of the wealth in the world is owned by the $$$20\%$$$ of the people. Now I want you to write a program to check that, for a given set of bank accounts, whether the stored balances is strictly not weaker than the law of twenty-eight. The test method is to find two real numbers $$$A$$$, $$$B$$$, and the $$$A\%$$$ of the people own the $$$B\%$$$ of the wealth, and $$$B - A$$$ is maximized.
The first line contains an integer $$$n$$$, indicating that we have the stored balances of $$$n$$$ accounts.
The second line contains $$$n$$$ integers $$$a_1, \dots, a_n$$$, which respectively represents the stored balance of each account.
The first line contains two real numbers (the result is rounded to two decimal places), representing $$$A$$$, $$$B$$$ respectively.
If more than one pair of $$$(A, B)$$$ can maximize $$$B - A$$$, please output the answer with the largest $$$A$$$.
13 411 5622 3638 3411 5069 693 2738 3757 2496 2861 6761 355 1839
46.15 71.27
2 10 10
100.00 100.00
Subtask 1 (20pts): $$$1 \leq n \leq 20$$$
Subtask 2 (40pts): $$$1 \leq n \leq 1000$$$
Subtask 3 (40pts): $$$1\leq n\leq 10^5, 1 \leq a_i \leq 10^4$$$
For $$$100\%$$$ data, it's guaranteed that $$$1\leq n\leq 10^5, 1 \leq a_i \leq 10^4$$$
In the first set of examples, the stored balances of individuals $$$2, 3, 4, 5, 8, 11$$$ are $$$5622, 3638, 3411, 5069, 3757, 6761$$$, and their total balance is $$$28258$$$. The total balance of all people is $$$39651$$$. Therefore, these selected people, who have $$$28258/39651 \approx 71.27\%$$$ of the wealth, correspond to $$$6/13 \approx 46.15\%$$$ of all people.
In the second set of examples, there are three possible sets of $$$(A, B)$$$, namely $$$(0, 0), (50, 50), (100, 100)$$$: their corresponding $$$B - A$$$ are all $$$0$$$. Therefore, according to the problem statement, you need to output the answer with the largest $$$A$$$, namely $$$(100, 100)$$$.
A member of My Little Pony, Pony Yaya, is a pony who loves matrices. He has tried to combine matrices with many other OI techniques, and today he wants to combine matrices with $$$\mathbb{F}_2$$$.
Pony Yaya finds a $$$01$$$ matrix $$$L$$$ of $$$n \times n$$$, and initially, all entries of $$$L$$$ are $$$0$$$.
Pony Yaya wants to do something with it. Each operation selects a number $$$p \in [1,n]$$$, and then flips the numbers in the $$$p$$$-th row and $$$p$$$-th column of the matrix $$$L$$$ respectively ($$$0$$$ becomes $$$1$$$, $$$1$$$ becomes $$$0$$$). Note that $$$L_{p,p}$$$ will be flipped twice, so the value of $$$L_{p,p}$$$ will not change.
Pony Yaya has certain expectations for certain entried. Specifically, he will give a $$$01$$$ matrix $$$A$$$ of $$$n \times n$$$, if the position $$$(i, j)$$$ satisfies $$$A_{i,j} = 1$$$, it means that Pony Yaya hopes $$$L_{i,j} = 0$$$. Otherwise, it means that he has no demand for $$$L_{i,j}$$$.
Pony Yaya wants to make $$$L$$$ meet all his needs through several operations, but unfortunately, his matrix skills are not superb enough. So he finds you, hoping you can meet all his needs.
In order to let you show your advanced matrix skills, he also wants you to give a solution with the smallest number of operations, and in that premise, he also wants you to give the sequence of operations with the smallest lexicographical order.
Definition of lexicographical order: For two operation sequences $$$a, b$$$ of length $$$k$$$, lexicographical order $$$a \lt b$$$ if and only if $$$\exists \ i\in[1,k]$$$ satisfies $$$a_i \lt b_i$$$ and $$$\forall j \lt i, a_j = b_j$$$.
The first line contains a positive integer $$$n$$$.
For the second line to the $$$(n+1)$$$-th line, each line contains a $$$01$$$ string of length $$$n$$$. The $$$j$$$-th character in $$$i+1$$$-th line represents the value of $$$A_{i,j}$$$.
If no operation sequence can meet Pony Yaya's needs, output $$$-1$$$.
Otherwise, output two lines.
The first line contains an integer $$$k$$$, representing the minimum number of operations.
The second line contains a sequence $$$p_i$$$ of length $$$k$$$, represent the operation sequence. There is a space between every two adjacent integers.
You need to ensure that the lexicographical order of the $$$p$$$ sequence is minimum in the premise that $$$k$$$ is minimum.
4 0101 1010 0101 1010
2 1 3
6 011001 100011 100110 001000 011000 110000
-1
7 0110000 0000000 1000100 0100010 0000010 0001000 1000000
3 1 4 5
Subtask 1 (10pts): $$$n \le 4$$$.
Subtask 2 (20pts): $$$n \le 10$$$.
Subtask 2 (20pts): $$$n \le 500$$$.
Subtask 3 (50pts): No special restrictions.
For $$$100\%$$$ of data, $$$n \le 5000$$$.
Aliens have landed on earth, and you, who are studying OI, have received a problem about aliens.
You are given an array $$$a$$$ of $$$n$$$ positive integers numbered from $$$1$$$ to $$$n$$$, and a number $$$m$$$.
The value of a substring is the bitwise-OR of all its elements, minus $$$m$$$.
You want to divide the sequence into some substrings and minimize the sum of their values.
The input consists of multiple test cases. The first line contains a single integer $$$T$$$ ($$$1\le T\le 10^5$$$) — the number of test cases. Description of the test cases is as follows.
The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1\le n\le 10^5$$$, $$$0\le m\le 10^9$$$).
The second line of each test case contains the $$$n$$$ integers of the array $$$a_1,a_2,\cdots,a_n$$$ ($$$0\le a_i\le 10^9$$$).
It is guaranteed that the sum of $$$n$$$ over all test cases is not greater that $$$5\times 10^5$$$.
For each test case, print a single line with the minimum sum of values.
4 5 2 5 1 3 2 4 5 3 5 1 3 2 4 5 25 128 31 30 28 64 1 100 1
5 0 148 -99
Subtask 1 (13 pts): $$$m=0$$$
Subtask 2 (19 pts): $$$\sum n\leq 10^2$$$
Subtask 3 (28 pts): $$$\sum n\leq 10^3$$$
Subtask 4 (40 pts): No special restrictions
For $$$100\%$$$ data, it's guaranteed $$$1\le n,T\le 10^5$$$, $$$\sum n\leq 5\times 10^5$$$, $$$0\leq a_i,m\le 10^9$$$.
- An optimal way in first case: $$$\{5,1,3,2,4\}$$$.
- An optimal way in second case: $$$\{5\},\{1\},\{3\},\{2\},\{4\}$$$.
- An optimal way in third case: $$$\{128\},\{31,30,28\},\{64\}$$$.
- An optimal way in fourth case: $$$\{1\}$$$.
Notice that the answer could be negative.
Long time ago, there was a lamb who had a tree of $$$n$$$ vertices, indexed from $$$1$$$ to $$$n$$$, and the lamb liked it very much.
However, on a night of lightning and thunder, a Peng flew into the sky and summoned lightning which cut off several edges of the tree.
The angry lamb wanted to know the sum of the indices of the vertices that are the centroids of each connected component. If there were two centroids in one connected component, both of them would be considered by the sum. Because the lamb didn't know which edges are cut off, it wanted to know the sum of "the sum of the indices" for all $$$2^{n-1}$$$ possible cases.
On a tree of $$$n$$$ vertices, a vertex is a centroid if and only if after removing it from the tree, each connected component in the result includes at most $$$n/2$$$ vertices. It can be proven that each tree has at most two different centroids.
Because the answer can be extremely large, you just need to tell the answer modulo $$$998244353$$$.
The first line contains one integer $$$n$$$, representing the number of vertices in the tree.
For the following $$$n-1$$$ lines, each line contains two positive integers $$$u_i, v_i$$$, representing an edge $$$(u_i, v_i)$$$ on the tree.
One integer, representing the answer modulo $$$998244353$$$.
3 1 2 2 3
20
5 1 2 1 3 2 4 2 5
168
Subtask 1 (10pts): $$$n \le 15$$$.
Subtask 2 (30pts): $$$n \le 300$$$.
Subtask 3 (15pts): $$$n \le 1000$$$.
Subtask 4 (5pts): The $$$i$$$ edge satisfies $$$u_i=i,v_i=i+1$$$.
Subtask 5 (40pts): No special properties.
For $$$100\%$$$ of data, $$$n\leq 3000$$$ is guaranteed.
A member of My Little Pony, Pony Yaya, is a pony who loves polynomials. He once tried to combine polynomials with many other OI techniques, and today he wants to combine polynomials with strings.
Pony Yaya defines that, if an $$$n$$$-degree polynomial $$$F$$$ satisfies $$$[x^i]F(x)=[x^{n-i}]F(x)$$$ , then we will call it a palindromic polynomial, where $$$[x^i]F(x)$$$ represents the coefficient of the $$$i$$$-th degree of polynomial $$$F(x)$$$. In particular, the constants are also palindromic polynomials. Pony Yaya is surprised to find:
- The polynomial $$$H$$$ obtained by multiplying the palindromic polynomial $$$F$$$ and the palindromic polynomial $$$G$$$ is also a palindromic polynomial.
- The polynomial $$$H$$$ obtained by multiplying the palindromic polynomial $$$F$$$ and the non-palindromic polynomial $$$G$$$ is not a palindromic polynomial.
As a polynomial lover, Pony Yaya has collected a lot of polynomials, and he put $$$n$$$ $$$k_i$$$-degree polynomials $$$F_i(x)=\sum_{j=0}^{k_i}a_jx^j$$$ in a sequence. It is guaranteed that $$$a_{k_i} \ne 0$$$. He wants you to help him do some queries on this polynomial sequence.
Specifically, there are $$$q$$$ queries in the form of l r. You need to tell Pony Yaya whether the multiplication of polynomials in the interval $$$[l, r]$$$ is a palindromic polynomial.
The first line contains two integers $$$n, q$$$.
For the following $$$n$$$ lines, the first number of each line is an integer $$$k_i$$$, and the following $$$k_i$$$ integers are the coefficients $$$a_{j}$$$ of the $$$i$$$-th polynomial.
For the following $$$q$$$ lines, each line contains two integers $$$l, r$$$, representing the $$$q$$$-th query.
For each query, output $$$0$$$ if the result is not a palindromic polynomial, and $$$1$$$ otherwise.
4 4 2 1 2 1 1 1 3 3 2 4 4 2 1 3 1 1 3 1 2 2 4 3 4
0 0 1 0
Subtask 1 (13pts): $$$q,\sum k\le 500$$$ .
Subtask 2 (11pts): $$$q\le 10$$$ .
Subtask 3 (19pts): $$$k_i\le 1$$$ .
Subtask 4 (23pts): $$$k_i\le 3$$$ .
Subtask 5 (34pts): No special restrictions.
For $$$100\%$$$ data,it's guaranteed that $$$1\le n\le 10^5,1\le q\le 10^5,1\le x,l,r\le n,0\le a_i \lt 10^9,\sum k\le 5\times 10^5$$$ .
In 2202, the Coronavirus pandemic sweeps the country Y again. As a researcher in country Y, Dr. W hopes to find a way to fight the virus.
Dr. W has an experiment equipment, which consists of $$$n$$$ nodes and $$$n-1$$$ bidirectional pipes, the $$$i$$$-th pipe connects $$$u_i$$$, $$$v_i$$$. Any pair of nodes can reach each other through the pipe. Dr. W has four kinds of operating devices, which can perform one of the four operations of $$${\tt abcd}$$$ respectively. On each pipe, there is exactly one kind of operation that can be performed by the operating device. The operating device on the $$$i$$$-th pipe performs $$$c_i$$$ operation on the virus.
Dr. W will do experiments for $$$q$$$ times. In the $$$i$$$-th experiment, two nodes $$$s_i$$$, $$$t_i$$$ will be selected, and then Dr. W will put the virus into the node numbered $$$s_i$$$, let it reach the node numbered $$$t_i$$$ through the shortest path, and then take it out. Virus will be operated by the operating devices on the shortest path one by one.
Dr. W found that if a certain operation sequence is the same as the reverse of it, the virus may mutate uncontrollably after this operation. For example, a virus operated by $$${\tt a}$$$, $$${\tt abba}$$$ or $$${\tt cabac}$$$ is uncontrollable, while a virus operated by $$${\tt ab}$$$ or $$${\tt bba}$$$ are not. In particular, the initial virus without any operation is controllable.
In an experiment, if the virus is uncontrollable when it reaches a certain node $$$u$$$, the node $$$u$$$ is said to be dangerous. The risk level of an experiment is defined as the number of dangerous nodes on the path.
In order to estimate the risk of the experiments, Dr. W wants you to tell him the risk level of each experiment.
The first line contains two integers $$$n$$$ and $$$q$$$.
Next $$$n-1$$$ lines, each with two integers $$$u_i,v_i$$$ and a character $$$c_i$$$.
Next $$$q$$$ lines, each with two integers $$$s_i$$$ and $$$t_i$$$.
$$$q$$$ lines, each with an integer representing the risk level of an experiment.
7 5 1 2 a 2 3 a 3 4 a 2 5 b 1 6 b 6 7 a 2 7 4 7 3 6 6 3 4 1
2 3 2 1 3
12 12 1 2 a 2 3 b 3 4 a 4 5 b 5 6 b 6 7 a 7 8 b 8 9 a 9 10 b 10 11 a 11 12 b 1 12 2 12 3 12 4 12 5 12 6 12 7 12 8 12 9 12 10 12 11 12 12 12
3 3 2 2 4 3 3 2 2 1 1 0
Subtask 1 (5pts): $$$n,q \le 100$$$.
Subtask 2 (12pts): $$$n,q \le 2000$$$.
Subtask 3 (21pts): $$$n,q \le 40000$$$.
Subtask 4 (17pts): The tree is guaranteed to be a chain.
Subtask 5 (45pts): No special properties.
For $$$100\%$$$ data, $$$1\leq n,q\leq 10^5$$$, $$$1\leq u_i,v_i,s_i,t_i\leq n,c_i\in\{{\tt a},{\tt b},{\tt c},{\tt d}\}$$$.
Explanation of example $$$1$$$
The total operation sequences of the five experiments are: $$${\tt aba}, {\tt aaaba}, {\tt aab}, {\tt baa}, {\tt aaa}$$$.
Take the first experiment as an example:
After reaching the node $$$1$$$, the operation sequence is $$${\tt a}$$$, and after reaching the node $$$7$$$, the operation sequence is $$${\tt aba}$$$. These two operation sequences are the same as the reverse, so node $$$1$$$ and node $$$7$$$ are dangerous.
After reaching the node $$$2$$$, the operation sequence is $$${\tt ab}$$$, and the reverse is $$${\tt ba}$$$, which is different from the original sequence, so it is not dangerous.
There are a total of $$$2$$$ nodes that are dangerous, so the risk level for this experiment is $$$2$$$.