F. AB-Strings

Codeforces

IDCF1013F

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 over the alphabet $\{a, b\}$. Let $ n = |s| $, $ m = |t| $. **Constraints** 1. $ 1 \leq |s| \leq 2 \cdot 10^5 $, $ 1 \leq |t| \leq 2 \cdot 10^5 $ 2. At least one of $ s, t $ contains at least one $ a $, and at least one contains at least one $ b $. **Objective** Find a sequence of operations minimizing the number of steps, where each operation consists of selecting prefixes $ s[1..i] $ and $ t[1..j] $ (with $ 0 \leq i \leq |s| $, $ 0 \leq j \leq |t| $) and swapping them, such that after all operations: - One string contains only $ a $'s, - The other contains only $ b $'s. **Output** A sequence of $ n $ operations $ (a_1, b_1), (a_2, b_2), \dots, (a_n, b_n) $, where each $ a_k \in [0, |s|] $, $ b_k \in [0, |t|] $, representing the prefix lengths swapped in step $ k $.

Samples

Input #1

bab
bb

Output #1

2
1 0
1 3

Input #2

bbbb
aaa

Output #2

API Response (JSON)

{
  "problem": {
    "name": "F. 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": "CF1013F"
  },
  "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 over the alphabet $\\{a, b\\}$.  \nLet $ n = |s| $, $ m = |t| $.  \n\n**Constraints**  \n1. $ 1 \\leq |s| \\leq 2 \\cdot 10^5 $, $ 1 \\leq |t| ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments