B. Cubes for Masha

Codeforces

IDCF887B

Time1000ms

Memory256MB

Difficulty—

brute forceimplementation

English · Original

Chinese · Translation

Formal · Original

Absent-minded Masha got set of _n_ cubes for her birthday. At each of 6 faces of each cube, there is exactly one digit from 0 to 9. Masha became interested what is the largest natural _x_ such she can make using her new cubes all integers from 1 to _x_. To make a number Masha can rotate her cubes and put them in a row. After that, she looks at upper faces of cubes from left to right and reads the number. The number can't contain leading zeros. It's not required to use all cubes to build a number. Pay attention: Masha can't make digit 6 from digit 9 and vice-versa using cube rotations. ## Input In first line integer _n_ is given (1 ≤ _n_ ≤ 3) — the number of cubes, Masha got for her birthday. Each of next _n_ lines contains 6 integers _a__i__j_ (0 ≤ _a__i__j_ ≤ 9) — number on _j_\-th face of _i_\-th cube. ## Output Print single integer — maximum number _x_ such Masha can make any integers from 1 to _x_ using her cubes or 0 if Masha can't make even 1. [samples] ## Note In the first test case, Masha can build all numbers from 1 to 87, but she can't make 88 because there are no two cubes with digit 8.

心不在焉的玛莎收到了一组 #cf_span[n] 个立方体作为生日礼物。每个立方体的 6 个面上各有一个数字 0 到 9。玛莎想知道，她能用这些立方体拼出从 1 到 #cf_span[x] 的所有整数时，最大的自然数 #cf_span[x] 是多少。为了组成一个数字，玛莎可以旋转立方体并将它们排成一行，然后从左到右读取每个立方体朝上的面的数字。组成的数字不能包含前导零。不需要使用所有立方体来组成一个数字。注意：玛莎不能通过旋转立方体将数字 6 变成 9，或反之亦然。第一行给出整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 3]）——玛莎收到的立方体数量。接下来的 #cf_span[n] 行，每行包含 6 个整数 #cf_span[aij]（#cf_span[0 ≤ aij ≤ 9]）——表示第 #cf_span[i] 个立方体的第 #cf_span[j] 个面上的数字。输出一个整数：最大的 #cf_span[x]，使得玛莎能用她的立方体拼出从 1 到 #cf_span[x] 的所有整数；如果玛莎连 1 都无法拼出，则输出 0。在第一个测试用例中，玛莎可以拼出从 1 到 87 的所有数字，但她无法拼出 88，因为没有两个立方体同时含有数字 8。 ## Input 第一行给出整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 3]）——玛莎收到的立方体数量。接下来的 #cf_span[n] 行，每行包含 6 个整数 #cf_span[aij]（#cf_span[0 ≤ aij ≤ 9]）——表示第 #cf_span[i] 个立方体的第 #cf_span[j] 个面上的数字。 ## Output 输出一个整数：最大的 #cf_span[x]，使得玛莎能用她的立方体拼出从 1 到 #cf_span[x] 的所有整数；如果玛莎连 1 都无法拼出，则输出 0。 [samples] ## Note 在第一个测试用例中，玛莎可以拼出从 1 到 87 的所有数字，但她无法拼出 88，因为没有两个立方体同时含有数字 8。

Let $ n \in \{1, 2, 3\} $ be the number of cubes. Each cube $ i \in \{1, \dots, n\} $ has a set $ C_i \subseteq \{0, 1, \dots, 9\} $ of digits on its six faces. Let $ S = \bigcup_{i=1}^n C_i $ be the union of all available digits. For a natural number $ x $, denote by $ D(x) $ the multiset of digits in its decimal representation (without leading zeros). Define a function $ \text{canForm}(x) $: $ \text{canForm}(x) = \text{True} $ if and only if there exists an injection $ f: D(x) \to \{1, \dots, n\} $ such that for each digit $ d \in D(x) $, $ d \in C_{f(d)} $, and no two digits in $ D(x) $ are mapped to the same cube. Let $ x^* = \max \{ x \in \mathbb{N} \mid \forall y \in \{1, 2, \dots, x\}, \text{canForm}(y) = \text{True} \} $. If $ \text{canForm}(1) = \text{False} $, then $ x^* = 0 $. Output $ x^* $.

Samples

Input #1

3
0 1 2 3 4 5
6 7 8 9 0 1
2 3 4 5 6 7

Output #1

Input #2

3
0 1 3 5 6 8
1 2 4 5 7 8
2 3 4 6 7 9

Output #2

API Response (JSON)

{
  "problem": {
    "name": "B. Cubes for Masha",
    "description": {
      "content": "Absent-minded Masha got set of _n_ cubes for her birthday. At each of 6 faces of each cube, there is exactly one digit from 0 to 9. Masha became interested what is the largest natural _x_ such she ca",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF887B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Absent-minded Masha got set of _n_ cubes for her birthday.\n\nAt each of 6 faces of each cube, there is exactly one digit from 0 to 9. Masha became interested what is the largest natural _x_ such she ca...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "心不在焉的玛莎收到了一组 #cf_span[n] 个立方体作为生日礼物。\n\n每个立方体的 6 个面上各有一个数字 0 到 9。玛莎想知道，她能用这些立方体拼出从 1 到 #cf_span[x] 的所有整数时，最大的自然数 #cf_span[x] 是多少。\n\n为了组成一个数字，玛莎可以旋转立方体并将它们排成一行，然后从左到右读取每个立方体朝上的面的数字。\n\n组成的数字不能包含前导零。不需要使用所有立...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ n \\in \\{1, 2, 3\\} $ be the number of cubes.  \nEach cube $ i \\in \\{1, \\dots, n\\} $ has a set $ C_i \\subseteq \\{0, 1, \\dots, 9\\} $ of digits on its six faces.\n\nLet $ S = \\bigcup_{i=1}^n C_i $ be t...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments