1937B.md (2396B)
1 Source: https://codeforces.com/problemset/problem/1937/B 2 3 B. Binary Path 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given a $2 \times n$ grid filled with zeros and ones. Let the number at the intersection of the $i$-th row and the $j$-th column be $a_{ij}$. 22 23 There is a grasshopper at the top-left cell $(1, 1)$ that can only jump one cell right or downwards. It wants to reach the bottom-right cell $(2, n)$. Consider the binary string of length $n+1$ consisting of numbers written in cells of the path without changing their order. 24 25 Your goal is to: 26 27 1. Find the lexicographically smallest$^\dagger$ string you can attain by choosing any available path; 28 2. Find the number of paths that yield this lexicographically smallest string. 29 30 $^\dagger$ If two strings $s$ and $t$ have the same length, then $s$ is lexicographically smaller than $t$ if and only if in the first position where $s$ and $t$ differ, the string $s$ has a smaller element than the corresponding element in $t$. 31 32 Input 33 34 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. 35 36 The first line of each test case contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$). 37 38 The second line of each test case contains a binary string $a_{11} a_{12} \ldots a_{1n}$ ($a_{1i}$ is either $0$ or $1$). 39 40 The third line of each test case contains a binary string $a_{21} a_{22} \ldots a_{2n}$ ($a_{2i}$ is either $0$ or $1$). 41 42 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 43 44 Output 45 46 For each test case, output two lines: 47 48 1. The lexicographically smallest string you can attain by choosing any available path; 49 2. The number of paths that yield this string. 50 51 Example 52 53 Input 54 55 ``` 56 3 57 58 2 59 60 00 61 62 00 63 64 4 65 66 1101 67 68 1100 69 70 8 71 72 00100111 73 74 11101101 75 ``` 76 77 Output 78 79 ``` 80 000 81 2 82 11000 83 1 84 001001101 85 4 86 ``` 87 88 Note 89 90 In the first test case, the lexicographically smallest string is $\mathtt{000}$. There are two paths that yield this string: 91 92  93 94 In the second test case, the lexicographically smallest string is $\mathtt{11000}$. There is only one path that yields this string: 95 96 