Given two arrays $$$A$$$, $$$B$$$ of length $$$n$$$ and $$$m$$$ separately, you have to merge them into only one array $$$C$$$ (of length $$$n+m$$$) obeying the rule that the relative order of numbers in the same original array does not change in the new array.
After merging, please calculate the $$$cost=\sum_{i=1}^{n+m} i \times C[i] $$$ and output it.
If there are multiple $$$cost$$$s, please output the minimum of them.
The first line of input file contains an integer $$$T$$$ ($$$1\le T\le 50$$$), describing the number of test cases.
Then there are $$$3 \times T$$$ lines, with every three lines representing a test case.
The first line of the test case contains two integers $$$n$$$ and $$$m$$$ ($$$1\le n,m\le 10^5$$$) as described above.
The second line of that contains $$$n$$$ integers, $$$i^{th}$$$ of which represents the $$$A[i]$$$.
The third line of that contains $$$m$$$ integers, $$$i^{th}$$$ of which represents the $$$B[i]$$$.
The numbers in both array have range in $$$[0,10^8]$$$.
It is guaranteed that the sum of $$$n+m$$$ in all cases does not exceed $$$10^6$$$.
You should output exactly $$$T$$$ lines. For each case, print Case $$$d$$$: ($$$d$$$ represents the order of test case) first and then print a number representing the minimum $$$cost$$$ on the same line.
2
2 2
5 3
4 5
3 3
1 3 5
2 6 4
Case 1: 40
Case 2: 75
Sample 1: Considering merging (5) (3) and [4] [5], we have following valid methods:
- (5) (3) [4] [5], $$$1 \times 5+2 \times 3+3 \times 4+4 \times 5=43$$$
- (5) [4] (3) [5], $$$1 \times 5+2 \times 4+3 \times 3+4 \times 5=43$$$
- (5) [4] [5] (3), $$$1 \times 5+2 \times 4+3 \times 5+4 \times 3=40$$$
- [4] (5) (3) [5], $$$1 \times 4+2 \times 5+3 \times 3+4 \times 5=43$$$
- [4] (5) [5] (3), $$$1 \times 4+2 \times 5+3 \times 5+4 \times 3=41$$$
- [4] [5] (5) (3), $$$1 \times 4+2 \times 5+3 \times 5+4 \times 3=41$$$
So the answer is the minimum of the numbers above, 40.
Given an array $$$A$$$ with $$$n$$$ numbers and two integers $$$L$$$, $$$m$$$. You have to output the final array after performing the following operation $$$m$$$ times:
$$$$$$A[i]=\left(\sum_{j=i}^{\min(i+L-1,n)}A[j]\right) \bmod P\text{, in order of } i=1, 2,\cdots, n$$$$$$
$$$P=998,244,353$$$ is a fixed number.
The first line of input file contains an integer $$$T$$$ ($$$1\le T\le 20$$$), describing the number of test cases.
Then there are $$$2 \times T$$$ lines, with every two lines representing a test case.
The first line of each test case contains three integers: $$$n$$$, $$$L$$$, $$$m$$$ ($$$1\le n\le 100,000$$$, $$$1\le L\le n$$$, $$$1\le m\le 10^9$$$) described above.
The second line of that contains exactly $$$n$$$ integers,the $$$i$$$-th of which represents $$$A[i]$$$ ($$$0\le A[i] \lt P, \text{for }i=1, 2, \cdots, n$$$).
It is guaranteed that the sum of $$$n$$$ in all cases does not exceed $$$200,000$$$.
You should output exactly $$$T$$$ lines.
For each case, print Case $$$d$$$: ($$$d$$$ represents the order of test case) first, and then output exactly $$$n$$$ integers, $$$i^{th}$$$ of which represents $$$A[i]$$$, separated by exactly one space.
2
3 2 2
1 2 3
4 1 3
1 2 3 4
Case 1: 8 8 3
Case 2: 1 2 3 4
Sample 1:
There is a binary tree with $$$N$$$ nodes.
As a tree killer, you picked subtrees from that tree yesterday!
And now you regret.
You probably remember the height of $$$M$$$ subtrees with distinct roots, but can you reconstruct that tree?
Well, that may be hard for you because of the tremendous number of nodes.
You just have to check whether you can!
By the way, guess whether original tree is a complete binary tree as well!
The first line of the input file contains a simple integer $$$T$$$ ($$$1\le T\le 100$$$) describing the number of test cases.
Then there are $$$2 \times T$$$ lines with every two lines representing a test case.
The first line of the test case contains two integers $$$N$$$, $$$M$$$ ($$$1\le N\le 10^9$$$, $$$1\le M\le 10^5$$$) described above.
The second line of that contains $$$M$$$ numbers representing the heights ranging in $$$[1,10^9]$$$.
Please print $$$T$$$ lines exactly, with the answer to corresponding test case each line.
For each answer, print Case $$$d$$$: ($$$d$$$ represents the order of test case) first, and then write your answer:
if what you remember cannot form a binary tree, print INVALID;
if it may be binary tree, then just check whether it may be a complete binary tree: IMPOSSIBLE (it must not be a complete binary tree), POSSIBLE (it may be a complete binary tree), DEFINITELY (it must be a complete binary tree).
5
1 1
1
1 1
2
2 1
2
2 2
1 2
15 3
3 3 3
Case 1: DEFINITELY
Case 2: INVALID
Case 3: POSSIBLE
Case 4: POSSIBLE
Case 5: IMPOSSIBLE
Now given two integers $$$x$$$ and $$$y$$$, you can reverse every consecutive three bits in arbitrary number's binary form (any leading zero can be taken into account) using one coin. Reversing $$$(1, 2, 3)$$$ means changing it into $$$(3, 2, 1)$$$.
Could you please find a way that minimize number of coins so that $$$x = y$$$? If you can, just output the minimum coins you need to use.
The first line of input file contains only one integer $$$T$$$ ($$$1\le T\le 10000$$$) indicating number of test cases.
Then there are $$$T$$$ lines followed, with each line representing one test case.
For each case, there are two integers $$$x$$$, $$$y$$$ ($$$0\le x, y \le 10^{18}$$$) described above.
Please output $$$T$$$ lines exactly.
For each line, output Case $$$d$$$: ($$$d$$$ represents the order of the test case) first. Then output the answer in the same line. If there is no way for that, print -1 instead.
3
0 3
3 6
6 9
Case 1: -1
Case 2: 1
Case 3: 2
- Sample 1: Considering following two binary string:
$$$0$$$: $$$0\cdots0000$$$
$$$3$$$: $$$0\cdots0011$$$
There is no way to achieve the goal.
- Sample 2: Considering following two binary string:
$$$3$$$: $$$0\cdots0011$$$
$$$6$$$: $$$0\cdots0110$$$
You can reverse the lowest three digits in $$$3$$$ so that $$$3$$$ is changed into $$$6$$$.
You just need to perform one reverse so that the minimum coin you need to use is $$$1$$$.
The Cartesian tree for a sequence of distinct numbers can be uniquely defined by the following properties:
The Cartesian tree for a sequence has one node for each number in the sequence. Each node is associated with a single sequence value.
A symmetric (in-order) traversal of the tree results in the original sequence. That is, the left subtree consists of the values earlier than the root in the sequence order, while the right subtree consists of the values later than the root, and a similar ordering constraint holds at each lower node of the tree.
The tree has the heap property: the parent of any non-root node has a larger value than the node itself.
$$$-$$$Wikipedia
It is quite easy to build a Cartesian tree with an array of $$$N$$$ distinct numbers, right?
What if changing the array by exchanging the value in position $$$i$$$ and that in position $$$i+1$$$?
Now you need to answer the sum of absolute layer(height) change of the tree nodes for each of the $$$M$$$ successive changes.
The first line contains a single integer $$$T$$$ ($$$1\le T\le 20$$$), indicating the number of test cases.
For each test case, the first line contains two integers $$$N$$$ ($$$2 \le N \le 10^5$$$) and $$$M$$$ ($$$1\le M\le 10^5$$$), indicating the number of elements in the array and the number of queries.
The second line contains $$$N$$$ elements, indicating the elements in the array.
The next $$$M$$$ lines describe $$$M$$$ changes described above. Each line contains a 0-based index $$$i$$$ ($$$0\le i \lt N-1$$$), which indicates we want to swap the elements located in $$$i$$$ and $$$i + 1$$$.
For each test case, print Case $$$T$$$: at first line, in which $$$T$$$ is the test number. For each change, output the sum of absolute layer change of the tree nodes in a new line.
3
4 2
1 2 3 4
2
1
3 6
1 2 3
0
1
1
0
0
0
5 10
2 3 5 4 1
0
1
2
3
2
3
1
2
3
2
Case 1:
2
2
Case 2:
0
1
1
0
0
0
Case 3:
0
0
1
0
1
1
1
1
3
2
The first sample of Sample 1:
There is an array $$$A$$$ of $$$n$$$ positive integers, and $$$m$$$ equations of the form A[x] op A[y] = z, where $$$x$$$ and $$$y$$$ represent the positions in $$$A$$$, $$$op \in \{+,-,*\}$$$ and $$$z$$$ is a given integer which may differ for each equation.
However, as all the numbers in $$$A$$$ are missing, you have to find out that array and print them out.
If there are multiple arrays that do not break any equation, you just have to print out the number of valid arrays mod $$$(10^9 + 7)$$$.
The first line of the input file contains an integer $$$T$$$ ($$$1\le T\le 25$$$), describing the number of test cases.
For each test case, the first line contains two integers $$$n$$$, $$$m$$$ ($$$1\le n\le 10^4$$$, $$$1\le m\le 10^6$$$) described above, followed by $$$m$$$ lines.
Each of the following $$$m$$$ lines contains one string of the form xPy=z without any space ($$$x$$$, $$$y$$$, $$$z$$$ are numbers and $$$P$$$ is a character, $$$1\le x,y\le n$$$, $$$P\in\{+,-,*\}$$$, $$$0\le z\le 10^6$$$) representing one equation A[x] P A[y] = z described above.
There are no more than 5 test cases that $$$m \geq 10^5$$$.
You may need to read the sample inputs for the detail.
You should output exactly $$$T$$$ lines.
For each test case, print Case $$$x$$$: $$$d$$$ ($$$x$$$ represents the order of test case, and $$$d$$$ represents the number of solution mod $$$(10^9+7)$$$, using $$$d=-1$$$ to represent infinite ) first.
Then if the array is unique, output $$$n$$$ numbers after $$$d$$$ describing that array separated by exactly one space.
You should notice that there is only one line for one case.
4
3 2
1+2=3
1*3=9
4 3
1+2=10
2+3=3
1+4=9
2 2
1+2=3
1-2=3
3 2
1+2=4
1*3=9
Case 1: 1 1 2 9
Case 2: 1 8 2 1 1
Case 3: 0
Case 4: 2
- Sample 1:
Equations:
- $$$A[1]+A[2]=3$$$
- $$$A[1] \times A[3]=9$$$
There is only one solution: $$$A[1]=1, A[2]=2, A[3]=9$$$.
- Sample 3:
Equations:
- $$$A[1]+A[2]=3$$$
- $$$A[1]-A[2]=3$$$
There is no solution for array $$$A$$$.
- Sample 4:
Equations:
- $$$A[1]+A[2]=4$$$
- $$$A[1] \times A[3]=9$$$
There is two solutions:($$$A[1]=1, A[2]=3, A[3]=9$$$) and ($$$A[1]=3, A[2]=1, A[3]=3$$$).
There is an array of length $$$n$$$, containing only positive numbers.
Now you can add all numbers by $$$1$$$ many times. Please find out the minimum times you need to perform to obtain an array whose greatest common divisor(gcd) is larger than $$$1$$$ or state that it is impossible.
You should notice that if you want to add one number by $$$1$$$, you need to add all numbers by $$$1$$$ at the same time.
The first line of input file contains an integer $$$T$$$ ($$$1\le T\le 20$$$), describing the number of test cases.
Then there are $$$2 \times T$$$ lines, with every two lines representing a test case.
The first line of each case contains a single integer $$$n$$$ ($$$1\le n \le 10^5$$$) described above.
The second line of that contains $$$n$$$ integers ranging in $$$[1,10^9]$$$.
You should output exactly $$$T$$$ lines.
For each test case, print Case $$$d$$$: ($$$d$$$ represents the order of the test case) first. Then output exactly one integer representing the answer. If it is impossible, print -1 instead.
3
1
2
5
2 5 9 5 7
5
3 5 7 9 11
Case 1: 0
Case 2: -1
Case 3: 1
- Sample 1: You do not need to do anything because its gcd is already larger than $$$1$$$.
- Sample 2: It is impossible to obtain that array.
- Sample 3: You just need to add all number by $$$1$$$ so that gcd of this array is $$$2$$$.
In information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. In other words, it measures the minimum number of substitutions required to change one string into the other, or the minimum number of errors that could have transformed one string into the other.
$$$-$$$ Wikipedia
Assume that there are two strings with same length, which only contain lowercase characters, find a lexicographically smallest string with same length, and the Hamming distance between the target string and each original string are equal.
The first line contains a number $$$T$$$ ($$$1 \leq T \leq 100$$$), indicating the number of test cases.
Each time case contains two lines of strings, indicating the two original strings, which only contain lowercase characters. The length of string is smaller than $$$10^4$$$, and total length of the strings is less then $$$10^6$$$.
For each case, output Case $$$x$$$: $$$y$$$, in which x indicates the case number starting with 1, and y indicates the result of the target string. The target string should only contain lowercase characters.
2
abc
acd
abandon
newyork
Case 1: aaa
Case 2: aaaaark
Sample 2:
HM(abandon,aaaaark) = HM(newyork, aaaaark) = 5
And aaaaark is the lexicographically smallest string that meets the constraints.
There are $$$n$$$ people sitting in a line. They are numbered from $$$1$$$ to $$$n$$$ from the left to right. For each person $$$i$$$, there is an item in his hands and also numbered $$$i$$$.
Each person has a "preference list" which is a permutation of $$$1, \dots, n$$$. The preference list describes one's preference for those items, i.e. if $$$i$$$ appears more formerly than $$$j$$$ in one's list, we could say that he prefer item $$$i$$$ than item $$$j$$$.
As the people can see the item in his neighbor's hand, if there are two persons (who are neighbors) both prefer the item in each other's hand, they can exchange their items.
Now given the preference lists of all the people, and two integers $$$i$$$, $$$j$$$, you have to answer whether there is an exchange scheme that person $$$j$$$ owns item $$$i$$$ at some moment.
The first line of input file contains an integer $$$T$$$ ($$$1 \leq T \leq 85$$$), describing the number of test cases.
For each test case, there are several lines.
First of them contains only one integer $$$n$$$ ($$$1\le n \le 200$$$) described above.
Then following $$$n$$$ lines with $$$n$$$ numbers ranging from $$$1$$$ to $$$n$$$ each line. The $$$i$$$-th line of those describing the "preference list" of person $$$i$$$ ($$$1\le i \le n$$$).
And the $$$(n+2)$$$-th line contains two integers $$$i$$$ and $$$j$$$ ($$$1\le i\le n$$$, $$$1\le j\le n$$$) described above.
There are no more than 14 test cases that $$$n \geq 100$$$.
You should output exactly $$$T$$$ lines.
For each test case, print Case $$$d$$$: ($$$d$$$ represents the order of case) first, and then print the answer, Yes or No, on the same line.
3
3
3 1 2
1 3 2
2 3 1
1 2
3
3 1 2
1 3 2
2 3 1
1 3
4
3 1 2 4
4 1 3 2
1 4 2 3
2 4 1 3
1 3
Case 1: Yes
Case 2: No
Case 3: Yes
There is a possible scheme for Sample 3:
$$$(1,\underline{2,3},4)\rightarrow(\underline{1,3},2,4)\rightarrow(3,1,\underline{2,4})\rightarrow(3,\underline{1,4},2)\rightarrow(3,4,1,2)$$$
Alice and Bob are always playing game! The game today is about taking out stone from the stone piles in turn.
There are $$$n$$$ piles of stones, and the $$$i$$$-th pile contains $$$A[i]$$$ stones.
As the number of stones in each pile differs from its neighbor's, they determine to take out exactly one stone from one of them in one turn without breaking that property. Alice goes first.
The player who cannot take stone will lose the game.
Now you have to determine the winner given $$$n$$$ numbers representing the piles, if they both play optimally.
You should notice that even a pile of 0 stone is still regarded as a pile!
The first line of input file contains an integer $$$T$$$ ($$$1\le T\le 100$$$), describing the number of test cases.
Then there are $$$2 \times T$$$ lines, with every two lines representing a test case.
The first line of each test case contains only one integer $$$n$$$ ($$$1\le n\le 10^5$$$) as described above.
The second line of that contains exactly $$$n$$$ numbers, representing the number of stone(s) in a pile in order. All these numbers are ranging in $$$[0,10^9]$$$.
It is guaranteed that the sum of $$$n$$$ in all cases does not exceed $$$10^6$$$.
You should output exactly $$$T$$$ lines.
For each test case, print Case $$$d$$$: ($$$d$$$ represents the order of the test case) first, then print the name of winner, Alice or Bob.
2
2
1 3
3
1 3 1
Case 1: Alice
Case 2: Bob
Sample 1:
There is a possible stone-taking sequence: $$$(1,3)\rightarrow(1,2)\rightarrow(0,2)\rightarrow(0,1)$$$
Here is an invalid sequence: $$$(1,3)\rightarrow(1,2)\rightarrow(1,1)\rightarrow(0,1)$$$. Though it has the same result as the first sequence, it breaks that property "the number of stones in each pile differs from its neighbor's".
"The Coin is invaluable."
If you believe that, just buy it and sell it out again!
The price of The Coin may fluctuate over time, but now you can predict the market prices in next $$$n$$$ days!
However, out of the magic power in The Coin, if you sell it out more than once, you have to notice that if the days between two successive selling are more than $$$L$$$, you will get a PUNISHMENT(WA) for your greed.
Now, can you imagine how many benefits you can gain without selling it out for more than $$$m$$$ times?
Do not forget that you are such a rich man that you do not need to worry about the price when you buy it.
The first line of the input file contains a simple integer $$$T$$$ ($$$1\le T\le 20$$$) describing the number of test cases.
Then there are $$$2 \times T$$$ lines with every two lines representing a test case.
The first line of the test case contains three integers $$$n$$$, $$$L$$$, $$$m$$$ ($$$1 \leq L \leq n \leq 10^5$$$, $$$1 \leq m \leq 100$$$) described above.
The second line of that contain $$$n$$$ integers representing the prices of The Coin in following $$$n$$$ days, and each price is less than $$$10^9$$$, and greater than $$$0$$$.
You should notice that you do not have The Coin at first.
Please print $$$T$$$ lines exactly.
For each case, print Case $$$d$$$: ($$$d$$$ represents the order of case) first, with the answer to corresponding test case followed.
3
5 1 2
2 32 4 2 32
5 2 2
2 32 4 2 32
5 5 5
32 16 8 4 2
Case 1: 30
Case 2: 32
Case 3: 0
- Sample 1: You can buy it in the first day, and sell it out in the fifth day.
- Sample 2: You can buy it in the first day, and sell it out in third day. Then buy it in the fourth day, and sell it out in the fifth day.
You should notice that you can not do the sellout in both the second day and fifth day because the days between those are beyond $$$L=2$$$ days.
- Sample 3: You can do nothing with The Coin.
There are two ants landing on an infinite ground containing two chocolate sticks, one white and one black. However, they do not know the accurate position of each other.
"Where are you?", Ant A shouted.
"I don't know. But from my own view I can see the white stick only!", Ant B replies.
"Well I cannot get your accurate position but I know where you may be!", Ant A says.
If two sticks can be regarded as segments which exclude the endpoints and share no more than one common point, can you guess where Ant B may be? Print the total area of that instead.
The first line of input file contains only one integer $$$T$$$ ($$$1\le T \le 1000$$$) indicating the number of test cases.
Then there are $$$T$$$ lines followed, with one test case each line.
For each test case, there are eight integers $$$x_w, y_w, X_w, Y_w, x_b, y_b, X_b, Y_b$$$ ranging in $$$[-1000,1000]$$$. The white one is represented by its two endpoints' positions $$$(x_w, y_w), (X_w, Y_w)$$$ and the black one is represented by its two endpoints' positions $$$(x_b, y_b), (X_b, Y_b)$$$.
Print $$$T$$$ lines exactly.
For each line, please output Case $$$d$$$: ($$$d$$$ represents the order of test case) first and then the answer, whose absolute error should be less than $$$10^{-6}$$$ . If that area is infinite, print inf as answer instead.
3
0 0 0 1 0 0 1 0
0 0 1 0 0 1 0 -1
1 1 1 2 0 0 0 3
Case 1: inf
Case 2: 0.000
Case 3: 0.2500000000
Sample 3:
Only the area $$$S$$$ meets the requirement and its total area is $$$0.25$$$.