B. Petr and Permutations

Codeforces

IDCF986B

Time2000ms

Memory256MB

Difficulty—

combinatoricsmath

English · Original

Chinese · Translation

Formal · Original

Petr likes to come up with problems about randomly generated data. This time problem is about random permutation. He decided to generate a random permutation this way: he takes identity permutation of numbers from $1$ to $n$ and then $3n$ times takes a random pair of different elements and swaps them. Alex envies Petr and tries to imitate him in all kind of things. Alex has also come up with a problem about random permutation. He generates a random permutation just like Petr but swaps elements $7n+1$ times instead of $3n$ times. Because it is more random, OK?! You somehow get a test from one of these problems and now you want to know from which one. ## Input In the first line of input there is one integer $n$ ($10^{3} \le n \le 10^{6}$). In the second line there are $n$ distinct integers between $1$ and $n$ — the permutation of size $n$ from the test. It is guaranteed that all tests except for sample are generated this way: First we choose $n$ — the size of the permutation. Then we randomly choose a method to generate a permutation — the one of Petr or the one of Alex. Then we generate a permutation using chosen method. ## Output If the test is generated via Petr's method print "_Petr_" (without quotes). If the test is generated via Alex's method print "_Um_nik_" (without quotes). [samples] ## Note Please note that the sample is not a valid test (because of limitations for $n$) and is given only to illustrate input/output format. Your program **still has to print correct answer to this test** to get AC. Due to randomness of input hacks in this problem are forbidden.

Petr 喜欢设计关于随机生成数据的问题。这次的问题是关于随机排列的。他决定用以下方式生成一个随机排列：从数字 $1$ 到 $n$ 的单位排列开始，然后进行 $3 n$ 次操作，每次随机选取两个不同的元素并交换它们。Alex 羡慕 Petr，试图在所有方面模仿他。Alex 也设计了一个关于随机排列的问题。他生成随机排列的方式与 Petr 相同，但交换元素的次数是 $7 n + 1$ 次，而不是 $3 n$ 次。因为这样更随机，对吧？！你偶然得到了一个来自上述两个问题之一的测试用例，现在你需要判断它来自哪一个。输入的第一行包含一个整数 $n$（$10^3 lt.eq n lt.eq 10^6$）。第二行包含 $n$ 个介于 $1$ 到 $n$ 之间的互不相同的整数——来自测试用例的大小为 $n$ 的排列。保证除了样例之外的所有测试用例均按以下方式生成：首先选择排列的大小 $n$，然后随机选择一种生成排列的方法——Petr 的方法或 Alex 的方法，再用所选方法生成排列。如果测试用例是通过 Petr 的方法生成的，请输出 "_Petr_"（不含引号）。如果是通过 Alex 的方法生成的，请输出 "_Um_nik_"（不含引号）。请注意，样例不是一个合法的测试用例（因为 $n$ 的限制），仅用于说明输入/输出格式。你的程序*仍必须为该样例输出正确答案*才能通过。由于输入具有随机性，本题禁止黑客攻击。 ## Input 在输入的第一行有一个整数 $n$（$10^3 lt.eq n lt.eq 10^6$）。在第二行有 $n$ 个介于 $1$ 到 $n$ 之间的互不相同的整数——来自测试用例的大小为 $n$ 的排列。保证除了样例之外的所有测试用例均按以下方式生成：首先选择排列的大小 $n$，然后随机选择一种生成排列的方法——Petr 的方法或 Alex 的方法，再用所选方法生成排列。 ## Output 如果测试用例是通过 Petr 的方法生成的，请输出 "_Petr_"（不含引号）。如果是通过 Alex 的方法生成的，请输出 "_Um_nik_"（不含引号）。 [samples] ## Note 请注意，样例不是一个合法的测试用例（因为 $n$ 的限制），仅用于说明输入/输出格式。你的程序*仍必须为该样例输出正确答案*才能通过。由于输入具有随机性，本题禁止黑客攻击。

Let $ \pi $ be a permutation of $ \{1, 2, \dots, n\} $, obtained by starting from the identity permutation and applying $ k $ random transpositions (swaps of two distinct elements). Let $ c $ be the number of cycles in the cycle decomposition of $ \pi $. The parity of the permutation $ \pi $ is determined by the number of transpositions $ k $: - Each transposition changes the parity of the permutation. - The identity permutation has even parity (0 transpositions). - After $ k $ transpositions, the parity of $ \pi $ is $ k \mod 2 $. The number of cycles $ c $ in a permutation of $ n $ elements satisfies: $$ \text{parity of } \pi = (n - c) \mod 2 $$ Thus: $$ k \equiv n - c \pmod{2} $$ Given: - Petr uses $ k = 3n $ - Alex uses $ k = 7n + 1 $ Compute $ c $ from the input permutation. Then: - If $ 3n \equiv n - c \pmod{2} $, output "Petr" - Else, output "Um_nik" Simplify the parity conditions: For Petr: $ 3n \equiv n - c \pmod{2} \Rightarrow 2n \equiv -c \pmod{2} \Rightarrow 0 \equiv c \pmod{2} \Rightarrow c \text{ even} $ For Alex: $ 7n + 1 \equiv n - c \pmod{2} \Rightarrow 6n + 1 \equiv -c \pmod{2} \Rightarrow 1 \equiv -c \pmod{2} \Rightarrow c \equiv 1 \pmod{2} \Rightarrow c \text{ odd} $ Therefore: > If the number of cycles $ c $ in the permutation is even → Petr > If $ c $ is odd → Um_nik --- **Formal Output:** Let $ c $ be the number of cycles in the cycle decomposition of the given permutation. If $ c \equiv 0 \pmod{2} $, output "Petr". If $ c \equiv 1 \pmod{2} $, output "Um_nik".

Samples

Input #1

5
2 4 5 1 3

Output #1

Petr

API Response (JSON)

{
  "problem": {
    "name": "B. Petr and Permutations",
    "description": {
      "content": "Petr likes to come up with problems about randomly generated data. This time problem is about random permutation. He decided to generate a random permutation this way: he takes identity permutation of",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF986B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Petr likes to come up with problems about randomly generated data. This time problem is about random permutation. He decided to generate a random permutation this way: he takes identity permutation of...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Petr 喜欢设计关于随机生成数据的问题。这次的问题是关于随机排列的。他决定用以下方式生成一个随机排列：从数字 $1$ 到 $n$ 的单位排列开始，然后进行 $3 n$ 次操作，每次随机选取两个不同的元素并交换它们。Alex 羡慕 Petr，试图在所有方面模仿他。Alex 也设计了一个关于随机排列的问题。他生成随机排列的方式与 Petr 相同，但交换元素的次数是 $7 n + 1$ 次，而不是 $...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ \\pi $ be a permutation of $ \\{1, 2, \\dots, n\\} $, obtained by starting from the identity permutation and applying $ k $ random transpositions (swaps of two distinct elements).\n\nLet $ c $ be the ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments