B. Sherlock and his girlfriend

Codeforces

IDCF776B

Time1000ms

Memory256MB

Difficulty—

constructive algorithmsnumber theory

English · Original

Chinese · Translation

Formal · Original

Sherlock has a new girlfriend (so unlike him!). Valentine's day is coming and he wants to gift her some jewelry. He bought _n_ pieces of jewelry. The _i_\-th piece has price equal to _i_ + 1, that is, the prices of the jewelry are 2, 3, 4, ... _n_ + 1. Watson gave Sherlock a challenge to color these jewelry pieces such that two pieces don't have the same color if the price of one piece is a prime divisor of the price of the other piece. Also, Watson asked him to minimize the number of different colors used. Help Sherlock complete this trivial task. ## Input The only line contains single integer _n_ (1 ≤ _n_ ≤ 100000) — the number of jewelry pieces. ## Output The first line of output should contain a single integer _k_, the minimum number of colors that can be used to color the pieces of jewelry with the given constraints. The next line should consist of _n_ space-separated integers (between 1 and _k_) that specify the color of each piece in the order of increasing price. If there are multiple ways to color the pieces using _k_ colors, you can output any of them. [samples] ## Note In the first input, the colors for first, second and third pieces of jewelry having respective prices 2, 3 and 4 are 1, 1 and 2 respectively. In this case, as 2 is a prime divisor of 4, colors of jewelry having prices 2 and 4 must be distinct.

Sherlock 有了一个新女朋友（这可真不像他！）。情人节快到了，他想送她一些珠宝。他买了 #cf_span[n] 件珠宝。第 #cf_span[i] 件珠宝的价格为 #cf_span[i + 1]，即珠宝的价格为 #cf_span[2, 3, 4, ... n + 1]。 Watson 给 Sherlock 一个挑战：将这些珠宝染色，使得如果一件珠宝的价格是另一件珠宝价格的质因数，则这两件珠宝不能有相同的颜色。同时，Watson 要求他最小化使用的不同颜色数量。请帮助 Sherlock 完成这个简单的任务。输入仅包含一行，一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 100000]）——珠宝的数量。输出的第一行应包含一个整数 #cf_span[k]，表示在满足上述约束条件下可使用的最少颜色数。第二行应包含 #cf_span[n] 个用空格分隔的整数（范围在 #cf_span[1] 到 #cf_span[k] 之间），按价格递增顺序指定每件珠宝的颜色。如果存在多种使用 #cf_span[k] 种颜色的染色方案，输出任意一种即可。在第一个输入中，价格分别为 #cf_span[2]、#cf_span[3] 和 #cf_span[4] 的第一、第二和第三件珠宝的颜色分别为 #cf_span[1]、#cf_span[1] 和 #cf_span[2]。在这种情况下，由于 #cf_span[2] 是 #cf_span[4] 的质因数，因此价格为 #cf_span[2] 和 #cf_span[4] 的珠宝颜色必须不同。 ## Input 输入仅包含一行，一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 100000]）——珠宝的数量。 ## Output 输出的第一行应包含一个整数 #cf_span[k]，表示在满足上述约束条件下可使用的最少颜色数。第二行应包含 #cf_span[n] 个用空格分隔的整数（范围在 #cf_span[1] 到 #cf_span[k] 之间），按价格递增顺序指定每件珠宝的颜色。如果存在多种使用 #cf_span[k] 种颜色的染色方案，输出任意一种即可。 [samples] ## Note 在第一个输入中，价格分别为 #cf_span[2]、#cf_span[3] 和 #cf_span[4] 的第一、第二和第三件珠宝的颜色分别为 #cf_span[1]、#cf_span[1] 和 #cf_span[2]。在这种情况下，由于 #cf_span[2] 是 #cf_span[4] 的质因数，因此价格为 #cf_span[2] 和 #cf_span[4] 的珠宝颜色必须不同。

**Definitions** Let $ n \in \mathbb{Z}^+ $ with $ 1 \leq n \leq 100000 $. Let $ P = \{p_1, p_2, \dots, p_n\} $ where $ p_i = i + 1 $, i.e., $ P = \{2, 3, 4, \dots, n+1\} $. **Constraints** For any two distinct elements $ a, b \in P $, if there exists a prime $ q $ such that $ q \mid a $ and $ q \mid b $, then $ a $ and $ b $ must be assigned different colors **if** one is a prime divisor of the other. More precisely: if $ a, b \in P $, $ a \neq b $, and $ \exists $ prime $ q $ such that $ q \mid a $ and $ q \mid b $, **and** either $ a = q $ and $ q \mid b $, or $ b = q $ and $ q \mid a $, then $ \text{color}(a) \neq \text{color}(b) $. **Objective** Minimize the number of colors $ k $ such that a coloring $ c: P \to \{1, 2, \dots, k\} $ exists satisfying the above constraint. Output $ k $ and a valid coloring $ c(p_1), c(p_2), \dots, c(p_n) $.

Samples

Input #1

Output #1

2
1 1 2

Input #2

Output #2

2
2 1 1 2

API Response (JSON)

{
  "problem": {
    "name": "B. Sherlock and his girlfriend",
    "description": {
      "content": "Sherlock has a new girlfriend (so unlike him!). Valentine's day is coming and he wants to gift her some jewelry. He bought _n_ pieces of jewelry. The _i_\\-th piece has price equal to _i_ + 1, that is",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF776B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Sherlock has a new girlfriend (so unlike him!). Valentine's day is coming and he wants to gift her some jewelry.\n\nHe bought _n_ pieces of jewelry. The _i_\\-th piece has price equal to _i_ + 1, that is...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Sherlock 有了一个新女朋友（这可真不像他！）。情人节快到了，他想送她一些珠宝。\n\n他买了 #cf_span[n] 件珠宝。第 #cf_span[i] 件珠宝的价格为 #cf_span[i + 1]，即珠宝的价格为 #cf_span[2, 3, 4, ... n + 1]。\n\nWatson 给 Sherlock 一个挑战：将这些珠宝染色，使得如果一件珠宝的价格是另一件珠宝价格的质因数，则这两...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ with $ 1 \\leq n \\leq 100000 $.  \nLet $ P = \\{p_1, p_2, \\dots, p_n\\} $ where $ p_i = i + 1 $, i.e., $ P = \\{2, 3, 4, \\dots, n+1\\} $.\n\n**Constraints**  \nFor ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments