B. Reversing Encryption

Codeforces

IDCF999B

Time1000ms

Memory256MB

Difficulty—

implementation

English · Original

Chinese · Translation

Formal · Original

A string $s$ of length $n$ can be encrypted by the following algorithm: * iterate over all divisors of $n$ in decreasing order (i.e. from $n$ to $1$), * for each divisor $d$, reverse the substring $s[1 \dots d]$ (i.e. the substring which starts at position $1$ and ends at position $d$). For example, the above algorithm applied to the string $s$\="_codeforces_" leads to the following changes: "_codeforces_" $\to$ "_secrofedoc_" $\to$ "_orcesfedoc_" $\to$ "_rocesfedoc_" $\to$ "_rocesfedoc_" (obviously, the last reverse operation doesn't change the string because $d=1$). You are given the encrypted string $t$. Your task is to decrypt this string, i.e., to find a string $s$ such that the above algorithm results in string $t$. It can be proven that this string $s$ always exists and is unique. ## Input The first line of input consists of a single integer $n$ ($1 \le n \le 100$) — the length of the string $t$. The second line of input consists of the string $t$. The length of $t$ is $n$, and it consists only of lowercase Latin letters. ## Output Print a string $s$ such that the above algorithm results in $t$. [samples] ## Note The first example is described in the problem statement.

长度为 $n$ 的字符串 $s$ 可以通过以下算法加密：例如，将上述算法应用于字符串 $s$="_codeforces_" 会得到以下变化："_codeforces_" $arrow.r$ "_secrofedoc_" $arrow.r$ "_orcesfedoc_" $arrow.r$ "_rocesfedoc_" $arrow.r$ "_rocesfedoc_"（显然，最后一次反转操作不会改变字符串，因为 $d = 1$）。给你一个加密后的字符串 $t$。你的任务是解密这个字符串，即找到一个字符串 $s$，使得上述算法的结果为字符串 $t$。可以证明，这样的字符串 $s$ 总是存在且唯一。输入的第一行包含一个整数 $n$（$1 lt.eq n lt.eq 100$）——字符串 $t$ 的长度。第二行包含字符串 $t$。$t$ 的长度为 $n$，且仅由小写拉丁字母组成。请输出一个字符串 $s$，使得上述算法的结果为 $t$。第一个示例已在题目描述中给出。 ## Input 输入的第一行包含一个整数 $n$（$1 lt.eq n lt.eq 100$）——字符串 $t$ 的长度。第二行包含字符串 $t$。$t$ 的长度为 $n$，且仅由小写拉丁字母组成。 ## Output 请输出一个字符串 $s$，使得上述算法的结果为 $t$。 [samples] ## Note 第一个示例已在题目描述中给出。

Let $ n \in \mathbb{N} $, $ 1 \leq n \leq 100 $, and let $ t \in \Sigma^n $, where $ \Sigma = \{a, b, \dots, z\} $, be the encrypted string. Define the encryption algorithm $ E: \Sigma^n \to \Sigma^n $ as follows: Let $ s \in \Sigma^n $ be the original string. For $ k = 1 $ to $ n $: Let $ d = \left\lfloor \frac{n - k}{2} \right\rfloor + 1 $. Reverse the substring $ s[d : n - d + 1] $ (1-indexed). Then $ t = E(s) $. Given $ t $, find the unique $ s \in \Sigma^n $ such that $ E(s) = t $. Equivalently, define the inverse algorithm $ E^{-1} $: For $ k = n $ down to $ 1 $: Let $ d = \left\lfloor \frac{n - k}{2} \right\rfloor + 1 $. Reverse the substring $ t[d : n - d + 1] $ (1-indexed). Then $ s = E^{-1}(t) $. **Objective:** Compute $ s = E^{-1}(t) $.

Samples

Input #1

10
rocesfedoc

Output #1

codeforces

Input #2

16
plmaetwoxesisiht

Output #2

thisisexampletwo

Input #3

1
z

Output #3

API Response (JSON)

{
  "problem": {
    "name": "B. Reversing Encryption",
    "description": {
      "content": "A string $s$ of length $n$ can be encrypted by the following algorithm: *   iterate over all divisors of $n$ in decreasing order (i.e. from $n$ to $1$), *   for each divisor $d$, reverse the substrin",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF999B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "A string $s$ of length $n$ can be encrypted by the following algorithm:\n\n*   iterate over all divisors of $n$ in decreasing order (i.e. from $n$ to $1$),\n*   for each divisor $d$, reverse the substrin...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "长度为 $n$ 的字符串 $s$ 可以通过以下算法加密：\n\n例如，将上述算法应用于字符串 $s$=\"_codeforces_\" 会得到以下变化：\"_codeforces_\" $arrow.r$ \"_secrofedoc_\" $arrow.r$ \"_orcesfedoc_\" $arrow.r$ \"_rocesfedoc_\" $arrow.r$ \"_rocesfedoc_\"（显然，最后一次反转操作不会...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ n \\in \\mathbb{N} $, $ 1 \\leq n \\leq 100 $, and let $ t \\in \\Sigma^n $, where $ \\Sigma = \\{a, b, \\dots, z\\} $, be the encrypted string.\n\nDefine the encryption algorithm $ E: \\Sigma^n \\to \\Sigma^n...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments