H. Zorro's Revenge

Codeforces

IDCF10283H

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Zorro is angry at Erik (see Xorro the Xorman from the previous contest) for making a mockery of him with the creation of Xorro. The original swashbuckler decides to teach Erik a lesson by making him solve a problem of his own making, or to face the wrath of his blade. Zorro despises bitwise operations, but he is quite the number theory connoisseur. He gives Erik three positive integers $N$, $K$, and $X$, and asks the inferior swordsman to tell him if it is possible to sum exactly $K$ integer powers of $X$ to $N$. Can you save Erik from a gruesome fate (he is quite bad at number theory problems)? The first and only line of input contains three space separated integers $N$ ($1 <= N <= 10^(18)$), $K$ ($1 <= K <= 2 dot.op 10^5$), and $X$ ($2 <= X <= 9$) as described above. If it is NOT possible to construct such a sum of $K$ integer powers of $X$, output a single line containing "NO" (all caps, without quotes). If it is possible, output "YES" (all caps, without quotes) on the first line of output. The second line of output should contain $K$ space-separated integers that are all integer powers of $X$ that in total sum to $N$. It is required that the outputted list is lexicographically minimized when printed out in descending order. ## Input The first and only line of input contains three space separated integers $N$ ($1 <= N <= 10^(18)$), $K$ ($1 <= K <= 2 dot.op 10^5$), and $X$ ($2 <= X <= 9$) as described above. ## Output If it is NOT possible to construct such a sum of $K$ integer powers of $X$, output a single line containing "NO" (all caps, without quotes).If it is possible, output "YES" (all caps, without quotes) on the first line of output. The second line of output should contain $K$ space-separated integers that are all integer powers of $X$ that in total sum to $N$. It is required that the outputted list is lexicographically minimized when printed out in descending order. [samples]

**Definitions** Let $ m \in \mathbb{Z}^+ $ be the number of rings (digits in password). Let $ S \subseteq \{0,1,\dots,9\}^m $ be a set of $ n $ forbidden passwords, with $ t \in \{0,1,\dots,9\}^m $ the initial password, $ t \notin S $. Let $ G = (V, E) $ be a directed graph where: - $ V = \{0,1,\dots,9\}^m $ is the set of all possible passwords. - $ E = \{ (p, q) \mid p, q \in V, \text{ and } q \text{ differs from } p \text{ in exactly one digit by } \pm 1 \pmod{10} \} $. Let $ F = S \cup \{t\} $ be the set of forbidden states (losing positions). Let $ W \subseteq V \setminus F $ be the set of valid (non-forbidden, non-initial) positions reachable from $ t $. **Constraints** 1. $ 1 \le m \le 5 $ 2. $ 0 \le n < 10^m $ 3. $ |S| = n $, all elements of $ S $ are distinct and $ \ne t $ 4. The game starts at $ t $, and players alternate moves along edges in $ E $. 5. A player loses if they move to any state in $ F $. **Objective** Determine the winner under optimal play: - Alice moves first. - The player who cannot make a move without entering $ F $ loses. - Output "Alice" if the starting position $ t $ is a winning position for the first player; "Bob" otherwise. Formally: Let $ f: V \setminus F \to \{\text{Win}, \text{Lose}\} $ be defined recursively: - $ f(p) = \text{Lose} $ if all neighbors $ q \in N(p) $ satisfy $ q \in F $ or $ f(q) = \text{Win} $. - $ f(p) = \text{Win} $ if there exists a neighbor $ q \in N(p) \setminus F $ such that $ f(q) = \text{Lose} $. Output: $$ \begin{cases} \text{Alice} & \text{if } f(t) = \text{Win} \\ \text{Bob} & \text{if } f(t) = \text{Lose} \end{cases} $$

API Response (JSON)

{
  "problem": {
    "name": "H. Zorro's Revenge",
    "description": {
      "content": "Zorro is angry at Erik (see Xorro the Xorman from the previous contest) for making a mockery of him with the creation of Xorro. The original swashbuckler decides to teach Erik a lesson by making him s",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10283H"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Zorro is angry at Erik (see Xorro the Xorman from the previous contest) for making a mockery of him with the creation of Xorro. The original swashbuckler decides to teach Erik a lesson by making him s...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ m \\in \\mathbb{Z}^+ $ be the number of rings (digits in password).  \nLet $ S \\subseteq \\{0,1,\\dots,9\\}^m $ be a set of $ n $ forbidden passwords, with $ t \\in \\{0,1,\\dots,9\\}^m ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments