codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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  ![](https://espresso.codeforces.com/f7600dba7e4f4b3e8dd2e42410732d0faa10ed7d.png) 
     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  ![](https://espresso.codeforces.com/66bd65c0272b8548a9e44eba22de8e32b395e0e2.png)