D. Huge Strings

Codeforces

IDCF868D

Time2000ms

Memory256MB

Difficulty—

bitmasksbrute forcedpimplementationstrings

English · Original

Chinese · Translation

Formal · Original

You are given _n_ strings _s_1, _s_2, ..., _s__n_ consisting of characters 0 and 1. _m_ operations are performed, on each of them you concatenate two existing strings into a new one. On the _i_\-th operation the concatenation _s__a__i__s__b__i_ is saved into a new string _s__n_ + _i_ (the operations are numbered starting from 1). After each operation you need to find the maximum positive integer _k_ such that all possible strings consisting of 0 and 1 of length _k_ (there are 2_k_ such strings) are substrings of the new string. If there is no such _k_, print 0. ## Input The first line contains single integer _n_ (1 ≤ _n_ ≤ 100) — the number of strings. The next _n_ lines contain strings _s_1, _s_2, ..., _s__n_ (1 ≤ |_s__i_| ≤ 100), one per line. The total length of strings is not greater than 100. The next line contains single integer _m_ (1 ≤ _m_ ≤ 100) — the number of operations. _m_ lines follow, each of them contains two integers _a__i_ abd _b__i_ (1 ≤ _a__i_, _b__i_ ≤ _n_ + _i_ - 1) — the number of strings that are concatenated to form _s__n_ + _i_. ## Output Print _m_ lines, each should contain one integer — the answer to the question after the corresponding operation. [samples] ## Note On the first operation, a new string "_0110_" is created. For _k_ = 1 the two possible binary strings of length _k_ are "_0_" and "_1_", they are substrings of the new string. For _k_ = 2 and greater there exist strings of length _k_ that do not appear in this string (for _k_ = 2 such string is "_00_"). So the answer is 1. On the second operation the string "_01100_" is created. Now all strings of length _k_ = 2 are present. On the third operation the string "_1111111111_" is created. There is no zero, so the answer is 0.

你被给定 #cf_span[n] 个由字符 #cf_span[0] 和 #cf_span[1] 组成的字符串 #cf_span[s1, s2, ..., sn]。执行 #cf_span[m] 次操作，每次操作将两个已有的字符串拼接成一个新的字符串。在第 #cf_span[i] 次操作中，拼接 #cf_span[saisbi] 得到的新字符串被保存为 #cf_span[sn + i]（操作编号从 #cf_span[1] 开始）。每次操作后，你需要找到最大的正整数 #cf_span[k]，使得所有长度为 #cf_span[k] 的由 #cf_span[0] 和 #cf_span[1] 组成的字符串（共有 #cf_span[2k] 个）都是新字符串的子串。如果不存在这样的 #cf_span[k]，则输出 #cf_span[0]。第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 100]) —— 字符串的数量。接下来的 #cf_span[n] 行每行包含一个字符串 #cf_span[s1, s2, ..., sn] (#cf_span[1 ≤ |si| ≤ 100])。所有字符串的总长度不超过 #cf_span[100]。接下来一行包含一个整数 #cf_span[m] (#cf_span[1 ≤ m ≤ 100]) —— 操作的数量。随后 #cf_span[m] 行，每行包含两个整数 #cf_span[ai] 和 #cf_span[bi] (#cf_span[1 ≤ ai, bi ≤ n + i - 1]) —— 用于拼接形成 #cf_span[sn + i] 的两个字符串的编号。请输出 #cf_span[m] 行，每行一个整数 —— 对应每次操作后的答案。在第一次操作中，生成了新字符串 "_0110_"。对于 #cf_span[k = 1]，所有长度为 #cf_span[k] 的二进制字符串是 "_0_" 和 "_1_"，它们都是新字符串的子串。对于 #cf_span[k = 2] 及更大的值，存在长度为 #cf_span[k] 的字符串未出现在该字符串中（例如，当 #cf_span[k = 2] 时，字符串 "_00_" 就不存在）。因此答案是 #cf_span[1]。在第二次操作中，生成了字符串 "_01100_"。此时所有长度为 #cf_span[k = 2] 的字符串均已出现。在第三次操作中，生成了字符串 "_1111111111_"。该字符串中没有字符 '0'，因此答案是 #cf_span[0]。 ## Input 第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 100]) —— 字符串的数量。接下来的 #cf_span[n] 行每行包含一个字符串 #cf_span[s1, s2, ..., sn] (#cf_span[1 ≤ |si| ≤ 100])。所有字符串的总长度不超过 #cf_span[100]。接下来一行包含一个整数 #cf_span[m] (#cf_span[1 ≤ m ≤ 100]) —— 操作的数量。随后 #cf_span[m] 行，每行包含两个整数 #cf_span[ai] 和 #cf_span[bi] (#cf_span[1 ≤ ai, bi ≤ n + i - 1]) —— 用于拼接形成 #cf_span[sn + i] 的两个字符串的编号。 ## Output 请输出 #cf_span[m] 行，每行一个整数 —— 对应每次操作后的答案。 [samples] ## Note 在第一次操作中，生成了新字符串 "_0110_"。对于 #cf_span[k = 1]，所有长度为 #cf_span[k] 的二进制字符串是 "_0_" 和 "_1_"，它们都是新字符串的子串。对于 #cf_span[k = 2] 及更大的值，存在长度为 #cf_span[k] 的字符串未出现在该字符串中（例如，当 #cf_span[k = 2] 时，字符串 "_00_" 就不存在）。因此答案是 #cf_span[1]。在第二次操作中，生成了字符串 "_01100_"。此时所有长度为 #cf_span[k = 2] 的字符串均已出现。在第三次操作中，生成了字符串 "_1111111111_"。该字符串中没有字符 '0'，因此答案是 #cf_span[0]。

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the initial number of binary strings. Let $ S = (s_1, s_2, \dots, s_n) $ be the initial sequence of strings, where each $ s_i \in \{0,1\}^* $. Let $ m \in \mathbb{Z}^+ $ be the number of operations. For $ i \in \{1, \dots, m\} $, operation $ i $ concatenates strings $ s_{a_i} $ and $ s_{b_i} $ to form $ s_{n+i} = s_{a_i} + s_{b_i} $. Let $ \mathcal{B}_k = \{0,1\}^k $ denote the set of all binary strings of length $ k $. **Constraints** 1. $ 1 \leq n \leq 100 $, $ 1 \leq m \leq 100 $ 2. $ 1 \leq |s_i| \leq 100 $ for $ i \in \{1, \dots, n\} $, total initial length $ \leq 100 $ 3. For each operation $ i $: $ 1 \leq a_i, b_i \leq n + i - 1 $ **Objective** After each operation $ i \in \{1, \dots, m\} $, compute the maximum integer $ k \geq 0 $ such that $ \mathcal{B}_k \subseteq \text{Substr}(s_{n+i}) $, where $ \text{Substr}(s) $ is the set of all contiguous substrings of $ s $. If no such $ k > 0 $ exists, output $ 0 $.

Samples

Input #1

Output #1

1
2
0

API Response (JSON)

{
  "problem": {
    "name": "D. Huge Strings",
    "description": {
      "content": "You are given _n_ strings _s_1, _s_2, ..., _s__n_ consisting of characters 0 and 1. _m_ operations are performed, on each of them you concatenate two existing strings into a new one. On the _i_\\-th op",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF868D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given _n_ strings _s_1, _s_2, ..., _s__n_ consisting of characters 0 and 1. _m_ operations are performed, on each of them you concatenate two existing strings into a new one. On the _i_\\-th op...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "你被给定 #cf_span[n] 个由字符 #cf_span[0] 和 #cf_span[1] 组成的字符串 #cf_span[s1, s2, ..., sn]。执行 #cf_span[m] 次操作，每次操作将两个已有的字符串拼接成一个新的字符串。在第 #cf_span[i] 次操作中，拼接 #cf_span[saisbi] 得到的新字符串被保存为 #cf_span[sn + i]（操作编号从 #...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the initial number of binary strings.  \nLet $ S = (s_1, s_2, \\dots, s_n) $ be the initial sequence of strings, where each $ s_i \\in \\{0,1\\}^* $.  \nLet $...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments