B. Polycarp's phone book

Codeforces

IDCF860B

Time4000ms

Memory256MB

Difficulty—

brute forcedata structureshashingimplementationstrings

English · Original

Chinese · Translation

Formal · Original

There are _n_ phone numbers in Polycarp's contacts on his phone. Each number is a 9-digit integer, starting with a digit different from 0. All the numbers are distinct. There is the latest version of Berdroid OS installed on Polycarp's phone. If some number is entered, is shows up all the numbers in the contacts for which there is a substring equal to the entered sequence of digits. For example, is there are three phone numbers in Polycarp's contacts: 123456789, 100000000 and 100123456, then: * if he enters 00 two numbers will show up: 100000000 and 100123456, * if he enters 123 two numbers will show up 123456789 and 100123456, * if he enters 01 there will be only one number 100123456. For each of the phone numbers in Polycarp's contacts, find the minimum in length sequence of digits such that if Polycarp enters this sequence, Berdroid shows this only phone number. ## Input The first line contains single integer _n_ (1 ≤ _n_ ≤ 70000) — the total number of phone contacts in Polycarp's contacts. The phone numbers follow, one in each line. Each number is a positive 9-digit integer starting with a digit from 1 to 9. All the numbers are distinct. ## Output Print exactly _n_ lines: the _i_\-th of them should contain the shortest non-empty sequence of digits, such that if Polycarp enters it, the Berdroid OS shows up only the _i_\-th number from the contacts. If there are several such sequences, print any of them. [samples]

Polycarp 的手机通讯录中有 #cf_span[n] 个电话号码。每个号码是一个 9 位整数，且首位数字不为 #cf_span[0]。所有号码互不相同。 Polycarp 的手机安装了最新版本的 Berdroid 操作系统。当输入某个数字序列时，系统会显示通讯录中所有包含该序列作为子串的电话号码。例如，若 Polycarp 的通讯录中有三个号码：#cf_span[123456789]、#cf_span[100000000] 和 #cf_span[100123456]，则：对于 Polycarp 通讯录中的每个电话号码，找出最短的数字序列，使得当 Polycarp 输入该序列时，Berdroid 系统仅显示该号码。第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 70000]) —— Polycarp 通讯录中电话号码的总数。接下来每行一个电话号码。每个号码是一个正的 9 位整数，首位数字在 #cf_span[1] 到 #cf_span[9] 之间。所有号码互不相同。请输出恰好 #cf_span[n] 行：第 #cf_span[i] 行应包含一个最短的非空数字序列，使得当 Polycarp 输入该序列时，Berdroid 系统仅显示通讯录中的第 #cf_span[i] 个号码。如果有多个这样的序列，输出任意一个即可。 ## Input 第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 70000]) —— Polycarp 通讯录中电话号码的总数。接下来每行一个电话号码。每个号码是一个正的 9 位整数，首位数字在 #cf_span[1] 到 #cf_span[9] 之间。所有号码互不相同。 ## Output 请输出恰好 #cf_span[n] 行：第 #cf_span[i] 行应包含一个最短的非空数字序列，使得当 Polycarp 输入该序列时，Berdroid 系统仅显示通讯录中的第 #cf_span[i] 个号码。如果有多个这样的序列，输出任意一个即可。 [samples]

**Definitions** Let $ n \in \mathbb{Z} $, $ 1 \leq n \leq 70000 $, be the number of phone contacts. Let $ P = \{p_1, p_2, \dots, p_n\} $ be a set of distinct 9-digit strings, where each $ p_i \in \{1,2,\dots,9\} \times \{0,1,\dots,9\}^8 $. For any string $ s \in \{0,1,\dots,9\}^* $, define $ \text{Match}(s) = \{ p \in P \mid s \text{ is a contiguous substring of } p \} $. **Constraints** All $ p_i $ are distinct and have exactly 9 digits, with first digit $ \neq 0 $. **Objective** For each $ i \in \{1, \dots, n\} $, find a shortest non-empty substring $ s_i \subseteq p_i $ such that: $$ \text{Match}(s_i) = \{p_i\} $$ Output any such $ s_i $ for each $ i $.

Samples

Input #1

Output #1

9
000
01

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "B. Polycarp's phone book",
    "description": {
      "content": "There are _n_ phone numbers in Polycarp's contacts on his phone. Each number is a 9-digit integer, starting with a digit different from 0. All the numbers are distinct. There is the latest version of",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF860B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are _n_ phone numbers in Polycarp's contacts on his phone. Each number is a 9-digit integer, starting with a digit different from 0. All the numbers are distinct.\n\nThere is the latest version of...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Polycarp 的手机通讯录中有 #cf_span[n] 个电话号码。每个号码是一个 9 位整数，且首位数字不为 #cf_span[0]。所有号码互不相同。\n\nPolycarp 的手机安装了最新版本的 Berdroid 操作系统。当输入某个数字序列时，系统会显示通讯录中所有包含该序列作为子串的电话号码。例如，若 Polycarp 的通讯录中有三个号码：#cf_span[123456789]、#c...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $, $ 1 \\leq n \\leq 70000 $, be the number of phone contacts.  \nLet $ P = \\{p_1, p_2, \\dots, p_n\\} $ be a set of distinct 9-digit strings, where each $ p_i \\in ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments