A storage facility consists of \(n\geq 3\) lots, placed along a road and numbered sequentially from \(0\) to \(n-1\). That is, for each \(i\) (\(0\leq i\leq n-2\)) the lots \(i\) and \(i+1\) are adjacent, and no other pair of lots is adjacent. All lots are currently empty.
A crane can be installed between two adjacent lots. The crane between lots \(i\) and \(i+1\) can be operated any number of times, and each operation can rearrange the contents of these two lots arbitrarily; in particular, it can swap them.
The cranes that are already installed are described by a string \(C\) of length \(n-1\): \(C[i]\) is ‘C’ if there is a
crane between lots \(i\) and \(i+1\), and ‘-’ otherwise. Let
\(z\) be the number of ‘-’
characters in \(C\). You are also given
a budget \(b\) (\(0\leq b\leq z\)): you may purchase and
install \(b\) additional cranes, each
between two adjacent lots that do not have one yet.
At some later time a shipment of \(m\) containers (\(1\leq m\leq 3\)) will arrive. The containers carry distinct labels from \(\{0,1,\dots,n-1\}\) and each of the \(\binom{n}{m}\) sets of labels is equally likely. The container labelled \(x\) belongs in lot \(x\).
The delivery company is known to mix up the container labels all the time. In particular, they will put the \(m\) containers into the correct set of \(m\) lots, but in a completely random order. That is, each of the \(m!\) ways of placing these \(m\) containers into the correct \(m\) lots is equally likely.
Once the containers are delivered, you may try to rectify the situation by operating the installed cranes. The delivery is repaired if each container ends up in the lot into which it belongs.
Choose the positions of the additional cranes so that the probability that the delivery can be repaired is as large as possible.
The first line of the input contains the number \(t\) of test cases. The specified number of test cases follows, one after another. Each test case consists of two lines:
For each test case output one line with an optimal final
configuration of cranes, in the same format as the string \(C\). (The new string must be obtained from
the old one by changing at most \(b\)
‘-’ characters into ’C’s.)
If there are multiple optimal configurations, you may output any one of them.
Input file: P1.in
Constraints: \(t=100\) and in each test case \(n\leq 20\) and \(1\leq m\leq 3\).
Input file: P2.in
Constraints: \(t=100\) and in each test case \(n\leq 100\) and \(1\leq m\leq 3\).
Input file: P3.in
Constraints: \(t=100\), in each test case \(n\leq 10^5\), \(1\leq m\leq 3\) and \(b\leq 1000\), and the sum of \(n\) over all test cases is at most \(1\,000\,000\).
Input file: P4.in
Constraints: \(t=100\), in each test case \(n\leq 10^5\), \(1\leq m\leq 3\) and \(z-b\leq 1000\), and the sum of \(n\) over all test cases is at most \(1\,000\,000\).
(In words, the condition \(z-b\leq 1000\) guarantees that in each test case you have a budget large enough to purchase almost all the cranes, leaving at most \(1000\) positions without a crane.)
input3 5 1 2 -C-- 6 2 3 -C--C 9 1 3 CCC--C-C | output-CC- -CCCC CCCC-C-C |
In the first example test case the only crane already present in the input allows us to swap containers between lots \(1\) and \(2\). The sample answer purchases another crane between lots \(2\) and \(3\).
For this arrangement of cranes the probability that a delivery can be repaired is \(13/20\). This is because with probability \(1/2\) the \(m = 2\) containers are delivered to their correct lots, and with probability \(1/2\) they are swapped. If they arrive swapped, we can repair the delivery if and only if the delivery involves two of the lots \(\{1, 2, 3\}\). As for \(n=5\) there are ten possible pairs of lots, this happens with the conditional probability \(3/10\).
Purchasing a crane between lots \(0\) and \(1\) is also an optimal solution for the first test case.
In the second test case the optimal purchase leads to the probability \(80/120 = 2/3\) that a delivery can be repaired. For example, if instead of being delivered to lots \((0, 1, 4)\) the containers are delivered to lots \((0, 4, 1)\), we can use three of our four cranes to swap the two misdelivered containers between lots \(1\) and \(4\).
In the third test case the optimal probability is \(47 / 126\).
