Cuber QQ has an Abstract algebra course this semester, and he has a problem in the latest problemset that he desperately needs your help.
Given $$$M=\{\begin{bmatrix} a & b\\ c & d \end{bmatrix}|a,b,c,d\in \mathbb{Z},ad-bc=1\}$$$ which is a multiplicative group. There is a nice property of this multiplicative group, that is, there are two generators $$$A=\begin{bmatrix} 1 & 1\\ 0 & 1 \end{bmatrix}$$$ and $$$B=\begin{bmatrix} 0 & 1\\ -1 & 0 \end{bmatrix}$$$, such that, $$$x\in M$$$ iff. $$$x=\prod _{i} x_i $$$ where $$$x_i\in \{A,B,A^{-1},B^{-1}\}$$$.
Now you are given an element $$$x\in M$$$, you need to find a sequence of $$$\{x_i\}$$$ such that $$$x=\prod _{i} x_i $$$ where $$$x_i\in \{A,B,A^{-1},B^{-1}\}$$$. To make your already-miserable life easier, it is guaranteed that there is at least one of $$$a$$$, $$$b$$$, $$$c$$$ and $$$d$$$ that equals to zero, i.e., $$$abcd=0$$$ for $$$x=\begin{bmatrix} a & b\\ c & d \end{bmatrix}$$$.
The first line contains a single integer $$$T$$$ ($$$1\le T\le 10$$$) — the number of test cases.
Each of the next $$$T$$$ lines contains four integers $$$a$$$, $$$b$$$, $$$c$$$ and $$$d$$$ ($$$-10^5\le a,b,c,d\le 10^5$$$, $$$ad-bc=1$$$, $$$abcd=0$$$), denoting $$$x=\begin{bmatrix} a & b\\ c & d \end{bmatrix}$$$.
For each test case, in the first line, please output one integer $$$m$$$ ($$$1 \le m \le 4$$$). In the following $$$m$$$ lines, each line contains one character $$$c_i$$$ and one integer $$$a_i$$$ ($$$c_i\in \{\text{'A'},\text{'B'}\},-10^5\le a_i\le 10^5$$$), such that $$$x=c_1^{a_1}c_2^{a_2}\cdots c_m^{a_m} = \prod _{i} c_i^{a_i}$$$.
In case of multiple solutions, please output any one.
We guarantee that there is always at least one solution.
3 1 1 0 1 -1 1 -1 0 -1 -1 0 -1
1 A 1 2 A 1 B 1 2 A 1 B 2
Cuber QQ has got a bracelet with countless number of pearls. Each pearl has a number written on it, and most remarkably, they are increasing integers counting from $$$1$$$. When you read the bracelet from beginning to end, it forms a large number. For example, assuming there are $$$11$$$ pearls on the bracelet, it reads "1234567891011". The market owner, however, is interested in whether a specific pattern exists in the bracelet. For example, "7891" exists in the bracelet above, but not "124", and neither "019".
Given a pattern $$$n$$$, please find the least number of pearls the bracelet needs to be equipped with before you can find the pattern on the bracelet.
The first line contains a single integer $$$T$$$ ($$$1\le T\le 10^5$$$) — the number of test cases.
Each of the next $$$T$$$ lines contains one integer $$$n$$$ ($$$1\le n\le 10^{18}$$$). It is guaranteed that $$$n$$$ does not have a leading zero.
For each test case, output one integer $$$m$$$, means the least number of pearls the bracelet needs.
3 5 45 32
5 5 24
On the evening of October 18 in 2020, the ceremony to launch the countdown to the 70th anniversary of East China Normal University was held on Zhongbei campus. The ceremony unveiled the logo for the celebration of the upcoming 70th anniversary of ECNU.
Designed by the School of Design, the logo, which is inspired by the pillars in front of the Qun Xian Tang, other landmark historic buildings of ECNU, and the architectural emblazonry and mortarboard sculpture in front of Li Ke San Guan, implies that ECNU, in its 69 years of development, has cultivated a galaxy of talents for the country.
The 70th anniversary of East China Normal University will hold on October 16 in 2021. To warmup for the grand anniversary event, we would like to initiate a countdown here and ask you to join us. It is April 10, 2021 today. We need your help to assist us in calibrating the timer so that it counts down to zero exactly on the big day.
The question is, how many days are there from today until the 70th anniversary?
This problem has no input.
Output one line contains an integer means the answer.
For example, if today is October 15, 2021. The answer is $$$1$$$.
Cuber QQ once said, when one integer is the divisor of another integer, it is the most wonderful thing in the world, because obviously not every integer divides one another.
You are given $$$a=\prod_{i=l_1}^{r_1}i$$$ and $$$b=\prod_{i=l_2}^{r_2}i$$$, and you should tell whether the "most wonderful thing in the world" will happen, i.e., whether $$$a$$$ is a divisor of $$$b$$$.
The first line contains an integer $$$T$$$ ($$$1\le T\le 10$$$), representing the number of test data.
One line for each test case, containing four space-separated integers $$$l_1, r_1, l_2, r_2 $$$ ($$$1 \le l_1 \le r_1 \le 10^7$$$, $$$1 \le l_2 \le r_2 \le 10^7$$$).
Output "Yes" if $$$\prod_{i=l_1}^{r_1}i$$$ is a divisor of $$$\prod_{i=l_2}^{r_2}i$$$, and "No" otherwise.
3 1 3 1 5 2 3 3 3 2 3 3 4
Yes No Yes
Cuber QQ know an Edge Game, in which two players move their tokens on edges alternatively. Specifically, the game starts with a fixed and given undirected tree. Player A and Player B each has a token on one node. They move in turn. In each step, the player moves his/her own token to a node adjacent to the current node located. Player A moves first. The player who first moves his/her token on the other's wins. Determine if A can win if each plays optimally.
In the first line there is one integer $$$n\;(2\le n\le 10^5)$$$, representing the number of nodes in the tree.
In each of the next $$$n-1$$$ lines are two integers $$$u,v\;(1\le u,v\le n,\; u\neq v)$$$ each, representing there is an edge between node $$$u$$$ and node $$$v$$$.
In the last line are two integers $$$a,b\;(1\le a,b\le n,\; a\neq b)$$$, representing the node A's token and B's token is on initially.
One line "Yes" or "No", denoting the winner.
3 1 2 1 3 1 3
Yes
3 1 2 1 3 2 3
No
Since Cuber QQ is a man of character, he himself prepared an interactive problem for this contest. The task is to guess a sequence based on the results of a specific function, called Function-Cuber.
To demonstrate how Function-Cuber works, let's assume that there is a sequence $$$a$$$ of length $$$n$$$. Function-Cuber $$$f_{cb}(a)$$$ is defined as sum of products of every pair of adjacent elements. i.e., $$$f_{cb}(a)=\sum_{i=1}^{n-1} a_ia_{i+1}$$$.
Though sequence $$$a$$$ is unknown, you can get of the output of $$$f_{cb}(a)$$$. However, as you probably have guessed, there are too many possibilities of $$$a$$$, and it is impossible to enumerate and check every of them.
Therefore, Cuber QQ defines another sequence transformation function $$$\text{M}(a,u,v)$$$ ($$$u\ne v$$$), that generates a sequence $$$a'$$$, which has the same length of $$$a$$$, and its values are:
$$$$$$ a'_i=\begin{cases} a_i+1 & i=u\\ a_i-1 & i=v\\ a_i & \text{Otherwise} \end{cases} $$$$$$
Note that this function will not actually change $$$a$$$. It will just generate another sequence $$$a'$$$.
Now Cuber QQ can answer you $$$f_{cb}(\textrm{M}(a, u, v))$$$ for any $$$u$$$ and $$$v$$$ you have given.
The interaction starts with reading two integers $$$n$$$ and $$$s$$$ ($$$2\le n\le 10^5,1\le s\le 10^9$$$) — denoting the length of $$$a$$$ and the value of $$$f_{cb}(a)$$$.
It is guaranteed that $$$1\le a_i\le 100$$$ and $$$n$$$ is even.
Then you can start interaction. You can make queries like:
- ? $$$u\quad v$$$ — The program will return the value of $$$f_{cb}(\text{M}(a,u,v))$$$. You should make sure $$$1\le u,v\le n,u\ne v$$$.
- ! $$$a_1\,a_2 \ldots a_n$$$ — The program will judge you output and finish interaction.
You can ask at most $$$n+25$$$ queries.
It is guaranteed that there is a unique solution to this problem.
After printing any query do not forget to print end of line and flush the output. Otherwise, you might get Idleness limit exceeded. To do this, use:
- fflush(stdout) or cout.flush() in C++;
- System.out.flush() in Java;
- flush(output) in Pascal;
- stdout.flush() in Python;
- see the documentation for other languages.
4 20 17 17
? 1 2 ? 2 3 ! 1 2 3 4
Note that the example interaction contains extra empty lines so that it's easier to read. The real interaction doesn't contain any empty lines and you shouldn't print any extra empty lines as well.
Cuber QQ likes QQ Speed, he always plays the game throughout all night, until early morning.
On a dark and gusty night, as usual, Cuber QQ was playing the $$$48$$$-player knockout round of QQ Speed, and it was his turn to "ban the map". He suddenly had an idea for the programming contest.
In each contest round, there are $$$n$$$ players. The gaming system will give all players $$$x$$$ maps, and each player can ban a map. After that, the gaming system will evenly, but not necessarily randomly, divide the players into $$$m$$$ groups ($$$m$$$ divides $$$n$$$). Every player in the same group must race on the same map, and different groups can either race on the same map or not. If one of the players in the group have banned a map, this map cannot be used by this group any more. Now, Cuber QQ wants to know the minimal number of maps the gaming system needs to provide to the players, and these maps can ensure having at least one grouping scheme in any case.
The first line contains a single integer $$$T$$$ ($$$1\le T\le 10^5$$$) — the number of test cases.
Each of the next $$$T$$$ lines contains two integers $$$n$$$ and $$$m$$$ ($$$1\le n,m\le 10^9,m\mid n$$$).
For each test case, output one line containing one integer which is the answer.
2 48 8 4 2
3 3
"Largest Rectangle in Histogram" problem is a classic problem. You are given an array of integers $$$arr$$$ where each element represents the height of a bar in a histogram. A histogram is a graphical display of data using bars of different heights. The bars are placed in the exact same sequence as given in the array, and each of them has width $$$1$$$. You need to find the area of the largest rectangle in the histogram.
But now, Cuber QQ wants to generalize this problem to three-dimensional case: Given an array of pairs, each of which represents a bar's depth and height. The bars have their front side aligned and each of them has width $$$1$$$. Please find the largest volume of the sub-cuboid in the 3D-histogram.
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2\cdot 10^5$$$), the number of blocks.
The next $$$n$$$ lines each contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i,y_i \le 10^6$$$), the $$$i$$$-th block's depth and height.
The output is a single integer in one single line, the largest volume.
3 1 1 3 3 2 2
9
5 4 3 5 6 2 4 1 5 3 2
30
The figure shows the 3D-histogram for the first sample.
Once upon a time, Quber CC wrote a letter to Cuber QQ. But unfortunately, due to the poor network condition, the sweet sentences had become completely a mess when Cuber QQ finally received them. However, Cuber QQ did not give up. He was going to remove some substrings from the sentence to make it reasonable.
For example, Cuber QQ received a sentence "inotloveyourpet". In his mind, it must be "iloveyou". It is possible to make the sentence "inotloveyourpet" to "iloveyou" by removing the substrings "not" and "rpet".
Since the letter was too long, it might be quite difficult to figure out its true meaning. So Cuber QQ will tell you the sentence he received and the sentence in his mind and ask you whether it is possible to change the received sentence to the expected one by removing some substrings from it.
The input contains two lines.
In the first line, a string $$$s$$$ ($$$ 1 \le |s| \le 100 $$$) consisting of only lower case letters, representing the sentence which Cuber QQ received.
In the second line, a string $$$t$$$ ($$$1 \le |t| \le |s| $$$) consisting of only lower case letters, representing the sentence in Cuber QQ's mind.
Output "Yes" if you can change $$$s$$$ to $$$t$$$ by removing some substrings. Otherwise please output "No".
inotloveyourpet iloveyou
Yes
inotloveyourpet iloveyourcat
No
Recently, a reality TV show called "Just the Chosen One" is becoming popular around the world. In the show, $$$n$$$ players get involved in a fierce competition for fabulous rewards sponsored by TuSimple, a world-famous company advancing in auto pilot technologies for logistic systems. Surprisingly however, the players compete with neither talent nor skill, but fortune.
Before the game starts, the $$$n$$$ players are ranked according to the Dow Jones Industrial Indexes (DJI, which reflects stock trends in the United States) when they were born (You can assume that their birthday DJIs are pairwise different). Initially, $$$n$$$ balls with the same shape, weight and temperature are put in a nontransparent black box, numbered in $$$1,2,\dots,n$$$。
Next, $$$n$$$ rounds will be carried out. In the $$$i$$$-th round:
- The player with DJI-rank $$$i$$$ randomly chooses a ball from the box, and does not put it back;
- All the players with balls will be ranked by the numbers on their balls, and players who have got the largest $$$m$$$ balls will get an AMAZING GIFT. If less than $$$m$$$ players have balls (i.e., less than $$$i$$$ rounds have been carried out), all the players who have got a ball will get an AMAZING GIFT. In other words, in the $$$i$$$-th round, $$$\min(i,m)$$$ players will get a gift.
Today, Cuber QQ finally gets a chance to prove that he is just "the Chosen One" — he was invited to participate in "Just the Chosen One"! Now Cuber QQ knows that he is ranked $$$k$$$ among all the competitors according to their birthday DJIs. He is wondering that what is the expected number of gifts that he will get.
Three space-separated integers — $$$n,m,k$$$ ($$$1\le n,m,k \le 10^9$$$) in a line, representing the number of players, the maximum number of chosen ones in each round, and the rank of Cuber QQ.
One line, containing a real number which represent the expected number of gifts that Cuber QQ will get. Your answer will be regarded as correct, if and only if the relative or absolute error is less than $$$10^{-6}$$$.
5 2 5
0.40000000
Given $$$l$$$ and $$$k$$$, Cuber QQ wants you to answer if there are more than $$$k$$$ primes (i.e., at least $$$k+1$$$ primes) in $$$[l,l+2k)$$$.
One line with two space-separated integers $$$l,k\;(1\le l,k\le 10^8)$$$.
One line with "Yes" or "No".
3 3
No
2 1
Yes