Test Tubes
플래티넘 IV의견: 0
Bessie has recently gotten into chemistry. At the moment, she has two different
colors \(1\) and \(2\) of various liquids that don't mix well with one another. She
has two test tubes of infinite capacity filled with \(N\) \((1 \leq N \leq 10^5)\)
units each of some mixture of liquids of these two colors. Because the liquids
don’t mix, once they settled, they divided into layers of separate colors.
Because of this, the two tubes can be viewed as strings \(f_1f_2\ldots f_N\) and
\(s_1s_2\ldots s_N\) where \(f_i\) represents the color of the liquid that is \(i\)
units from the bottom of the first tube, and \(s_i\) represents the color of the
liquid that is \(i\) units from the bottom of the second tube. It is guaranteed
that there is at least one unit of each color of liquid.
Bessie wants to separate these liquids so that each test tube contains all units
of one color of liquid. She has a third empty beaker of infinite capacity to
help her in this task. When Bessie makes a "pour", she moves all liquid of color
\(i\) at the top of one test tube or beaker into another.
Determine the minimum number of pours to separate all the liquid into the two
test tubes, and the series of moves needed to do so. It does not matter which
test tube ends up with which color, but the beaker must be empty..
There will be \(T\) (\(1 \leq T \leq 10\)) test cases, with a parameter \(P\) for each
test case.
Suppose the minimum number of pours to separate the liquids into the original
tubes is \(M\).
- If \(P=1\), you will receive credit if you print only \(M\).
- If \(P=2\), you will receive credit if you print an integer \(A\) such that \(M \leq A \leq M+5\), followed by \(A\) lines that construct a solution with that number of moves. Each line should contain the source and the destination tube (\(1\), \(2\), or \(3\) for the beaker). The source tube must be nonempty before the move and a tube may not be poured into itself.
- If \(P=3\), you will receive credit if you print \(M\), followed by a valid construction using that number of moves.
Problem credits: Suhas Nagar
SCORING
- Inputs 2-6: \(P = 1\)
- Inputs 7-11: \(P=2\)
- Inputs 12-21: No additional constraints.
Additionally, it is guaranteed that \(T=10\) for all inputs besides the sample.
Problem credits: Suhas Nagar
The first line contains \(T\), the. number of test cases. For each test case, the
next line contains \(N\) and \(P\) representing the amount each test tube is
initially filled to, and the query type. The following line contains
\(f_1f_2f_3\ldots f_N\) representing the first test tube. \(f_i \in \{ 1,2 \}\) and
\(f_1\) represents the bottom of the test tube. The subsequent line contains
\(s_1s_2s_3\ldots s_N\) representing the second test tube. \(s_i \in \{ 1,2 \}\) and
\(s_1\) represents the bottom of the test tube.
It is guaranteed that there will be at least one \(1\) and one \(2\) across both
input strings.
For each test case, you will print a single number representing the minimum
pours to separate the liquid in the test tubes. Depending on the query type, you
may also need to provide a valid construction.
6
4 1
1221
2211
4 2
1221
2211
4 3
1221
2211
6 3
222222
111112
4 3
1121
1222
4 2
1121
12224
4
1 2
1 3
2 1
3 2
4
1 2
1 3
2 1
3 2
1
2 1
5
2 3
1 2
1 3
1 2
3 1
6
2 3
1 2
1 3
1 2
2 1
3 2In the first three test cases, the minimum number of pours to separate the tubes
is \(4\). We can see how the following moves separate the test tubes:
Initial state:
1: 1221
2: 2211
3:
After the move "1 2":
1: 122
2: 22111
3:
After the move "1 3":
1: 1
2: 22111
3: 22
After the move "2 1":
1: 1111
2: 22
3: 22
After the move "3 2":
1: 1111
2: 2222
3:
In the last test case, the minimum amount of pours is \(5\). However, since \(P=2\),
the given construction with \(6\) moves is valid since it is within \(5\) pours from
the optimal answer.
riseoj 작성
출처 올림피아드 > USACO > 2023-2024 > February > Silver
평가 및 의견
Test Tubes
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Test Tubes