D. Secure but True

Codeforces

IDCF10108D

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Since both Nicole and Noura are admins for the ACPC page, they need to agree on a secure and easy way to exchange password information whenever one of the admins changes it, therefore, Nicole suggested the following technique for doing it: Let L be the list of all strings that contain only mirrored letters {A, H, I, M, O, T, U, V, W, X, Y}, sorted by their length. If two strings have the same length, they are sorted according to the alphabetical order. Help Nicole and Noura by writing a program that finds the new password. Given a string S that contains only mirrored letters, the new password is the string in L that is located after the string S by K. The first line of input contains an integer T (1 ≤ T ≤ 256), the number of test cases. Each test case will consist of an integer K (1 ≤ K ≤ 109), followed by the string S (1 ≤ |S| ≤ 103). |S| represents the length of the string S. For each test case, print the new password on a single line. Warning: large Input/Output data, be careful with certain languages. ## Input The first line of input contains an integer T (1 ≤ T ≤ 256), the number of test cases.Each test case will consist of an integer K (1 ≤ K ≤ 109), followed by the string S (1 ≤ |S| ≤ 103).|S| represents the length of the string S. ## Output For each test case, print the new password on a single line. [samples] ## Note Warning: large Input/Output data, be careful with certain languages.

**Definitions** Let $\Sigma = \{A, H, I, M, O, T, U, V, W, X, Y\}$ be the set of mirrored letters, ordered alphabetically: $$ \Sigma = [\sigma_0, \sigma_1, \dots, \sigma_{10}] = [A, H, I, M, O, T, U, V, W, X, Y] $$ Let $L$ be the infinite lexicographically ordered list of all finite-length strings over $\Sigma$, sorted first by length (ascending), then lexicographically within each length. **Given** For each test case: - $K \in \mathbb{Z}$, $1 \leq K \leq 10^9$ - $S \in \Sigma^*$, a non-empty string of length $|S| \leq 1000$ **Objective** Find the string $P \in L$ such that $P$ is the $K$-th string after $S$ in $L$, i.e., if $S$ is at position $i$ in $L$, then $P$ is at position $i + K$. Output $P$.

API Response (JSON)

{
  "problem": {
    "name": "D. Secure but True",
    "description": {
      "content": "Since both Nicole and Noura are admins for the ACPC page, they need to agree on a secure and easy way to exchange password information whenever one of the admins changes it, therefore, Nicole suggeste",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10108D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Since both Nicole and Noura are admins for the ACPC page, they need to agree on a secure and easy way to exchange password information whenever one of the admins changes it, therefore, Nicole suggeste...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $\\Sigma = \\{A, H, I, M, O, T, U, V, W, X, Y\\}$ be the set of mirrored letters, ordered alphabetically:  \n$$ \\Sigma = [\\sigma_0, \\sigma_1, \\dots, \\sigma_{10}] = [A, H, I, M, O, T,...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments