D. AB-Strings

Codeforces

IDCF1012D

Time1000ms

Memory256MB

Difficulty—

constructive algorithmsstrings

English · Original

Chinese · Translation

Formal · Original

There are two strings _s_ and _t_, consisting only of letters _a_ and _b_. You can make the following operation several times: choose a prefix of _s_, a prefix of _t_ and swap them. Prefixes can be empty, also a prefix can coincide with a whole string. Your task is to find a sequence of operations after which one of the strings consists only of _a_ letters and the other consists only of _b_ letters. The number of operations should be minimized. ## Input The first line contains a string _s_ (1 ≤ |_s_| ≤ 2·105). The second line contains a string _t_ (1 ≤ |_t_| ≤ 2·105). Here |_s_| and |_t_| denote the lengths of _s_ and _t_, respectively. It is guaranteed that at least one of the strings contains at least one _a_ letter and at least one of the strings contains at least one _b_ letter. ## Output The first line should contain a single integer _n_ (0 ≤ _n_ ≤ 5·105) — the number of operations. Each of the next _n_ lines should contain two space-separated integers _a__i_, _b__i_ — the lengths of prefixes of _s_ and _t_ to swap, respectively. If there are multiple possible solutions, you can print any of them. It's guaranteed that a solution with given constraints exists. [samples] ## Note In the first example, you can solve the problem in two operations: 1. Swap the prefix of the first string with length 1 and the prefix of the second string with length 0. After this swap, you'll have strings _ab_ and _bbb_. 2. Swap the prefix of the first string with length 1 and the prefix of the second string with length 3. After this swap, you'll have strings _bbbb_ and _a_. In the second example, the strings are already appropriate, so no operations are needed.

有两个仅由字母 _a_ 和 _b_ 组成的字符串 #cf_span[s] 和 #cf_span[t]。你可以进行如下操作若干次：选择 #cf_span[s] 的一个前缀和 #cf_span[t] 的一个前缀，并交换它们。前缀 #cf_span(class=[tex-font-style-underline], body=[可以为空])，前缀也可以与整个字符串重合。你的任务是找到一个操作序列，使得操作后其中一个字符串仅包含 _a_ 字母，另一个字符串仅包含 _b_ 字母。操作次数应被 #cf_span(class=[tex-font-style-underline], body=[最小化])。第一行包含一个字符串 #cf_span[s] (#cf_span[1 ≤ |s| ≤ 2·105])。第二行包含一个字符串 #cf_span[t] (#cf_span[1 ≤ |t| ≤ 2·105])。这里 #cf_span[|s|] 和 #cf_span[|t|] 分别表示 #cf_span[s] 和 #cf_span[t] 的长度。保证至少有一个字符串包含至少一个 _a_ 字母，且至少有一个字符串包含至少一个 _b_ 字母。第一行应包含一个整数 #cf_span[n] (#cf_span[0 ≤ n ≤ 5·105]) —— 操作次数。接下来的 #cf_span[n] 行，每行包含两个用空格分隔的整数 #cf_span[ai], #cf_span[bi] —— 分别表示要交换的 #cf_span[s] 和 #cf_span[t] 的前缀长度。如果有多个可能的解，你可以输出任意一个。题目保证在给定约束下存在解。在第一个例子中，你可以用两次操作解决该问题：在第二个例子中，字符串已经符合要求，因此不需要任何操作。 ## Input 第一行包含一个字符串 #cf_span[s] (#cf_span[1 ≤ |s| ≤ 2·105])。第二行包含一个字符串 #cf_span[t] (#cf_span[1 ≤ |t| ≤ 2·105])。这里 #cf_span[|s|] 和 #cf_span[|t|] 分别表示 #cf_span[s] 和 #cf_span[t] 的长度。保证至少有一个字符串包含至少一个 _a_ 字母，且至少有一个字符串包含至少一个 _b_ 字母。 ## Output 第一行应包含一个整数 #cf_span[n] (#cf_span[0 ≤ n ≤ 5·105]) —— 操作次数。接下来的 #cf_span[n] 行，每行包含两个用空格分隔的整数 #cf_span[ai], #cf_span[bi] —— 分别表示要交换的 #cf_span[s] 和 #cf_span[t] 的前缀长度。如果有多个可能的解，你可以输出任意一个。题目保证在给定约束下存在解。 [samples] ## Note 在第一个例子中，你可以用两次操作解决该问题：交换第一个字符串长度为 #cf_span[1] 的前缀和第二个字符串长度为 #cf_span[0] 的前缀。交换后，你将得到字符串 _ab_ 和 _bbb_。再交换第一个字符串长度为 #cf_span[1] 的前缀和第二个字符串长度为 #cf_span[3] 的前缀。交换后，你将得到字符串 _bbbb_ 和 _a_。在第二个例子中，字符串已经符合要求，因此不需要任何操作。

**Definitions** Let $ s, t \in \{a, b\}^* $ be two input strings. Let $ n_s = |s| $, $ n_t = |t| $ denote their lengths. **Constraints** 1. $ 1 \leq n_s, n_t \leq 2 \cdot 10^5 $ 2. At least one of $ s, t $ contains at least one $ a $. 3. At least one of $ s, t $ contains at least one $ b $. **Objective** Find a sequence of operations minimizing the number of steps, where each operation consists of: - Choosing a prefix $ s[1..i] $ of $ s $ (with $ 0 \leq i \leq n_s $) - Choosing a prefix $ t[1..j] $ of $ t $ (with $ 0 \leq j \leq n_t $) - Swapping $ s[1..i] $ with $ t[1..j] $ Such that, after all operations, one string contains only $ a $'s and the other contains only $ b $'s. **Output** The minimal number of operations $ n $, followed by $ n $ pairs $ (a_i, b_i) $, where $ a_i $ and $ b_i $ are the lengths of the prefixes of $ s $ and $ t $ swapped in the $ i $-th operation.

Samples

Input #1

bab
bb

Output #1

2
1 0
1 3

Input #2

bbbb
aaa

Output #2

API Response (JSON)

{
  "problem": {
    "name": "D. AB-Strings",
    "description": {
      "content": "There are two strings _s_ and _t_, consisting only of letters _a_ and _b_. You can make the following operation several times: choose a prefix of _s_, a prefix of _t_ and swap them. Prefixes can be em",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF1012D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are two strings _s_ and _t_, consisting only of letters _a_ and _b_. You can make the following operation several times: choose a prefix of _s_, a prefix of _t_ and swap them. Prefixes can be em...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "有两个仅由字母 _a_ 和 _b_ 组成的字符串 #cf_span[s] 和 #cf_span[t]。你可以进行如下操作若干次：选择 #cf_span[s] 的一个前缀和 #cf_span[t] 的一个前缀，并交换它们。前缀 #cf_span(class=[tex-font-style-underline], body=[可以为空])，前缀也可以与整个字符串重合。\n\n你的任务是找到一个操作序列，使...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ s, t \\in \\{a, b\\}^* $ be two input strings.  \nLet $ n_s = |s| $, $ n_t = |t| $ denote their lengths.  \n\n**Constraints**  \n1. $ 1 \\leq n_s, n_t \\leq 2 \\cdot 10^5 $  \n2. At least...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments