← 返回题目列表

Codeforces · 1937/B

B. 二进制路径

中文机器翻译题面 查看原题

给你一个 $$$2 \times n$$$ 的网格,其中充满了零和一。令第 $$$i$$$ 行和第 $$$j$$$ 列的交叉点处的数字为 $$$a_{ij}$$$。

左上角的单元格 $$$(1, 1)$$$ 处有一只蚱蜢,它只能向右或向下跳一个单元格。它想要到达右下角的单元格$$$(2, n)$$$。考虑长度为 $$$n+1$$$ 的二进制字符串,该字符串由写入路径单元格中的数字组成,且不更改其顺序。

您的目标是:

1. 通过选择任意可用路径找到按字典顺序最小的$$$^\dagger$$$字符串;
2. 找出产生该字典顺序最小字符串的路径数。

$$$^\dagger$$$ 如果两个字符串 $$$s$$$ 和 $$$t$$$ 具有相同的长度,则 $$$s$$$ 按字典顺序小于 $$$t$$$ 当且仅当在 $$$s$$$ 和 $$$t$$$ 不同的第一个位置,字符串 $$$s$$$ 的元素比 $$$s$$$ 中的相应元素小$$$t$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$)。

每个测试用例的第二行包含一个二进制字符串 $$$a_{11} a_{12} \ldots a_{1n}$$$ ($$$a_{1i}$$$ 是 $$$0$$$ 或 $$$1$$$)。

每个测试用例的第三行包含一个二进制字符串 $$$a_{21} a_{22} \ldots a_{2n}$$$ ($$$a_{2i}$$$ 是 $$$0$$$ 或 $$$1$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出两行:

1. 通过选择任何可用路径可以获得的按字典顺序排列的最小字符串;
2. 产生该字符串的路径数。

示例

输入 #1

3
2
00
00
4
1101
1100
8
00100111
11101101

输出 #1

000
2
11000
1
001001101
4

注意

在第一个测试用例中,字典顺序最小的字符串是 $$$\mathtt{000}$$$。有两条路径可以产生该字符串:

在第二个测试用例中,字典顺序最小的字符串是 $$$\mathtt{11000}$$$。只有一条路径可以生成该字符串: