C. Permutation Cycle

Codeforces

IDCF932C

Time2000ms

Memory256MB

Difficulty—

brute forceconstructive algorithms

English · Original

Chinese · Translation

Formal · Original

For a permutation _P_\[1... _N_\] of integers from 1 to _N_, function _f_ is defined as follows: Let _g_(_i_) be the minimum positive integer _j_ such that _f_(_i_, _j_) = _i_. We can show such _j_ always exists. For given _N_, _A_, _B_, find a permutation _P_ of integers from 1 to _N_ such that for 1 ≤ _i_ ≤ _N_, _g_(_i_) equals either _A_ or _B_. ## Input The only line contains three integers _N_, _A_, _B_ (1 ≤ _N_ ≤ 106, 1 ≤ _A_, _B_ ≤ _N_). ## Output If no such permutation exists, output _\-1_. Otherwise, output a permutation of integers from 1 to _N_. [samples] ## Note In the first example, _g_(1) = _g_(6) = _g_(7) = _g_(9) = 2 and _g_(2) = _g_(3) = _g_(4) = _g_(5) = _g_(8) = 5 In the second example, _g_(1) = _g_(2) = _g_(3) = 1

对于整数 $1$ 到 $N$ 的一个排列 $P[1... N]$，函数 $f$ 定义如下：令 $g(i)$ 为满足 $f(i, j) = i$ 的最小正整数 $j$。我们可以证明这样的 $j$ 总是存在。给定 $N, A, B$，请找出一个 $1$ 到 $N$ 的排列 $P$，使得对所有 $1 ≤ i ≤ N$，$g(i)$ 等于 $A$ 或 $B$ 之一。输入仅一行，包含三个整数 $N, A, B$（$1 ≤ N ≤ 10^6, 1 ≤ A, B ≤ N$）。如果不存在这样的排列，请输出 _-1_。否则，请输出一个 $1$ 到 $N$ 的排列。在第一个例子中，$g(1) = g(6) = g(7) = g(9) = 2$ 且 $g(2) = g(3) = g(4) = g(5) = g(8) = 5$。在第二个例子中，$g(1) = g(2) = g(3) = 1$。 ## Input 输入仅一行，包含三个整数 $N, A, B$（$1 ≤ N ≤ 10^6, 1 ≤ A, B ≤ N$）。 ## Output 如果不存在这样的排列，请输出 _-1_。否则，请输出一个 $1$ 到 $N$ 的排列。 [samples] ## Note 在第一个例子中，$g(1) = g(6) = g(7) = g(9) = 2$ 且 $g(2) = g(3) = g(4) = g(5) = g(8) = 5$。在第二个例子中，$g(1) = g(2) = g(3) = 1$。

**Definitions** Let $ N, A, B \in \mathbb{Z}^+ $ with $ 1 \leq N \leq 10^6 $, $ 1 \leq A, B \leq N $. Let $ P = (P[1], P[2], \dots, P[N]) $ be a permutation of $ \{1, 2, \dots, N\} $. Define $ f(i, j) $ as the result of applying the permutation $ P $ iteratively $ j $ times starting from $ i $: $$ f(i, 1) = P[i], \quad f(i, j) = P[f(i, j-1)] \text{ for } j > 1. $$ Define $ g(i) $ as the smallest positive integer $ j $ such that $ f(i, j) = i $ — i.e., the cycle length containing $ i $ in the functional graph of $ P $. **Constraints** For all $ i \in \{1, 2, \dots, N\} $, $ g(i) \in \{A, B\} $. **Objective** Find a permutation $ P $ such that every element lies in a cycle of length either $ A $ or $ B $. If no such permutation exists, output $-1$. Otherwise, output any such permutation $ P $.

Samples

Input #1

9 2 5

Output #1

6 5 8 3 4 1 9 2 7

Input #2

3 2 1

Output #2

1 2 3

API Response (JSON)

{
  "problem": {
    "name": "C. Permutation Cycle",
    "description": {
      "content": "For a permutation _P_\\[1... _N_\\] of integers from 1 to _N_, function _f_ is defined as follows: Let _g_(_i_) be the minimum positive integer _j_ such that _f_(_i_, _j_) = _i_. We can show such _j_ a",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF932C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "For a permutation _P_\\[1... _N_\\] of integers from 1 to _N_, function _f_ is defined as follows:\n\nLet _g_(_i_) be the minimum positive integer _j_ such that _f_(_i_, _j_) = _i_. We can show such _j_ a...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "对于整数 $1$ 到 $N$ 的一个排列 $P[1... N]$，函数 $f$ 定义如下：\n\n令 $g(i)$ 为满足 $f(i, j) = i$ 的最小正整数 $j$。我们可以证明这样的 $j$ 总是存在。\n\n给定 $N, A, B$，请找出一个 $1$ 到 $N$ 的排列 $P$，使得对所有 $1 ≤ i ≤ N$，$g(i)$ 等于 $A$ 或 $B$ 之一。\n\n输入仅一行，包含三个整数 $...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N, A, B \\in \\mathbb{Z}^+ $ with $ 1 \\leq N \\leq 10^6 $, $ 1 \\leq A, B \\leq N $.  \nLet $ P = (P[1], P[2], \\dots, P[N]) $ be a permutation of $ \\{1, 2, \\dots, N\\} $.  \nDefine $ f...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments