Background

Original problem link: https://oier.team/problems/S5C。

---

IMAWANOKIWA - Iyowa / Hatsune Miku

あなたの未来が見たかった。

Problem Description

You are given a sequence $a_{1 \sim n}$ of initial length $n$ that contains only $\boldsymbol{0, 1, 2}$. You can perform the following operation:

• Choose two adjacent positions $j$ and $j + 1$, delete $a_j, a_{j + 1}$, and insert $\mathrm{popc}(a_j + a_{j + 1})$ at the original position. The second half of the sequence therefore shifts forward by one position. Here, $\mathrm{popc}(x)$ denotes the number of $1$'s in the binary representation of $x$.

Obviously, after each operation the sequence length decreases by $1$, so after performing $n - 1$ operations, the sequence will end up with exactly one number.

Let the minimum possible remaining number after all possible sequences of $n - 1$ operations be $t$. Define a good operation sequence $p$ as a positive integer sequence of length $n - 1$, where $p_i$ denotes the chosen $j$ in the $i$-th operation (clearly $1 \le p_i \le n - i$), and after performing operations according to this sequence, the remaining number equals $t$. You need to output $t$ and the lexicographically smallest good operation sequence.

If you cannot find the lexicographically smallest good operation sequence, you can still get partial points, see [Scoring] for details.

To avoid excessive output, you only need to output the hash value of the lexicographically smallest good operation sequence under a certain hashing method, see [Output Format] for details.

Input Format

This problem contains multiple test cases.

The first line contains a positive integer $T$, the number of test cases. Then for each test case:

• A single line containing a string of length $n$, where the $i$-th character represents $a_i$.

Output Format

For each test case:

• Output one line with two non-negative integers $t, \mathrm{Hash}(p')$, where
  • The first number is the minimum possible remaining number.
  • The second number is the hash value $\mathrm{Hash}(p')$ of the lexicographically smallest good operation sequence $p'$, defined below.
  • Even if the second number you output is incorrect, you can still get partial points, and the problem will use a custom checker to do this. See [Scoring] for details.

Let $B = 13331$ and $M = 2^{64}$. We define the hash value $\mathrm{Hash}(c)$ of a positive integer sequence $c_{1 \sim l}$ as $\sum_{i = 1}^l B^{l - i}c_i$ modulo $M$.

Hint: In code, you can use the natural overflow of C++ type unsigned long long to achieve the modulo $2^{64}$ effect.

7
110121
120202
1202
1121212
000
010101110
0112210112

1 31589928355420248
1 31587559229276557
2 177728893
2 15233797274127957404
0 13332
1 4098728445451629840
1 892964726593242284

Hint

[Sample Explanation #1]

For the first test case, the lexicographically smallest good operation sequence $p$ is $[1, 3, 2, 1, 1]$. When performing operations according to this sequence, the changes of sequence $a$ are as follows:

$$[1, 1, 0, 1, 2, 1]\\ [1, 0, 1, 2, 1]\\ [1, 0, 2, 1]\\ [1, 1, 1]\\ [1, 1]\\ [1]$$

So the hash value you should output is $\mathrm{Hash}([1, 3, 2, 1, 1]) = (1 \times 13331^4 + 3 \times 13331^3 + 2 \times 13331^2 + 1 \times 13331^1 + 1 \times 13331^0) \bmod 2^{64} = 31589928355420248$.

For the second test case, the lexicographically smallest good operation sequence $p$ is $[1, 2, 2, 1, 1]$. When performing operations according to this sequence, the changes of sequence $a$ are as follows:

$$[1, 2, 0, 2, 0, 2]\\ [2, 0, 2, 0, 2]\\ [2, 1, 0, 2]\\ [2, 1, 2]\\ [2, 2]\\ [1]$$

[Sample #2]

See popc/popc2.in and popc/popc2.ans in the attachments.

This sample contains ten test cases. All test cases satisfy $n = 10^5$. Among them, test cases $1 \sim 5$ satisfy that there is no $0$ in sequence $a$, and test cases $6 \sim 10$ satisfy that there is no $1$ in sequence $a$.

[Sample #3]

See popc/popc3.in and popc/popc3.ans in the attachments.

This sample contains forty test cases. Among them, test cases $1 \sim 10$ satisfy $n = 300$, $11 \sim 20$ satisfy $n = 3000$, $21 \sim 30$ satisfy $n = 3 \times 10^4$, and $31 \sim 40$ satisfy $n = 10^5$.

[Scoring]

This problem will use a custom checker to compute your partial score.

For a test point, if there exists any testdata where the minimum value you output is incorrect, then you cannot get any score for this test point.

For a test point, if the minimum value you output is correct for every test case, but there exists some testdata where the hash value of the lexicographically smallest good operation sequence you computed is incorrect, then you can get $25\%$ of the score for this test point (i.e. $1$ point, see [Constraints]). Note that you still need to output any integer within $\boldsymbol{[0, 2^{64})}$ as the hash value of your solution.

For a test point, if the minimum value you output is correct for every test case, and the hash value of the lexicographically smallest good operation sequence you computed is also correct, then you can get the full score for this test point.

[Constraints]

For all testdata, it is guaranteed that $1 \le T \le 200$, $2 \le n \le 10^5$, and sequence $a$ contains only $\boldsymbol{0, 1, 2}$.

Test Point ID	$T\le$	$n\le$	Special Property
$1 \sim 3$	$10$	$10$	None
$4 \sim 6$		$300$
$7 \sim 9$		$3000$
$10 \sim 12$		$3 \times 10^4$
$13 \sim 15$		$10^5$	No $0$ in sequence $a$
$16 \sim 19$			No $1$ in sequence $a$
$20 \sim 21$			None
$22 \sim 23$	$50$
$24 \sim 25$	$200$

Translated by ChatGPT 5