Chipmunk is a math genius, and he is extraordinarily good at calculus.
Now Chipmunk gives you a formula and asks you to calculate it in one minute, or you should treat him to dinner. The formula looks like this: $$$$$$ \int_0^{2\pi}\frac{\text{d}x}{(1+\sin^2x)\sqrt{2-\sin^2x}} $$$$$$
Obviously it is impossible to get the accurate answer, so Chipmunk only requires you to tell him the integer part of it.
It can be anything, and has nothing to do with the answer.
Print an integer $$$n\ (1\le n\le 5)$$$, representing the answer to the problem above.
The probability that Awson is god
1
Of course Chipmunk will not tell you the correct answer in the example above!
The Rule 110 cellular automaton (often called simply Rule 110) is an elementary cellular automaton with interesting behavior on the boundary between stability and chaos. In this respect, it is similar to Conway's Game of Life. Like Life, Rule 110 is known to be Turing complete. This implies that, in principle, any calculation or computer program can be simulated using this automaton.
The Rule 110 is famous for its interesting properties. Among the 88 possible unique elementary cellular automata, Rule 110 is the only one for which Turing completeness has been proven, although proofs for several similar rules should follow as simple corollaries (e.g. Rule 124, which is the horizontal reflection of Rule 110). Rule 110 is arguably the simplest known Turing complete system.
This paragraph will introduce how Rule 110 works. When applying Rule 110 to a pattern, whether each point in the pattern will be 0 or 1 in the new generation depends on its current value, and on the values of its two neighbors. If a point is at the left/right border, then the left/right neighbor of it will be considered as 0. The rules are as follows:
| Current pattern | 000 | 001 | 010 | 011 | 100 | 101 | 110 | 111 |
| New state for center cell | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 0 |
Chipmunk is interested in the automaton but he is not clever enough to solve it quickly. Now Chipmunk gives you the initial pattern, and you need to apply Rule 110 to the pattern once and output the result.
The first line contains an integer $$$n\ (1\le n\le 10^5)$$$, the length of the pattern.
The next line is a string of length $$$n$$$ consisting of only 0s and 1s, representing the initial pattern.
Output a string of length $$$n$$$, the pattern after applying Rule 110.
The problem contains several subtasks. You can get the corresponding score for each passed test case.
- Subtask 1 ($$$40$$$ points): $$$n\le 1000$$$.
- Subtask 2 ($$$60$$$ points): no additional constraints.
1 1
1
8 00111010
01101110
In the first example, there is an only 1 in the initial pattern. The two neighbors of it are both 0, which satisfies pattern 010. According to the table above, the value of the point will stay at 1.
The game Tic-Tac-toe is played by two people taking turns on a $$$3 \times 3$$$ board, with the person winning the game when his first getting a whole horizontal or vertical or diagonal line filled with his tokens. It's easy to find that there are only $$$8$$$ ways of putting tokens to win the game (only considering the tokens in the key line).
All $$$8$$$ winning ways are shown in the picture below.
Today, Walk_alone is bored with playing the 2D Tic-Tac-Toe with Salix Leaf! He thinks the board is too small and the winning ways are too monotonous. So they decide to make a larger chess board and add a brand new dimension to the game! Now this game seems more interesting:
In a 3D $$$n \times n \times n$$$ cube, two people put their tokens by turn, and the first one whose tokens fill one horizontal or vertical or diagonal line of the cube wins the game. For instance, some winning ways in a 3D $$$4 \times 4 \times 4$$$ cube are shown in the picture below.
He is too lazy to do any calculation, so he wants you to tell him the number of ways to put the tokens in a line.
The first and the only line of the input contains an integer $$$n\ (2 \leq n \leq 1000)$$$.
Print only one number representing the number of ways to put the tokens in a line.
The problem contains $$$20$$$ test cases. You can get $$$5$$$ points for each passed test case.
2
28
3
49
4
76
After math class, Teacher Awson gave Sinoey $$$n$$$ tasks as his homework, the $$$i$$$-th of which is to calculate the sum of $$$3$$$ consecutive integers starting from $$$i-1$$$, i.e. $$$(i-1)+i+(i+1)$$$. Note that he does not need to calculate $$$i-1$$$ or $$$i+1$$$.
It is a big problem for Sinoey because he does not want to carry even once! For two numbers represented as $$$\overline{x_n\dots x_2x_1}$$$ and $$$\overline{y_n\dots y_2y_1}$$$, carrying means there exists an integer $$$i\ (1\le i\le n)$$$ such that $$$x_i+y_i\ge 10$$$. Take the $$$4$$$th task, $$$3+4+5$$$ as an example. Since $$$3+4+5 \gt 10$$$, Sinoey will have to minus the first digit by $$$10$$$ and add $$$1$$$ to the next digit in order to get the correct answer.
Carrying is awful, and Sinoey decides to do only the tasks that do not require carrying. Now you need to tell him the number of tasks he will do.
The only line of the input contains an integer $$$n\ (1\le n\le 10^{18})$$$, the total number of tasks.
Print an integer representing the number of tasks Sinoey decides to do.
The problem contains several subtasks. You can get the corresponding score for each passed test case.
- Subtask 1 ($$$30$$$ points): $$$n\le 10^6$$$.
- Subtask 2 ($$$30$$$ points): $$$n\le 10^{10}$$$.
- Subtask 3 ($$$40$$$ points): no additional constraints.
12
5
141214
1536
In the first example, task $$$1,2,3,11$$$ and $$$12$$$ are easy.
Yjmeimei likes game theory, but she is not smart enough to solve any related problem.
Now Zygege gives her a new problem.
There are $$$n$$$ piles of stones. Alice and Bob take turns removing them. On Alice's turn, she can remove an arbitrary number of stones (at least one) from a single pile. On Bob's turn, he can remove some stones from a single pile, and the number of stones he chooses should not be less than the number of stones Alice has removed in total. Alice plays first, and the player who cannot make a move loses.
Now Yjmeimei needs to figure out who will win the game if both Alice and Bob play the game optimally. Of course it is still too hard for her, so she asks you for help.
Since the problem is a bit like Nim, Yjmeimei names it "Do Not Play Nim".
The input contains several test cases.
The first line of the input contains an integer $$$T\ (1\le T\le 10)$$$, the number of test cases.
For each test case, the first line contains an integer $$$n\ (1\le n\le 2\cdot 10^5)$$$ indicating the number of piles of stones. The second line of contains $$$n$$$ integers. The $$$i$$$-th integer $$$a_i\ (1\le a_i\le 10^9)$$$ represents the number of stones in the $$$i$$$-th pile.
It is guaranteed that the sum of $$$n$$$ in all test cases does not exceed $$$2\cdot 10^5$$$.
For each test case, print "Alice" or "Bob" (without quotes) in one line indicating the winner. If the result is not deterministic, print "Awson is God!".
The problem contains several subtasks. You can get the corresponding score for each passed test case.
- Subtask 1 ($$$20$$$ points): $$$n\le 2$$$.
- Subtask 2 ($$$80$$$ points): no additional constraints.
311021 161 1 4 5 1 4
Alice Bob Alice
In the first case, Alice can take $$$6$$$ stones, and it will be impossible for Bob to take no less than $$$6$$$ stones, so Alice wins.
In the second case, Alice will remove the first pile, and Bob will remove the second pile. Alice cannot move after that for all stones are removed, so Bob wins.
The third case is too smelly for Yjmeimei to elaborate on!
Awson loves chipmunks, especially the $$$k$$$-th one among all $$$n$$$ chipmunks! He wants to keep a consecutive interval of chipmunks in his home, and the interval should include the $$$k$$$-th chipmunk.
However, chipmunks eat a lot and it is a heavy burden for Awson to buy food for all chipmunks. Specifically, the $$$i$$$-th chipmunk has a hunger value $$$a_i$$$. If Awson decides to raise the chipmunks from index $$$l$$$ to $$$r\ (1\le l\le k\le r\le n)$$$, then the burden brought to Awson will be $$$f(l,r)=\sum_{l\le i\le r} a_i$$$.
Awson does not want to worry too much about chipmunks' food, so he will choose the interval with the $$$m$$$-th smallest burden. Now you are required to tell Awson the burden he will carry.
The first line contains three integers $$$n\ (1\le n\le 10^6)$$$, $$$k\ (1\le k\le n)$$$ and $$$m\ (1\le m\le k\,(n-k+1))$$$ as described above.
The second line contains $$$n$$$ integers. The $$$i$$$-th integer $$$a_i\ (|a_i|\le 10^9)$$$ represents the hunger value of the $$$i$$$-th chipmunk.
Print an integer representing the $$$m$$$-th smallest burden.
The problem contains several subtasks. You can get the corresponding score for each passed test case.
- Subtask 1 ($$$30$$$ points): $$$n\le 10^3$$$.
- Subtask 2 ($$$70$$$ points): no additional constraints.
4 2 3 1 2 4 8
6
4 2 2 -1 2 -4 8
-2
In the first example, the second chipmunk must be chosen, and there are $$$6$$$ ways to choose the interval in total. They are $$$f(2,2)=2,$$$ $$$f(1,2)=3,$$$ $$$f(2,3)=6,$$$ $$$f(1,3)=7,$$$ $$$f(2,4)=14,$$$ and $$$f(1,4)=15$$$. Among them, $$$f(2,3)=6$$$ is the third smallest, so the answer is $$$6$$$.
There are $$$n$$$ chipmunks standing in a row. The height of the $$$i$$$-th one is indicated as $$$h_i\ (1\le i\le n)$$$. It is guaranteed that array $$$h$$$ is a permutation of length $$$n$$$. Recall that a permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order.
Awson wants to sort the chipmunks by height in increasing order. Each time he can select the $$$i$$$-th and the $$$j$$$-th chipmunk satisfying $$$i \lt j$$$ and $$$h_i \gt h_j$$$, and swap them. He will keep doing that until all chipmunks are sorted.
Awson also noticed that when swaping two chipmunks, each chipmunk whose position and height are both between them will get $$$a$$$ happiness. Formally speaking, for all integers $$$k\in(i,j)$$$, the happiness of the $$$k$$$-th chipmunk will increase by $$$a$$$ if and only if $$$h_i \gt h_k \gt h_j$$$. Note that $$$a$$$ can be negative.
Awson wants to maximize the total happiness of all chipmunks. Can you tell him the maximum happiness he can get if he swaps optimally?
The first line contains two integers $$$n\ (1\le n\le 2\cdot 10^5)$$$ and $$$a\ (a\in\{-1,1\})$$$, as described above.
The next line contains $$$n$$$ integers separated by spaces, the $$$i$$$-th of which indicates the height of the $$$i$$$-th chipmunk $$$h_i\ (1\le h_i\le n)$$$.
Print an integer representing the maximum sum of happiness of all chipmunks.
The problem contains several subtasks. You can get the corresponding score for each passed test case.
- Subtask 1 ($$$20$$$ points): $$$a=-1$$$.
- Subtask 2 ($$$40$$$ points): $$$a=1$$$ and $$$n\le 5\cdot 10^3$$$.
- Subtask 3 ($$$40$$$ points): no additional constraints.
3 1 1 2 3
0
5 -1 5 2 3 4 1
0
6 1 6 5 1 4 2 3
4
In the first example, the chipmunks are already sorted. No happiness is gained, so the answer is $$$0$$$.
In the second example, it would better not swap the the first and the last chipmunk, or the chipmunks in the middle would be unhappy.
In the third example, one of the best strategies is as follows (the swapped two are marked bold, and chipmunks that can get happiness are underlined):
$$$$$$ [6,\color{red}{\textbf{5}},1,\underline{4},\color{red}{\textbf{2}},3] \rightarrow [\color{red}{\textbf{6}},2,1,\underline{4},\underline{5},\color{red}{\textbf{3}}] \rightarrow [\color{red}{\textbf{3}},\underline{2},\color{red}{\textbf{1}},4,5,6] \rightarrow [1,2,3,4,5,6] $$$$$$
At last, the $$$6$$$ chipmunks get $$$0,1,0,2,1,0$$$ happiness respectively, so the total happiness is $$$4$$$.
Awson is our god, so sometimes we call him AoShen.
AoShen has $$$n$$$ fans, and each of them has a favourite number. They all know the favourite numbers of the others.
One day, AoShen asks his fans to play a game. Each person must tell AoShen the number of different favorite numbers among other fans'. Formally speaking, if the $$$j$$$-th fan's favorite number is $$$v_j$$$, then the $$$i$$$-th fan will tell AoShen the number of different elements in $$$\{v_j\mid 1\le j\le n,\, j\neq i\}$$$.
Take Walk_alone, Yzyyylx, Sinoey and Weierstras, who likes $$$5,5,14,114514$$$, respectively, as an example. The numbers they tell AoShen will be $$$3,3,2,2$$$.
However, some of them may cheat. For instance, if there are $$$3$$$ people and the numbers they tell AoShen are $$$1,2,100$$$, then obviously, AoShen is cheated. But AoShen may not be cheated if they tell him $$$1,2,2$$$, for it is possible that the first one likes $$$100$$$, and the rest of them like $$$200$$$.
AoShen hates cheaters, so he asks you to tell him the minimum number of people who are cheating.
The input contains several test cases.
The first line of the input contains an integer $$$T\ (1\le T\le 10)$$$, the number of test cases.
For each test case, the first line contains an integer $$$n\ (2\le n\le 10^5)$$$, the number of fans.
The second line contains $$$n$$$ integers. The $$$i$$$-th integer $$$a_i\ (1\le a_i\le 10^5)$$$ indicates the number that the $$$i$$$-th fan tells AoShen.
It is guaranteed that the sum of $$$n$$$ in all test cases does not exceed $$$10^5$$$.
Print a single number indicating the minimum number of cheaters.
The problem contains several subtasks. You can get the corresponding score for each passed test case.
- Subtask 1 ($$$50$$$ points): there is at most one cheater.
- Subtask 2 ($$$50$$$ points): no additional constraints.
331 2 10043 3 3 351 2 3 4 5
1 0 3
In the first case, the third fans must be cheating.
In the second case, no one is cheating when all fans' favorite numbers are distinct.
In the third case, at least $$$3$$$ fans are cheating. When their favorite numbers are $$$1,3,1,2,2$$$, the numbers they tell AoShen should be $$$3,2,3,3,3$$$.
Walk Alone has just met a cute girl, Salix Leaf. Her birthday is coming, so Walk Alone decides to buy a bipartite graph with $$$n+m$$$ nodes. $$$m$$$ nodes for her, and the rest $$$n$$$ for himself. On each node there is a number, and there are $$$e$$$ edges connecting the two sides.
Walk Alone is curious about the graph, and he wants to find out some features of the graph so that he can tease Salix when meeting her the next time.
Specifically, Walk Alone will ask her $$$q$$$ questions. In each question, Walk Alone will give her a number $$$x$$$, and ask her to tell him the number of ways to choose a subset of nodes from the graph such that
- The xor sum of nodes she chooses is $$$x$$$.
- It is possible to choose some edges from the graph, so that each node in the graph is covered by at most one edge, and each node in the subset is be covered by exactly one edge.
Since the answer is very large, Walk Alone only requires the answer modulo $$$998\,244\,353$$$.
It is too hard for Salix to solve the questions herself. As her best friend, can you help her with the questions?
The first line contains three integers, $$$n\ (1\le n\le 20)$$$, $$$m\ (1\le m\le 20)$$$, and $$$e\ (1\le e\le n\cdot m)$$$.
The second line contains $$$n$$$ integers, the $$$i$$$-th number $$$a_i\ (0\le a_i \lt 2^{18})$$$ represents the number on the $$$i$$$-th node of Walk Alone's.
The third line contains $$$m$$$ integers, the $$$i$$$-th number $$$b_i\ (0\le b_i \lt 2^{18})$$$ represents the number on the $$$i$$$-th node of Salix's.
The next $$$e$$$ lines describe the edges in the graph. Each line contains two integers $$$u\ (1\le u\le n)$$$ and $$$v\ (1\le v\le m)$$$, indicating an edge between the $$$u$$$-th node of Walk Alone's and the $$$v$$$-th node of Salix's. It is guaranteed that there are no multiple edges.
The next line contains an integer $$$q\ (1\le q\le 10^5)$$$, and each of the next $$$q$$$ lines contains an integer $$$x\ (0\le x \lt 2^{18})$$$ indicating a question.
For each query, output a number in a line representing the answer.
3 2 4 1 2 3 4 5 1 1 1 2 2 1 3 2 3 0 1 7
3 3 4
The graph in the example is shown in the picture below (we label the nodes owned by Walk Alone and Salix as $$$A_1,A_2,A_3$$$ and $$$B_1,B_2$$$ respectively).
In the first query, the sets with xor sum equal to $$$0$$$ are $$$\varnothing,\{A_1,B_1,B_2\},\{A_2,A_3,B_1,B_2\}$$$. All these sets are valid. For the second set, we can choose $$$2$$$ edges, $$$(A_1,B_1)$$$ and $$$(A_3,B_2)$$$. For the last set, we can choose $$$(A_2,B_1)$$$ and $$$(A_3,B_2)$$$.
In the second query, the sets with xor sum equal to $$$1$$$ are $$$\{A_1\},\{A_2,A_3\},\{B_1,B_2\},\{A_1,A_2,A_3,B_1,B_2\}$$$. For the last set, it can be proved that choosing a valid set that can cover all nodes exactly once is impossible, so there are only $$$3$$$ valid sets in total.
After data structure class in Sinoey's dream, Awson gave Sinoey a simple segment operation problem as his homework. Sinoey has $$$5$$$ hours to solve it before he wakes up.
There is a set $$$S$$$ containing all integers. Initially, the value of each element in $$$S$$$ is $$$0$$$. In this problem, Sinoey is given an integer sequence $$$a$$$ of length $$$n$$$, the $$$i$$$-th element of which is $$$a_i$$$, and he has to do the following two types of operations:
- R l r w. Let $$$T=\{a_i\mid l\le i\le r\}$$$. For each element $$$x$$$ in $$$T$$$, add $$$S_x$$$ by $$$w$$$. $$$(1\le l\le r\le n,\ |w| \lt 2^{31})$$$
- A x. Output the value of $$$x$$$ in $$$S$$$. $$$(|x| \lt 2^{31})$$$
The first line contains two integers $$$n\ (1\le n\le 10^5)$$$ and $$$q\ (1\le q\le 10^5)$$$, the length of sequence and the number of operations respectively.
The next line contains $$$n$$$ integers representing the sequence. For each element $$$a_i$$$ in the sequence, $$$|a_i| \lt 2^{31}$$$ is guaranteed.
Each of the next $$$q$$$ lines indicates an operation. The formats and constraints are introduced above.
For each query, print the answer in a line.
The problem contains several subtasks. You can get the corresponding score only if you have passed all test cases in a subtask.
- Subtask 1 ($$$20$$$ points): $$$n\le 100$$$.
- Subtask 2 ($$$80$$$ points): no additional constraints.
4 5 1 2 1 3 R 1 3 1 A 1 R 2 4 1 A 1 A 3
1 2 1
The interval in the first operation contains two different elements: $$$1$$$ and $$$2$$$, so $$$S_1$$$ and $$$S_2$$$ will increase by one after the first operation.
There are $$$n$$$ invervals, the $$$i$$$-th of which is $$$[l_i,r_i]$$$. We define the length covered by it as $$$r_i − l_i$$$.
Define the beauty of $$$[x, y]$$$ as the length covered by $$$\bigcup_{i=x}^y [l_i,r_i]$$$.
Now you are given m queries. For each query $$$[A,B]$$$, you need to find the expected beauty of $$$[x,y]$$$, where $$$[x,y]$$$ is uniformly sampled from all possible integer pairs such that $$$A \leq x \leq y \leq B$$$.
Find the answers modulo $$$998\ 244\ 353$$$.
The first line contains two integers $$$n$$$ ($$$1 \leq n \leq 2\cdot 10^5$$$) and $$$m$$$ ($$$1 \leq m \leq 2 \cdot 10^5$$$), the number of intervals and queries, respectively.
The following $$$n$$$ lines describe the intervals. The $$$i$$$-th line contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$0 \leq l_i \lt r_i \leq 10^8$$$).
The next $$$m$$$ lines describe the queries. The $$$i$$$-th line contains two integers $$$A_i$$$ and $$$B_i$$$ ($$$1 \leq A_i \leq B_i \leq n$$$)
For each query, print the answer in a line.
3 3 1 3 2 5 6 7 1 1 1 2 2 3
2 3 665496238
In the example above, there are $$$3$$$ intervals, $$$[1,3]$$$, $$$[2,5]$$$ and $$$[6,7]$$$.
In the first query, $$$x = y = 1$$$, so the answer is the beauty of $$$[1,1]$$$, equal to $$$3 − 1 = 2$$$.
In the second query, $$$[x,y]$$$ is randomly distributed in $$$\{[1,1],[1,2],[2,2]\}$$$. The beauty of them are $$$2$$$, $$$4$$$ and $$$3$$$, respectively, so the answer is $$$(2 + 4 + 3)/3 = 3$$$.
The answer to the third query is $$$(3 + 1 + 4)/3 = 8/3$$$.