Given a sequence $$$a$$$ consists $$$n$$$ distinct integers. Please construct a permutation $$$p$$$ and a sequence $$$b$$$ satisfied:
- Both $$$p$$$ and $$$b$$$ have exactly $$$n$$$ elements;
- For every $$$i \in [2,n]$$$ ,there exist an indice $$$j(1 \leq j \leq i-1)$$$ such that $$$b_i \oplus p_j=0$$$.
You need to minimize $$$\sum\limits_{i=2}^n popcount(a[p[i]] \oplus a[b[i]])$$$, where $$$popcount(x)$$$ represents the number of $$$1$$$ in the binary representation of $$$x$$$, $$$\oplus$$$ means bitwise exclusive OR operation.
The input consists of multiple test cases.
The first line contains an integer $$$T$$$ $$$(1 \leq T \leq 10)$$$ — the number of test cases. The description of the test cases follows.
The first line contains one integers $$$n$$$ $$$(1 \leq n \leq 2*10^5)$$$ .
The second line contains $$$n$$$ distinct integers $$$a_1,a_2,\dots,a_n(0 \leq a_i \lt 2^{18})$$$ .
For each test case, print three lines.
The first line contains one number, represents the minimum value.
The second line contains $$$n$$$ numbers $$$p_1,p_2,\dots,p_n$$$ — the permutation you construct.
The last line contains $$$n$$$ numbers $$$b_1,b_2,\dots,b_n$$$ — the sequence you construct.
If there are several answers, you can print any.
2 3 2 3 4 4 65 23 11 43
3 1 2 3 3 1 1 7 1 3 4 2 4 1 3 3
A school has a total of $$$3*n$$$ students, divided evenly into $$$A$$$ group, $$$B$$$ group or $$$C$$$ group, with $$$n$$$ in each group. Everyone has an ability value $$$v_i$$$, the tacit value between two students is $$$f(i,j)=(v_i+v_j)*(v_i \oplus v_j) \% M$$$, where $$$\oplus$$$ means bitwise exclusive OR operation. As the competition coach of this school, you need to select exactly $$$m$$$ teams to participate in the $$$CCPC$$$ competition in the second half of the year.
Specifically, Each team contains exactly three students, and the three students are from different groups. Let the team members from the $$$A,B,C$$$ group be $$$a,b,c$$$, then the tacit value of this team is $$$f(a,b)+f(a,c)$$$.
Please find out the maximum sum of the tacit values of the $$$m$$$ teams.
The input consists of multiple test cases.
The first line contains an integer $$$T$$$ $$$(1 \leq T \leq 10)$$$ — the number of test cases. The description of the test cases follows.
The first line contains three integers $$$n,m,M$$$ $$$(1 \leq m \leq n \leq 200,10 \leq M \leq 2000)$$$.
Then follows three lines, each line contains $$$n$$$ integers $$$v_1,v_2,\dots,v_n$$$ $$$(1 \leq v_i \leq 2000)$$$ — the ability value of each student in group $$$A,B$$$ and $$$C$$$ .
For each test case, print the answer.
2 3 2 10 1 2 3 4 5 6 7 8 9 4 4 21 5 4 2 6 9 1 10 2 4 3 99 12
27 98
Define function $$$f(x)= \prod \limits_{i=1}^{len} (x\%10^i)\%(x+1)$$$, where $$$len$$$ represents the digit length of $$$x$$$.
For example, $$$f(1023)=(3*23*23*1023)\%1024$$$.
Define function $$$g(n,m)= \begin{cases} f(g(n,m-1))& {m \gt 1}\\ f(n)& {m=1} \end{cases}$$$. For example, $$$g(n,2)=f(f(n))$$$.
You are given $$$n$$$ and $$$m$$$, please calculate $$$\sum\limits_{i=1}^m g(n,i)$$$.
The input consists of multiple test cases.
The first line contains an integer $$$T$$$ $$$(1 \leq T \leq 20)$$$ — the number of test cases. The description of the test cases follows.
The only line contains two integers $$$n,m$$$ $$$(1 \leq n,m \leq 10^9)$$$ .
For each test case, print the answer.
2 3 4 4102 642
12 21262
$$$\textit{Fall Guys}$$$ is a recently popular game. There are at most 60 players participating in a game and only one player will win finally after passing through one level after another.
$$$\textit{Fall Guys}$$$ has a level named climbing competition. Players will reach the destination after crossing many obstacles. After reaching the destination, they have to grab the crown to be the winner. But the crown moves up and down, and the player can catch it when the crown is below $$$h$$$ m.
Now, there are $$$n$$$ players participating in the climbing competition level. The height of the crown is $$$0$$$ at the beginning of the game, and then the crown will move up at a speed of $$$1$$$ m/s. When the height increases to $$$H$$$ m, the crown will immediately move down at a speed of $$$1$$$ m/s until the height decreases to $$$0$$$, and then move up and move down repeatedly.
The time that the $$$i$$$-th player reaches the destination is $$$x_i$$$. When a player reaches the destination, if the height of the crown is greater than $$$h$$$ m he will wait in place, otherwise he will immediately jump and grab the crown. However, each player has a delay time $$$c_i$$$ because of the bad network. Assuming that a player grab the crown at the moment of $$$t$$$ s, the system will determine that the moment he grab the crown is $$$(t+c_i)$$$ s.
The first player who grab the crown will win. If multiple players grab the crown at the same time, the winner is the player with the lower number.
You are given the arrival time $$$x_i$$$ and the delay time $$$c_i$$$ of all players, please calculate who will be the final winner.
The input consists of multiple test cases.
The first line contains an integer $$$T$$$ $$$(1 \leq T \leq 20)$$$ — the number of test cases. The description of the test cases follows.
The first line contains three integers $$$n,h,H$$$ $$$(1 \leq n \leq 2*10^5,1 \leq h \leq H \leq 300)$$$.
The second line contains $$$n$$$ integers $$$x_1,x_2,\dots,x_n(1 \leq x_i \leq 2*10^5)$$$ — the arrival time of the $$$i$$$-th player.
The third line contains $$$n$$$ integers $$$c_1,c_2,\dots,c_n(1 \leq c_i \leq 2*10^5)$$$ — the delay time of the $$$i$$$-th player.
For each test case, print the winner.
2 4 2 5 3 6 1 9 6 4 2 3 3 1 2 1 2 3 4 5 6
3 1
Given you two integers $$$N$$$,$$$K$$$,you need to construct a set of $$$N$$$-dimensional vectors of size $$$N$$$.Each dimension of each vector can only be $$$0$$$ or $$$1$$$. And for a vector, its sum of all dimensions is $$$K$$$. Meanwhile, any vector can't be represented by other vectors using $$$XOR$$$ operation.
If such a vector group exists, find the minimum vector group, otherwise output $$$-1$$$. (Define the minimum set of vectors as the minimum lexicographic order after each vector is converted to binary)
There are $$$T(1 \leq T \leq 1000)$$$ test cases in this problem.
For every test case,the first line has two integer $$$N(1 \leq N \leq 62)$$$,$$$K(1 \leq K \leq N)$$$.
If the vector group does not exist, output $$$-1$$$.
Otherwise output the minimum vector group, expressed in decimal notation.
2 5 3 5 1
7 11 13 14 19 1 2 4 8 16
Have you heard about Splendor's board game? We will adapt the process of this game. There are five colors of chips and gems in this game: white, blue, red, green and black. You start with zero chip.
There will be $$$N$$$ gem cards and $$$M$$$ pirates,Each gem card has three attributes,score,gem type,in exchange for the chips needed.
In each turn,you can exchange the corresponding chip for one card,then you will gain the score of this card and the gem on this card. (Once you have this card,you can't get the same card next time.)
But noticed: there can be no score in a gem card.
When the pirate observes that you have the type and number of gems he wants, the pirate will automatically come to you and you will receive the pirate's score.(Means that you will get bonus scores.) In each turn, you can do one of the three things:
1. Obtain any three different colored chips from the stack.
2. Obtain any two chips of the same color from the stack.
3. Exchange your chips for gems. Now, you have known all the gems and pirates.Your goal is to reach the minimum $$$goal$$$ score as soon as possible. How many turns does it take?(If you can't reach the minimum goal,you should output $$$-1$$$.)
White, blue, red, green and black correspond to $$$1$$$,$$$2$$$,$$$3$$$,$$$4$$$,$$$5$$$ There are $$$T(1 \leq T \leq 100)$$$ test cases in this problem.
For every test cases,the first line has three integers $$$N(1 \leq N \leq 20)$$$, $$$M(1 \leq M \leq 100)$$$, $$$goal(1 \leq goal \leq 40)$$$respectively representing the number of gems, the number of pirates, and the total score of the goal. The next $$$N$$$ rows starts with three integers,where the $$$i$$$ row starts with three integers $$$p_i(0 \leq p_i \leq 5)$$$,$$$op_i(1 \leq op_i \leq 5)$$$,$$$k_i(1 \leq k_i \leq 5)$$$, respectively representing the score of the $$$i$$$ gem card, the kind of gem, and the number of kinds of chips required.
Each row is followed by $$$k_i$$$ pairs of integers,$$$b_{ij}(1 \leq b_{ij} \leq 5)$$$,$$$c_{ij}(1 \leq c_{ij} \leq 9)$$$,indicating that it takes $$$c_{ij}$$$ type $$$b_{ij}$$$ chips to get this gem card. Next, there are $$$M$$$rows, each row represents a pirate's information, where the first row of $$$i$$$ has two integers $$$q_i(0 \leq q_i \leq 5)$$$,$$$b_i(1 \leq p_i \leq 5)$$$,indicating that the pirate's score is $$$q_i$$$, and the number of types of gems the player needs to own is $$$b_i$$$.
Each row is followed by $$$b_i$$$ pairs of integers,$$$d_{ij}(1 \leq d_{ij} \leq 5)$$$,$$$e_{ij}(1 \leq e_{ij} \leq 9)$$$,indicating that the pirate needs to find that you have at least $$$e_{ij}$$$ of type $$$d_{ij}$$$ to come to you. Promised that all $$$b_{ij}$$$,$$$d_{ij}$$$ in one gem card or one pirate are different.
For every test case, output the answer in a line.
1 12 4 15 3 3 4 4 3 1 3 5 3 2 5 4 2 1 1 7 4 5 3 3 6 5 3 4 3 5 4 2 2 7 4 3 1 1 3 2 3 3 3 1 2 2 1 2 3 5 5 3 2 2 2 1 5 2 3 1 1 3 3 2 5 2 4 3 0 1 3 4 2 5 1 2 2 0 4 1 3 3 0 5 3 2 2 3 1 1 2 0 4 1 5 4 3 2 1 4 2 4 3 3 1 3 2 3 4 3 3 3 4 3 3 3 5 3 3 2 2 4 4 4
17
Now there are $$$K$$$ people play Halli Galli game.They will play $$$N$$$ turns in all,in the order of the first player,the second player,$$$\cdots$$$,the $$$K$$$ player,the first player,$$$\cdots$$$.
In one turn,the player will display a card on his side,if there are $$$a$$$ kinds of fruit which its total ammount is exactly 5 in all sides,the bell will be pushed $$$a$$$ times in this turn.Notices that the previous card will be covered by the current card.
Now you have to calculate the total times they push the bell in $$$N$$$ turns.
There are $$$T(1 \leq T \leq 100)$$$ test cases in this problem.
For every test cases,the first line has two integers $$$N(1 \leq N \leq 100)$$$, $$$K(1 \leq K \leq 6)$$$respectively representing the number of turns, the number of people.
The next $$$N$$$ rows with a char $$$ch$$$ and an integer $$$x(1 \leq x \leq 5)$$$,respectively representing the type of fruit on the card,the ammount of fruit on the card.
There are always four kinds of fruit,respectively 'A' ,'B','G','P'(Apple,Banana,Grape,Pear).
For every test case, output the answer in a line.
1 5 3 A 5 B 2 B 3 G 1 P 5
6
PepperLa loves strings.His desire for strings is infinite, but his storage is limited.
There is a method to compress strings. A substring whose characters are all the same and are all lower case letters could be compressed into one character plus one hexadecimal number which represents character's counting. (numbers over ten are represented in upper case letters) Here a substring is a string could be obtained by deleting several characters from the begin and end.
For example,the string is "aaacccccccccc". compression operations could replace "aaa" with "a3", and repalce "cccccccccc" with "cA". So the compressed string becomes "a3cA". And if you choose 17 'a', you could compress it to "a11", but you can't compress "11" to "12".
The method allows lossy compression which means you can miss at most 1 character before you compressing the string. It should be noted that after deleting one character the string is actually not successive.(See sample testcase for details)
You can do any times or even zero times of compression operations, find the shortest compressed string, if there are multiple answers, output the one with minimal lexicographic order.
There are multiple test cases in this problem.
For every test case, the input contains one line, the given string.
The input guarantees that strings contains only lower case letters
For each test case, $$$1 \lt string.length \leq 10^6$$$, $$$\sum{length}\leq 5 \times 10^6$$$
For each test case, output a single line contains the answer string.
aaacccccccccc aaabaaa
a2cA a3a3
In first string, if you choose to miss one 'a', the string becomes "aacccccccccc" and compressed string is "a2cA".
In second string, if you choose to miss one 'b', the string becomes something like "aaa aaa" the answer is not "a6" but "a3a3".
PepperLa is good at dealing with string problems, so he's going to offer string algorithm courses.
PepperLa has set up $$$N$$$ class rooms, there's one road between every two class rooms, and each road is equal in length.
PepperLa is afraid of the dark, so he only walks on roads with the light on. At the beginning, there is no light on. PepperLa has to pay one dollar for lighting the light of a road. However, PepperLa is dreaming of buying himself a switch, so he would like to pay the least.
The courses are scheduled so tightly that PepperLa can't afford to waste his time. So the distance between two class room should not be too far away. Specifically, you need to light the fewest roads so that the shortest distance between class room $$$i$$$ and class room $$$j$$$ should eaqual to $$$dis[i][j]$$$.(the distance means the total length of the path)
Please tell PeoperLa how much is the minimum he has to pay.
There are multiple test cases in this problem.
For every test case, The first line has 1 interger, $$$N(1 \leq N \leq 10^3)$$$
The next $$$N$$$ lines each line contains $$$N$$$ interger, the interger in $$$i$$$'th row, $$$j$$$'th column is $$$dis[i][j](1 \leq dis[i][j] \leq 10^6)$$$
The input guarantees that the data given is legal and there's always a solution
$$$dis[i][j]=dis[j][i],dis[i][i]=0, \sum{N}\leq 5 \times 10^3$$$
For each test case, output a single line contains one integer,representing for the minimal money PepperLa has to pay.
3 0 1 2 1 0 1 2 1 0
2
Light the light of road (1,2),(2,3)
Given you an $$$N*N$$$ grid graph,you can color any block black or white,but you have to meet the condition:
For each block $$$(x,y)$$$,it can't be the same color as $$$(x-3,y),(x-1,y+2),(x+1,y+2),(x+3,y)$$$.
You need to calculate the total number of options for coloring the $$$N*N$$$ grid graph.
There are $$$T$$$ test cases in this problem.
The first line has one integer $$$T(1 \leq T \leq 10^5)$$$.
For every test case,the first line has $$$1$$$ integer $$$N(1 \leq N \leq 10^9)$$$.
For every test case, output the answer in a line.
2 1 6
2 4
PepperLa is a braggart(King of Blowing Cattle), which only means he has great lung capacity.
One day,the two-dimensional plane he lives is on fire.His current position is $$$(1,1)$$$, and the fire escape is at $$$(n,m)$$$. "Just a fire, why bother!" PepperLa boasted.
Because the fire is spreading quickly, once he starts running, he can't turn back. If his current position is $$$(x, y)$$$, he can only move forward to $$$(x+1,y+1)$$$ or $$$(x+1,y)$$$ or $$$(x,y+1)$$$ in one minute.
There is different volume of fresh air rested in each area. If an area's fresh air $$$\leq 0$$$, that means what left in the area is poisonous somke, PepperLa couldn't breath here.
Thanks to PepperLa's great lung capacity, each breath he can take in any volume of air and stored in his lung, he can hold the breath through poisonous smoke area. Each time, He can hold his breath for at most $$$K$$$ minutes, and cost $$$U$$$ volume of air.(If he doesn't hold the breath it cost no air, wow) He can start to hold his breath only if the air in his lung $$$ \gt = U$$$.
Now PepperLa wonder whether he could survive so he could brag about his heroic experience. If PepperLa survives, he wants to know the maximum volume of air left in the lung when he comes to the exit.(the more air left, the more he can boast) If PepperLa couldn't escape, sadly, output -1.
There are multiple test cases in this problem.
For every test case, The first line has 4 interger, $$$N, M, K, U$$$ $$$(1 \leq N, M \leq 10^3,1 \leq K, U \leq 10^9)$$$
The next $$$N$$$ lines each line contains $$$M$$$ interger, the interger in $$$i$$$'th row, $$$j$$$'th column is volume of air rested in area $$$(i,j)\in[-10^9,10^9]$$$
The input guarantees that the air rested in area $$$(1,1),(n, m) \gt 0$$$, $$$\sum{N\times M}\leq 7 \times 10^6$$$
For each test case, output a single line contains one integer,representing for the answer.
3 4 2 1 1 0 0 9 0 -1 1 1 -1 0 2 1
4
$$$(1,1)$$$–hold breath->$$$(2,2)$$$–hold breath->$$$(2,3)$$$—>$$$(3,3)$$$—>$$$(3,4)$$$
when you at (1,1) you start to hold your breath, that's the first minute. The second minute, you walk through (2,2). Then you come to (2,3) and you can no longer hold your breath.
PepperLa's City is a three-dimensional city whose size is $$$(Z*X*Y)$$$.
PepperLa Express is the only express in the city. The company has set up several delivery station in the city, and users will choose the nearest one.
PepperLa's vehicle is poor, it can only travel along the $$$Z, X, Y$$$ axis at the speed of one unit length per day.
Because many users complained about the delivery inefficiency, PepperLa decides to add a new delivery station in the open space. According to "barrel principle" PepperLa hopes to reduce the maximum delivery time. It means to minimize the maximum delivery time of all users.
Could You help him find the best place?
There are multiple test cases in this problem.
For every test case, The first line has 3 interger, $$$Z,X,Y(1 \leq Z,X,Y \leq 10^2)$$$
Then following $$$Z\times X$$$ lines each line contains $$$Y$$$ characters, the character in $$$i$$$'th row (start from 0), $$$j$$$'th column is $$$(z=\lfloor i/X \rfloor+1,x=i\%X+1, y=j)$$$
'.' represents open space, '*' represents a user, '@' represents a delivery station.
The input guarantees that there is at least one '.' and at least one '@'. $$$\sum{Z\times X \times Y}\leq 6 \times 10^6$$$
For each test case, output a single line contains one integer,representing for the minimal delivery time.
3 3 3 ... .*. ... @*@ *.* @*@ ... .*. ...
1
the best place to set up a new delivery station is $$$(z=2,x=2,y=2)$$$